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 = 1 = 1 = 1 = 2 1 − 1 = 1 = 2^1 - 1 = 1 = 2 1 − 1 = 1
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 = 1 = 1 = 1 = [ 1 × 2 2 ] 2 = 1 = \left[\frac{1 \times 2}{2}\right]^2 = 1 = [ 2 1 × 2 ] 2 = 1
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 } a 1 = 1 a_1 = 1 a 1 = 1 a n + 1 = 2 a n + 1 a_{n+1} = 2a_n + 1 a n + 1 = 2 a n + 1 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
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 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 (2 个标签)
mathematical induction equality proof
Base case : when n = 1 n = 1 n = 1 = 1 × 2 = 2 = 1 \times 2 = 2 = 1 × 2 = 2 = 1 × 2 × 3 3 = 2 = \frac{1 \times 2 \times 3}{3} = 2 = 3 1 × 2 × 3 = 2
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.
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 (2 个标签)
mathematical induction equality proof
Base case : when n = 1 n = 1 n = 1 = 1 2 = \frac{1}{2} = 2 1 = 1 2 = \frac{1}{2} = 2 1
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.
Exercise 3
The sequence { a n } \{a_n\} { a n } a 1 = 2 a_1 = 2 a 1 = 2 a n + 1 = 3 a n − 2 a_{n+1} = 3a_n - 2 a n + 1 = 3 a n − 2 a n = 2 n a_n = 2^n a n = 2 n
Reference Answer (2 个标签)
mathematical induction equality proof
Base case : when n = 1 n = 1 n = 1 a 1 = 2 = 2 1 a_1 = 2 = 2^1 a 1 = 2 = 2 1
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 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 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
Summary Symbols Used in This Article
符号 类型 读音/说明 在本文中的含义 f ( n ) , g ( n ) f(n), g(n) f ( n ) , g ( n ) 数学符号 f/g of n The expressions on the two sides of the equality n , k n, k n , k 数学符号 n, k Natural numbers a n a_n a n 数学符号 a-sub-n The n n n { a n } \{a_n\} { a n } 数学符号 set of a-sub-n A sequence ⋯ \cdots ⋯ 数学符号 and so on Ellipsis n ( n + 1 ) 2 \frac{n(n+1)}{2} 2 n ( n + 1 ) 数学符号 n(n+1) over 2 The sum of the first n n n ∑ \sum ∑ 数学符号 sum The summation symbol
中英对照
中文术语 英文术语 音标 说明 求和公式 summation formula /sʌˈmeɪʃən ˈfɔːmjələ/ A formula expressing a sum 递推关系 recurrence relation /rɪˈkɜːrəns rɪˈleɪʃən/ A relation defining later terms from earlier ones 立方和 sum of cubes /sʌm əv kjuːbz/ 1 3 + 2 3 + ⋯ + n 3 1^3 + 2^3 + \cdots + n^3 1 3 + 2 3 + ⋯ + n 3 数学归纳法 mathematical induction /ˌmæθəˈmætɪkəl ɪnˈdʌkʃən/ A proof method from the base case to the general 归纳步骤 inductive step /ɪnˈdʌktɪv step/ Deriving from n = k n=k n = k n = k + 1 n=k+1 n = k + 1
