We've updated our
Privacy Policy effective December 15. Please read our updated Privacy Policy and tap

Study Guides > Boundless Algebra

Mathematical Inductions

Sequences of Mathematical Statements

Sequences of statements are logical, ordered groups of statements that are important for mathematical induction.

Learning Objectives

Discuss what is meant by a sequence of mathematical statements

Key Takeaways

Key Points

  • A sequence is an ordered list of objects or events. Like a set, it contains members, but unlike a set, the order of the members matters.
  • A sequence of statements refers to the progression of logical implications of one statement.
  • Sequences of statements are important for mathematical inductions, which rely on infinite sequences of statements.

Key Terms

  • natural numbers: A set of numbers sometimes described as all non-negative integers [latex](0, 1, 2,...)[/latex] and sometimes described as all positive integers [latex](1, 2, 3,...)[/latex].
  • set: A collection of zero or more objects, possibly infinite in size, and disregarding any order or repetition of the objects that may be contained within it.
In mathematics, a sequence is an ordered list of objects, or elements. The length of a sequence is the number of ordered elements, and it may be infinite. Unlike a set, order matters in sequences, and exactly the same elements can appear multiple times at different positions in the sequence. A sequence is a discrete function. For example, [latex]\left ( M,A,R,Y \right )[/latex] is a sequence of letters that differs from [latex]\left ( A,R,M,Y \right )[/latex]. Although the composition is the same, the ordering differs. Sequences can be finite, as in this example, or infinite, such as the sequence of all even positive integers [latex](2,4,6, \cdots )[/latex]. In mathematics, a "sequence of statements" refers to the progression of logical implications of one statement. In this case, a "statement" usually refers to an equation that contains an equal sign. Sequences of statements are necessary for mathematical induction. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one. For example, in the context of mathematical induction, a sequence of statements usually involves an algebraic statement into which you can substitute any natural number [latex](0, 1, 2, 3,...)[/latex] and the statement should hold true. So a sequence is formed by substituting integers [latex]k[/latex], [latex]k + 1 [/latex], [latex]k + 2[/latex] and so on into the mathematical statement. This concept will be expanded on in the following concept, which introduces proof by mathematical induction.

Proof by Mathematical Induction

Proving an infinite sequence of statements is necessary for proof by induction, a rigorous form of deductive reasoning.

Learning Objectives

Use mathematical induction to prove an infinite sequence of statements

Key Takeaways

Key Points

  • Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers.
  • It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.
  • Proving an infinite sequence of statements can be understood in the context of the domino effect, which by nature mediates a sequential and predictable order of events.

Key Terms

  • inductive reasoning: The process of making inferences based upon observed patterns, or simple repetition. Often used in reference to predictions about what will happen or does happen, based upon what has happened.
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers (non-negative integers ). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one. The simplest and most common form of mathematical induction proves that a statement involving a natural number [latex]n[/latex] holds for all values of [latex]n[/latex]. The proof consists of two steps:
  1. The basis ( base case): showing that the statement holds when [latex]n[/latex] is equal to the lowest value that [latex]n[/latex] is given in the question. Usually, [latex]n=0[/latex] or [latex]n=1[/latex].
  2. The inductive step: showing that if the statement holds for some [latex]n[/latex], then the statement also holds when [latex]n+1[/latex] is substituted for [latex]n[/latex].
The assumption in the inductive step that the statement holds for some [latex]n[/latex], is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for [latex]n+1[/latex]. The choice between [latex]n=0[/latex] and [latex]n=1[/latex] in the base case is specific to the context of the proof: If [latex]0[/latex] is considered a natural number, as is common in the fields of combinatorics and mathematical logic, then [latex]n=0[/latex]. If, on the other hand, [latex]1[/latex] is taken as the first natural number, then the base case is given by [latex]n=1[/latex]. This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly.

Visualization

It may be helpful to think of the domino effect. If one is presented with a long row of dominoes standing on end, one can be sure that:
  1. The first domino will fall
  2. Whenever a domino falls, its next neighbor will also fall
So it is concluded that all of the dominoes will fall, and that this fact is inevitable.
image Dominoes: Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes.

Example

Prove the following statement: For each positive integer [latex]n[/latex], [latex-display]\displaystyle{0 + 1 + 2 + \cdots + n = \frac{n(n+1)}{2}}[/latex-display] Base Case: We first have to check that the statement holds for [latex]n=0[/latex]. On the left-hand side of the equation, we have only [latex]0[/latex]. On the right hand side of the equation we substitute [latex]n=0[/latex]. Thus we have  [latex]\displaystyle{0 = \frac{0(0+1)}{2}}[/latex], which can be simplified to [latex]0= 0[/latex]. We have proven that the statement holds true for the base case of [latex]n=0[/latex]. Inductive Step: Assume that the statement holds for [latex]n=k[/latex], and check if it holds for [latex]n=k+1[/latex] as well. In other words, we want to show that the statement holds true when we substitute [latex]k+1[/latex] for [latex]n[/latex]: [latex-display]\displaystyle{0 + 1 + 2 + \cdots + k + (k+1) = \frac{\left(k+1\right)\left[\left(k+1\right)+1\right]}{2}}[/latex-display] Note that we can use the induction hypothesis that the statement holds for [latex]n=k[/latex] to rewrite the left-hand side of the equation: [latex-display]\displaystyle{0 + 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2}} + (k+1)[/latex-display] We can now rewrite this statement and show that it equals the right-hand side of the previous statement. In other words, if we can show that the following holds true, we will show that [latex]\displaystyle{0 + 1 + 2 + \cdots + n = \frac{n(n+1)}{2}}[/latex] holds true for [latex]k+1[/latex]: [latex-display]\displaystyle{\frac{k(k+1)}{2} + (k+1) = \frac{\left(k+1\right)\left[\left(k+1\right)+1\right]}{2} }[/latex-display] We can rewrite [latex]\displaystyle{\frac{k(k+1)}{2} + (k+1)}[/latex] algebraically as follows: [latex]\displaystyle{ \begin{align} \frac{k(k+1)}{2} + (k+1) &= \frac{k(k+1) + 2(k+1)}{2} \\ &=\frac{(k+1)(k+2)}{2} \\ &=\frac{\left(k+1\right)\left[\left(k+1\right)+1\right]}{2} \end{align} }[/latex] This is exactly we wanted to prove. We have shown that [latex]\displaystyle{0 + 1 + 2 + \cdots + n = \frac{n(n+1)}{2}}[/latex] holds true for any [latex]n = k + 1[/latex] if it holds true for [latex]n = k[/latex]. This completes the induction step. We conclude that the statement holds for every non-negative integer [latex]n[/latex].

Licenses & Attributions

CC licensed content, Shared previously

CC licensed content, Specific attribution