This page presents several classical problems solved using the principle of mathematical induction.
Mathematical induction is a proof technique used to show that a statement \(P(n)\) is true for all integers \(n \ge N\), where \(N\) is a fixed positive integer.
The proof consists of two steps:
Use mathematical induction to prove that
\[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \]for all positive integers \(n\).
Let \(P(n)\) be the statement \[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}. \]
Step 1: For \(n = 1\),
\[ 1 = \frac{1(1+1)}{2} = 1. \]Thus, \(P(1)\) is true.
Step 2: Assume \(P(k)\) is true:
\[ 1 + 2 + \cdots + k = \frac{k(k+1)}{2}. \]Add \(k+1\) to both sides:
\[ 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}. \]This proves \(P(k+1)\). Hence, the statement is true for all \(n\).
Prove that
\[ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \]for all positive integers \(n\).
Base Step: For \(n = 1\),
\[ 1^2 = \frac{1(2)(3)}{6} = 1. \]Induction Step: Assume
\[ 1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}. \]Add \((k+1)^2\):
\[ \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}. \]This proves \(P(k+1)\).
Prove that
\[ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2 (n+1)^2}{4}. \]Base Step:
\[ 1^3 = \frac{1^2(2)^2}{4} = 1. \]Induction Step: Assume the formula holds for \(k\).
Add \((k+1)^3\) and factor:
\[ \frac{k^2 (k+1)^2}{4} + (k+1)^3 = \frac{(k+1)^2 (k+2)^2}{4}. \]Thus, the formula holds for all \(n\).
Prove that \(n^3 + 2n\) is divisible by \(3\) for all positive integers \(n\).
Base Step:
\[ 1^3 + 2(1) = 3. \]Induction Step:
\[ (k+1)^3 + 2(k+1) = (k^3 + 2k) + 3(k^2 + k + 1). \]This expression is divisible by \(3\), completing the proof.
Prove that
\[ 3^n > n^2 \quad \text{for all integers } n \ge 3. \]The inequality is verified for \(n = 1, 2\). Assuming it holds for \(k\):
\[ 3^{k+1} = 3 \cdot 3^k > 3k^2 > (k+1)^2. \]Thus, the inequality holds for all \(n \ge 3\).
Prove that
\[ n! > 2^n \quad \text{for all } n \ge 4. \]Base Step:
\[ 4! = 24 > 16 = 2^4. \]Induction Step:
\[ (k+1)! = (k+1)k! > (k+1)2^k > 2^{k+1}. \]Prove that
\[ [R(\cos t + i \sin t)]^n = R^n(\cos nt + i \sin nt) \]for all positive integers \(n\).
The result holds for \(n = 1\). Assume it is true for \(n = k\).
Multiply both sides by \(R(\cos t + i \sin t)\) and apply trigonometric identities:
\[ \cos(kt+t) + i\sin(kt+t) = \cos((k+1)t) + i\sin((k+1)t). \]This completes the induction proof.