The Domino Effect of Truth
Mathematical Induction is a powerful proof technique used to prove a statement \( P(n) \) for all natural numbers \( n \in \mathbb{N} \). Intuitively, it works exactly like a row of falling dominoes.
1. Base Case \( P(1) \)
You must push the first domino. If the first one doesn't fall, the chain reaction never starts.
2. Inductive Step \( P(k) \implies P(k+1) \)
Ensure the gap isn't too wide! If domino \( k \) falls, it must hit domino \( k+1 \).
Formal Definition
Let \( P(n) \) be a property defined for \( n \in \mathbb{N} \). If:
- Base Case: \( P(1) \) is true.
- Inductive Step: For every \( k \in \mathbb{N} \), if \( P(k) \) is true, then \( P(k+1) \) is true.
Then \( P(n) \) is true for all \( n \in \mathbb{N} \).
Visual Proof: Sum of First \( n \) Integers
Let's prove that \( \sum_{i=1}^n i = \frac{n(n+1)}{2} \). Visually, this sum represents a triangular stack of blocks. Two such triangles form a rectangle of area \( n(n+1) \).
Inductive Proof Sketch
LHS: \( 1 \). RHS: \( \frac{1(2)}{2} = 1 \). True.
Assume \( 1 + \dots + k = \frac{k(k+1)}{2} \).
Add \( k+1 \) to both sides:
\( \frac{k(k+1)}{2} + (k+1) \)
\( = (k+1)(\frac{k}{2} + 1) \)
\( = (k+1)(\frac{k+2}{2}) \)
\( = \frac{(k+1)((k+1)+1)}{2} \)
This matches the formula for \( n = k+1 \)!
Practice Problems
True/False
1. In a proof by induction, proving the base case \( P(1) \) is optional if the induction step is correct.
Show Solution
FALSE - Both base case AND induction step are required.
2. The induction step requires proving \( P(n+1) \) is true assuming \( P(n) \) is true.
Show Solution
TRUE - This is exactly the induction step.
3. If \( P(n) \implies P(n+1) \) for all \( n \), then all \( P(n) \) are true.
Show Solution
FALSE - Need base case too! Otherwise no anchor point.
4. Mathematical induction can only be used to prove formulas involving sums.
Show Solution
FALSE - Can prove inequalities, divisibility, etc.
Fill in the Blank
5. Prove by induction that \( 3 + 11 + 19 + ... + (8n-5) = 4n^2 - n \)
Base case: \( n = 1 \). LHS = 3, RHS = \( 4(1)^2 - 1 = \) _____ ✓
Induction step: Assume \( 3 + 11 + ... + (8k-5) = \) _____
Adding next term: \( 3 + 11 + ... + (8k-5) + (8(k+1)-5) \)
= [_____] + \( (8k+3) \) [by induction hypothesis]
= \( 4k^2 - k + 8k + 3 \)
= \( 4k^2 + \) _____ \( + 3 \)
= \( 4(k^2 + 2k + 1) + (k+1) - 4 \)
= \( 4( \)_____ \( )^2 - (k+1) \) ✓
Show Solution
Base: 3
Induction hypothesis: \( 4k^2 - k \)
First blank: \( 4k^2 - k \)
Second blank: \( 7k \)
Third blank: \( k+1 \)
6. Prove \( 7^n - 6n - 1 \) is divisible by 36 for all \( n \in \mathbb{N} \)
Base case: \( n = 1 \). \( 7^1 - 6(1) - 1 = \) _____ \( = 0 = 36(0) \) ✓
Induction step: Assume \( 7^k - 6k - 1 = \) _____ for some integer \( m \)
Consider \( n = k+1 \):
\( 7^{k+1} - 6(k+1) - 1 \)
\( = 7 \cdot 7^k - 6k - 6 - 1 \)
\( = 7( \)_____ \( + 6k + 1) - 6k - 7 \) [solve for \( 7^k \) from hypothesis]
\( = 7 \cdot 36m + \) _____ \( + 7 - 6k - 7 \)
\( = 36(7m) + \) _____ ✓
Show Solution
Base: 0
Hypothesis: \( 36m \)
First \( 7^k \): \( 36m \)
Second blank: \( 42k \)
Third blank: \( 36k \)
7. Show that for all \( n \ge 4 \), \( n! \gt n^2 \)
Base case: \( n = 4 \). \( 4! = \) _____, \( 4^2 = 16 \), so \( 24 \gt 16 \) ✓
Induction step: Assume \( k! \gt k^2 \) for some \( k \ge 4 \)
Consider \( (k+1)! \):
\( (k+1)! = (k+1) \cdot k! \)
\( \gt (k+1) \cdot \) _____ [by hypothesis]
Need to show \( (k+1) \cdot k^2 \gt (k+1)^2 \)
Dividing by \( (k+1) \): \( k^2 \gt \) _____
This is true since \( k \ge 4 \) ✓
Show Solution
4! = 24
Hypothesis: \( k^2 \)
Last blank: \( k+1 \)
Full Problems
8. Prove \( 1^2 + 2^2 + ... + n^2 = \frac{1}{6}n(n+1)(2n+1) \) for all \( n \in \mathbb{N} \)
Show Solution
Base case: \( n=1 \). LHS = \( 1^2 = 1 \). RHS = \( \frac{1}{6}(1)(2)(3) = 1 \) ✓
Induction step: Assume \( 1^2 + ... + k^2 = \frac{1}{6}k(k+1)(2k+1) \)
Consider \( n = k+1 \):
\( 1^2 + ... + k^2 + (k+1)^2 \)
\( = \frac{1}{6}k(k+1)(2k+1) + (k+1)^2 \)
\( = (k+1)[\frac{1}{6}k(2k+1) + (k+1)] \)
\( = (k+1)[\frac{1}{6}(2k^2+k+6k+6)] \)
\( = \frac{1}{6}(k+1)(2k^2+7k+6) \)
\( = \frac{1}{6}(k+1)(k+2)(2k+3) \) ✓
9. Prove \( n^2 \gt n+1 \) for all integers \( n \ge 2 \)
Show Solution
Base case: \( n=2 \). \( 4 \gt 3 \) ✓
Induction step: Assume \( k^2 \gt k+1 \)
\( (k+1)^2 = k^2 + 2k + 1 \gt (k+1) + 2k + 1 = 3k + 2 \)
Need \( 3k+2 \gt k+2 \), which is \( 2k \gt 0 \), true for \( k \ge 2 \).
10. Prove \( |\sin(nx)| \le n|\sin(x)| \) for all \( n \in \mathbb{N} \)
Show Solution
Base case: \( n=1 \). \( |\sin(x)| \le |\sin(x)| \) ✓
Induction step: Assume \( |\sin(kx)| \le k|\sin(x)| \)
\( |\sin((k+1)x)| = |\sin(kx+x)| \le |\sin(kx)\cos(x)| + |\cos(kx)\sin(x)| \)
\( \le k|\sin(x)|(1) + (1)|\sin(x)| = (k+1)|\sin(x)| \) ✓
11. Prove \( 1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2 \)
Show Solution
Base case: \( n=1 \). \( 1 = 1 \) ✓
Induction step: Assume \( \sum k^3 = (\sum k)^2 \)
Use \( \sum_{i=1}^k i = \frac{k(k+1)}{2} \).
Show \( [\frac{k(k+1)}{2}]^2 + (k+1)^3 = [\frac{(k+1)(k+2)}{2}]^2 \)
Algebra check: \( (k+1)^2 [\frac{k^2}{4} + k + 1] = (k+1)^2 [\frac{k^2+4k+4}{4}] = [\frac{(k+1)(k+2)}{2}]^2 \) ✓
Practice Problems
1. True/False
Mathematical Induction can be used to prove statements for all real numbers.
Show Solution
False. Mathematical Induction is primarily used for proving statements about natural numbers (integers \( n \ge 1 \)) or other countably infinite sets.
The base case is optional if the inductive step is strong enough.
Show Solution
False. The base case is essential. Without it, the "domino chain" never starts falling, even if the inductive step is valid.
In the inductive step, we assume \( P(n) \) is true to prove \( P(n+1) \) is true.
Show Solution
True. This assumption is called the Inductive Hypothesis.
2. Fill in the Blank
To prove a statement \( P(n) \) for all \( n \in \mathbb{N} \), we first verify the case.
Show Solution
Base
The assumption that \( P(k) \) is true is called the hypothesis.
Show Solution
Inductive (or Induction)
The sum of the first \( n \) integers is given by the formula \( \frac{n(n+1)}{?} \). The missing denominator is .
Show Solution
2
3. Full Problems
Problem 1: Prove that \( 1 + 3 + 5 + \dots + (2n-1) = n^2 \) for all \( n \ge 1 \).
Show Solution
Base Case: For \( n=1 \), LHS = \( 2(1)-1 = 1 \). RHS = \( 1^2 = 1 \). Since \( 1=1 \), the base case holds.
Inductive Step: Assume the statement is true for \( n=k \), i.e., \( 1 + 3 + \dots + (2k-1) = k^2 \).
We want to show it holds for \( n=k+1 \), i.e., \( 1 + 3 + \dots + (2k-1) + (2(k+1)-1) = (k+1)^2 \).
Starting from the LHS for \( k+1 \):
\( [1 + 3 + \dots + (2k-1)] + (2k+1) \)
Substitute the inductive hypothesis:
\( = k^2 + (2k+1) \)
\( = k^2 + 2k + 1 \)
\( = (k+1)^2 \)
This matches the RHS for \( n=k+1 \). Thus, by mathematical induction, the statement is true for all \( n \ge 1 \).
Problem 2: Prove that \( n^3 - n \) is divisible by 3 for all \( n \ge 1 \).
Show Solution
Base Case: For \( n=1 \), \( 1^3 - 1 = 0 \). Since 0 is divisible by 3, the base case holds.
Inductive Step: Assume \( k^3 - k \) is divisible by 3 for some \( k \ge 1 \). That is, \( k^3 - k = 3m \) for some integer \( m \).
We want to show \( (k+1)^3 - (k+1) \) is divisible by 3.
Expand the expression for \( k+1 \):
\( (k+1)^3 - (k+1) = (k^3 + 3k^2 + 3k + 1) - (k + 1) \)
\( = k^3 + 3k^2 + 3k + 1 - k - 1 \)
\( = (k^3 - k) + 3k^2 + 3k \)
By the inductive hypothesis, \( k^3 - k = 3m \). So:
\( = 3m + 3k^2 + 3k = 3(m + k^2 + k) \)
Since \( m + k^2 + k \) is an integer, the expression is divisible by 3.
Problem 3: Prove that \( 2^n \gt n \) for all \( n \ge 1 \).
Show Solution
Base Case: For \( n=1 \), \( 2^1 = 2 \) and \( 2 \gt 1 \). The base case holds.
Inductive Step: Assume \( 2^k \gt k \) for some \( k \ge 1 \).
We want to show \( 2^{k+1} \gt k+1 \).
Start with the LHS:
\( 2^{k+1} = 2 \cdot 2^k \)
By the inductive hypothesis, \( 2^k \gt k \), so:
\( 2 \cdot 2^k \gt 2k \)
We need to show \( 2k \ge k+1 \). This is true if \( k \ge 1 \).
Thus, \( 2^{k+1} \gt 2k \ge k+1 \), so \( 2^{k+1} \gt k+1 \).
Problem 4: Prove that \( \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \).
Show Solution
Base Case: For \( n=1 \), LHS = \( 1^2 = 1 \). RHS = \( \frac{1(2)(3)}{6} = 1 \). Base case holds.
Inductive Step: Assume \( \sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6} \).
We want to show \( \sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2(k+1)+1)}{6} = \frac{(k+1)(k+2)(2k+3)}{6} \).
LHS for \( k+1 \):
\( \sum_{i=1}^{k+1} i^2 = (\sum_{i=1}^k i^2) + (k+1)^2 \)
\( = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \)
\( = (k+1) [\frac{k(2k+1)}{6} + (k+1)] \)
\( = (k+1) [\frac{2k^2 + k + 6k + 6}{6}] \)
\( = \frac{k+1}{6} (2k^2 + 7k + 6) \)
Factor \( 2k^2 + 7k + 6 \): \( (2k+3)(k+2) \).
\( = \frac{(k+1)(k+2)(2k+3)}{6} \)
This matches the RHS.