This is a beta course, so its structure, chapters, and examples may continue to change.
Proving Equalities
Proving equalities with mathematical induction is the most common application. Such problems usually involve summation formulas, product formulas, or recurrence relations.
Proof Strategy
The steps to prove the equality f ( n ) = g ( n ) f(n) = g(n) f ( n ) = g ( n ) :
Base case : verify that f ( n 0 ) = g ( n 0 ) f(n_0) = g(n_0) f ( n 0 ) = g ( n 0 )
Inductive hypothesis : assume f ( k ) = g ( k ) f(k) = g(k) f ( k ) = g ( k )
Inductive step : use the inductive hypothesis to prove f ( k + 1 ) = g ( k + 1 ) f(k+1) = g(k+1) f ( k + 1 ) = g ( k + 1 )
Key technique : in the inductive step, split
f ( k + 1 ) f(k+1) f ( k + 1 ) into
f ( k ) f(k) f ( k ) plus the newly added term, then replace
f ( k ) f(k) f ( k ) using the inductive hypothesis.
Worked Examples
Example 1: Sum of a Geometric Sequence
Proposition : prove that 1 + 2 + 2 2 + ⋯ + 2 n − 1 = 2 n − 1 1 + 2 + 2^2 + \cdots + 2^{n-1} = 2^n - 1 1 + 2 + 2 2 + ⋯ + 2 n − 1 = 2 n − 1
Proof :
Base case : when n = 1 n = 1 n = 1 , the left side = 1 = 1 = 1 and the right side = 2 1 − 1 = 1 = 2^1 - 1 = 1 = 2 1 − 1 = 1 , holds.
Inductive hypothesis : assume 1 + 2 + 2 2 + ⋯ + 2 k − 1 = 2 k − 1 1 + 2 + 2^2 + \cdots + 2^{k-1} = 2^k - 1 1 + 2 + 2 2 + ⋯ + 2 k − 1 = 2 k − 1
Inductive step :
1 + 2 + 2 2 + ⋯ + 2 k − 1 + 2 k = ( 2 k − 1 ) + 2 k (inductive hypothesis) = 2 ⋅ 2 k − 1 = 2 k + 1 − 1 \begin{aligned}
&1 + 2 + 2^2 + \cdots + 2^{k-1} + 2^k \\
&= (2^k - 1) + 2^k \quad \text{(inductive hypothesis)} \\
&= 2 \cdot 2^k - 1 \\
&= 2^{k+1} - 1
\end{aligned} 1 + 2 + 2 2 + ⋯ + 2 k − 1 + 2 k = ( 2 k − 1 ) + 2 k (inductive hypothesis) = 2 ⋅ 2 k − 1 = 2 k + 1 − 1
Conclusion : by mathematical induction, the equality holds.
Proposition : prove that 1 3 + 2 3 + 3 3 + ⋯ + n 3 = [ n ( n + 1 ) 2 ] 2 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2 1 3 + 2 3 + 3 3 + ⋯ + n 3 = [ 2 n ( n + 1 ) ] 2
Proof :
Base case : when n = 1 n = 1 n = 1 , the left side = 1 = 1 = 1 and the right side = [ 1 × 2 2 ] 2 = 1 = \left[\frac{1 \times 2}{2}\right]^2 = 1 = [ 2 1 × 2 ] 2 = 1 , holds.
Inductive hypothesis : assume 1 3 + 2 3 + ⋯ + k 3 = [ k ( k + 1 ) 2 ] 2 1^3 + 2^3 + \cdots + k^3 = \left[\frac{k(k+1)}{2}\right]^2 1 3 + 2 3 + ⋯ + k 3 = [ 2 k ( k + 1 ) ] 2
Inductive step :
1 3 + 2 3 + ⋯ + k 3 + ( k + 1 ) 3 = [ k ( k + 1 ) 2 ] 2 + ( k + 1 ) 3 = k 2 ( k + 1 ) 2 4 + ( k + 1 ) 3 = k 2 ( k + 1 ) 2 + 4 ( k + 1 ) 3 4 = ( k + 1 ) 2 [ k 2 + 4 ( k + 1 ) ] 4 = ( k + 1 ) 2 ( k 2 + 4 k + 4 ) 4 = ( k + 1 ) 2 ( k + 2 ) 2 4 = [ ( k + 1 ) ( k + 2 ) 2 ] 2 \begin{aligned}
&1^3 + 2^3 + \cdots + k^3 + (k+1)^3 \\
&= \left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3 \\
&= \frac{k^2(k+1)^2}{4} + (k+1)^3 \\
&= \frac{k^2(k+1)^2 + 4(k+1)^3}{4} \\
&= \frac{(k+1)^2[k^2 + 4(k+1)]}{4} \\
&= \frac{(k+1)^2(k^2 + 4k + 4)}{4} \\
&= \frac{(k+1)^2(k+2)^2}{4} \\
&= \left[\frac{(k+1)(k+2)}{2}\right]^2
\end{aligned} 1 3 + 2 3 + ⋯ + k 3 + ( k + 1 ) 3 = [ 2 k ( k + 1 ) ] 2 + ( k + 1 ) 3 = 4 k 2 ( k + 1 ) 2 + ( k + 1 ) 3 = 4 k 2 ( k + 1 ) 2 + 4 ( k + 1 ) 3 = 4 ( k + 1 ) 2 [ k 2 + 4 ( k + 1 )] = 4 ( k + 1 ) 2 ( k 2 + 4 k + 4 ) = 4 ( k + 1 ) 2 ( k + 2 ) 2 = [ 2 ( k + 1 ) ( k + 2 ) ] 2
Conclusion : by mathematical induction, the equality holds.
Example 3: A Recurrence Sequence
Proposition : the sequence { a n } \{a_n\} { a n } satisfies a 1 = 1 a_1 = 1 a 1 = 1 and a n + 1 = 2 a n + 1 a_{n+1} = 2a_n + 1 a n + 1 = 2 a n + 1 . Prove that a n = 2 n − 1 a_n = 2^n - 1 a n = 2 n − 1 .
Proof :
Base case : when n = 1 n = 1 n = 1 , a 1 = 1 = 2 1 − 1 a_1 = 1 = 2^1 - 1 a 1 = 1 = 2 1 − 1 , holds.
Inductive hypothesis : assume a k = 2 k − 1 a_k = 2^k - 1 a k = 2 k − 1
Inductive step :
a k + 1 = 2 a k + 1 = 2 ( 2 k − 1 ) + 1 (inductive hypothesis) = 2 k + 1 − 2 + 1 = 2 k + 1 − 1 \begin{aligned}
a_{k+1} &= 2a_k + 1 \\
&= 2(2^k - 1) + 1 \quad \text{(inductive hypothesis)} \\
&= 2^{k+1} - 2 + 1 \\
&= 2^{k+1} - 1
\end{aligned} a k + 1 = 2 a k + 1 = 2 ( 2 k − 1 ) + 1 (inductive hypothesis) = 2 k + 1 − 2 + 1 = 2 k + 1 − 1
Conclusion : by mathematical induction, a n = 2 n − 1 a_n = 2^n - 1 a n = 2 n − 1 for all n ≥ 1 n \geq 1 n ≥ 1 .
Practice Problems
Exercise 1
Prove: 1 × 2 + 2 × 3 + 3 × 4 + ⋯ + n ( n + 1 ) = n ( n + 1 ) ( n + 2 ) 3 1 \times 2 + 2 \times 3 + 3 \times 4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3} 1 × 2 + 2 × 3 + 3 × 4 + ⋯ + n ( n + 1 ) = 3 n ( n + 1 ) ( n + 2 )
Reference Answer mathematical induction equality proof
Approach : Use mathematical induction: verify the equality for n = 1 n = 1 n = 1 , then carry the induction hypothesis over to the n + 1 n + 1 n + 1 case.
Steps :
Base case : when n = 1 n = 1 n = 1 , the left side = 1 × 2 = 2 = 1 \times 2 = 2 = 1 × 2 = 2 and the right side = 1 × 2 × 3 3 = 2 = \frac{1 \times 2 \times 3}{3} = 2 = 3 1 × 2 × 3 = 2 , holds.
Inductive hypothesis : assume the equality holds for n = k n = k n = k .
Inductive step :
1 × 2 + ⋯ + k ( k + 1 ) + ( k + 1 ) ( k + 2 ) = k ( k + 1 ) ( k + 2 ) 3 + ( k + 1 ) ( k + 2 ) = k ( k + 1 ) ( k + 2 ) + 3 ( k + 1 ) ( k + 2 ) 3 = ( k + 1 ) ( k + 2 ) ( k + 3 ) 3 \begin{aligned}
&1 \times 2 + \cdots + k(k+1) + (k+1)(k+2) \\
&= \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) \\
&= \frac{k(k+1)(k+2) + 3(k+1)(k+2)}{3} \\
&= \frac{(k+1)(k+2)(k+3)}{3}
\end{aligned} 1 × 2 + ⋯ + k ( k + 1 ) + ( k + 1 ) ( k + 2 ) = 3 k ( k + 1 ) ( k + 2 ) + ( k + 1 ) ( k + 2 ) = 3 k ( k + 1 ) ( k + 2 ) + 3 ( k + 1 ) ( k + 2 ) = 3 ( k + 1 ) ( k + 2 ) ( k + 3 ) Conclusion : by mathematical induction, the equality holds.
Answer : By mathematical induction, the equality holds.
Exercise 2
Prove: 1 1 × 2 + 1 2 × 3 + ⋯ + 1 n ( n + 1 ) = n n + 1 \frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1} 1 × 2 1 + 2 × 3 1 + ⋯ + n ( n + 1 ) 1 = n + 1 n
Reference Answer mathematical induction equality proof
Approach : Use mathematical induction: verify the equality for n = 1 n = 1 n = 1 , then carry the induction hypothesis over to the n + 1 n + 1 n + 1 case.
Steps :
Base case : when n = 1 n = 1 n = 1 , the left side = 1 2 = \frac{1}{2} = 2 1 and the right side = 1 2 = \frac{1}{2} = 2 1 , holds.
Inductive hypothesis : assume the equality holds for n = k n = k n = k .
Inductive step :
1 1 × 2 + ⋯ + 1 k ( k + 1 ) + 1 ( k + 1 ) ( k + 2 ) = k k + 1 + 1 ( k + 1 ) ( k + 2 ) = k ( k + 2 ) + 1 ( k + 1 ) ( k + 2 ) = k 2 + 2 k + 1 ( k + 1 ) ( k + 2 ) = ( k + 1 ) 2 ( k + 1 ) ( k + 2 ) = k + 1 k + 2 \begin{aligned}
&\frac{1}{1 \times 2} + \cdots + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} \\
&= \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} \\
&= \frac{k(k+2) + 1}{(k+1)(k+2)} \\
&= \frac{k^2 + 2k + 1}{(k+1)(k+2)} \\
&= \frac{(k+1)^2}{(k+1)(k+2)} \\
&= \frac{k+1}{k+2}
\end{aligned} 1 × 2 1 + ⋯ + k ( k + 1 ) 1 + ( k + 1 ) ( k + 2 ) 1 = k + 1 k + ( k + 1 ) ( k + 2 ) 1 = ( k + 1 ) ( k + 2 ) k ( k + 2 ) + 1 = ( k + 1 ) ( k + 2 ) k 2 + 2 k + 1 = ( k + 1 ) ( k + 2 ) ( k + 1 ) 2 = k + 2 k + 1 Conclusion : by mathematical induction, the equality holds.
Answer : By mathematical induction, the equality holds.
Exercise 3
The sequence { a n } \{a_n\} { a n } satisfies a 1 = 2 a_1 = 2 a 1 = 2 and a n + 1 = 3 a n − 2 a_{n+1} = 3a_n - 2 a n + 1 = 3 a n − 2 . Prove that a n = 2 n a_n = 2^n a n = 2 n .
Reference Answer mathematical induction equality proof
Approach : First derive the general term of the sequence from the recurrence, then use mathematical induction to check that this general term satisfies both the recurrence and the initial condition.
Steps :
Base case : when n = 1 n = 1 n = 1 , a 1 = 2 = 2 1 a_1 = 2 = 2^1 a 1 = 2 = 2 1 , holds.
Inductive hypothesis : assume a k = 2 k a_k = 2^k a k = 2 k
Inductive step :
a k + 1 = 3 a k − 2 = 3 ⋅ 2 k − 2 = 3 ⋅ 2 k − 2 1 = 2 ( 3 ⋅ 2 k − 1 − 1 ) \begin{aligned}
a_{k+1} &= 3a_k - 2 \\
&= 3 \cdot 2^k - 2 \\
&= 3 \cdot 2^k - 2^1 \\
&= 2(3 \cdot 2^{k-1} - 1)
\end{aligned} a k + 1 = 3 a k − 2 = 3 ⋅ 2 k − 2 = 3 ⋅ 2 k − 2 1 = 2 ( 3 ⋅ 2 k − 1 − 1 ) This method is not quite right. Let us verify: a 2 = 3 × 2 − 2 = 4 = 2 2 a_2 = 3 \times 2 - 2 = 4 = 2^2 a 2 = 3 × 2 − 2 = 4 = 2 2 ✓
Re-prove:
a k + 1 = 3 a k − 2 = 3 ⋅ 2 k − 2 \begin{aligned}
a_{k+1} &= 3a_k - 2 \\
&= 3 \cdot 2^k - 2
\end{aligned} a k + 1 = 3 a k − 2 = 3 ⋅ 2 k − 2 We need to show that this equals 2 k + 1 2^{k+1} 2 k + 1 . But 3 ⋅ 2 k − 2 ≠ 2 k + 1 3 \cdot 2^k - 2 \neq 2^{k+1} 3 ⋅ 2 k − 2 = 2 k + 1 .
Let me verify: a 3 = 3 × 4 − 2 = 10 ≠ 8 a_3 = 3 \times 4 - 2 = 10 \neq 8 a 3 = 3 × 4 − 2 = 10 = 8
So a n = 2 n a_n = 2^n a n = 2 n does not hold. The correct general term should be a n = 2 n + 2 n − 1 = 3 ⋅ 2 n − 1 a_n = 2^n + 2^{n-1} = 3 \cdot 2^{n-1} a n = 2 n + 2 n − 1 = 3 ⋅ 2 n − 1 …
Actually, let me recalculate: a 1 = 2 , a 2 = 4 , a 3 = 10 a_1 = 2, a_2 = 4, a_3 = 10 a 1 = 2 , a 2 = 4 , a 3 = 10 …
By working out the recurrence, one can discover that a n = 2 ⋅ 3 n − 1 a_n = 2 \cdot 3^{n-1} a n = 2 ⋅ 3 n − 1 .
Answer : The claim to be proved, a n = 2 n a_n = 2^n a n = 2 n , does not hold : a 2 = 3 × 2 − 2 = 4 = 2 2 a_2 = 3 \times 2 - 2 = 4 = 2^2 a 2 = 3 × 2 − 2 = 4 = 2 2 happens to match, but a 3 = 3 × 4 − 2 = 10 ≠ 2 3 = 8 a_3 = 3 \times 4 - 2 = 10 \neq 2^3 = 8 a 3 = 3 × 4 − 2 = 10 = 2 3 = 8 . The fixed-point method gives the correct general term a n = 3 n − 1 + 1 a_n = 3^{n-1} + 1 a n = 3 n − 1 + 1 (check: a 1 = 2 a_1 = 2 a 1 = 2 , and 3 ( 3 n − 1 + 1 ) − 2 = 3 n + 1 3(3^{n-1} + 1) - 2 = 3^n + 1 3 ( 3 n − 1 + 1 ) − 2 = 3 n + 1 ).
Summary
Symbols Used in This Article
Symbol notation
Symbol Type Pronunciation/Explanation Meaning in This Article f ( n ) , g ( n ) f(n), g(n) f ( n ) , g ( n ) Mathematical symbol f/g of n The expressions on the two sides of the equality n , k n, k n , k Mathematical symbol n, k Natural numbers a n a_n a n Mathematical symbol a-sub-n The n n n th term of a sequence { a n } \{a_n\} { a n } Mathematical symbol set of a-sub-n A sequence ⋯ \cdots ⋯ Mathematical symbol and so on Ellipsis n ( n + 1 ) 2 \frac{n(n+1)}{2} 2 n ( n + 1 ) Mathematical symbol n(n+1) over 2 The sum of the first n n n natural numbers ∑ \sum ∑ Mathematical symbol sum The summation symbol