Solutions — Introduction to Mathematical Induction
-
Q1 — The Four Steps
Step 1 — Base case: Verify the statement is true for the starting value (usually n = 1). This provides the first “domino” that falls — without it, the chain has no beginning.
Step 2 — Inductive hypothesis: Assume the statement is true for some arbitrary integer k ≥ 1. This is a working assumption only; you have not yet proved it holds for every k.
Step 3 — Inductive step: Using the assumption from Step 2, prove algebraically that the statement must also be true for n = k + 1. This establishes the implication P(k) ⇒ P(k+1), showing that each fallen domino knocks over the next.
Step 4 — Conclusion: Since the base case holds and the implication P(k) ⇒ P(k+1) has been proved for all k ≥ 1, by the principle of mathematical induction the statement is true for all integers n ≥ 1.
-
Q2 — Base Case Verification
The claim is: 1 + 3 + 5 + … + (2n − 1) = n².
When n = 1, the LHS contains only the single term 2(1) − 1 = 1.
LHS = 1
RHS = 1² = 1
LHS = RHS ✓ The base case holds.
-
Q3 — Writing P(k) and P(k+1)
The claim is: 1 + 2 + 3 + … + n = n(n+1)/2.
P(k): 1 + 2 + 3 + … + k = k(k+1)/2
P(k+1): 1 + 2 + 3 + … + k + (k+1) = (k+1)(k+2)/2
In P(k+1), every occurrence of n is replaced by k+1. The LHS includes one additional term (k+1) beyond the sum to k, and the RHS has k+1 substituted for n, giving (k+1)((k+1)+1)/2 = (k+1)(k+2)/2.
-
Q4 — Prove the Triangular Number Formula
Claim: 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.
Step 1 — Base case (n = 1):
LHS = 1 RHS = 1(2)/2 = 1 LHS = RHS ✓
Step 2 — Inductive hypothesis:
Assume 1 + 2 + … + k = k(k+1)/2 for some k ≥ 1.
Step 3 — Inductive step: Prove that 1 + 2 + … + (k+1) = (k+1)(k+2)/2.
LHS = 1 + 2 + … + k + (k+1)
= k(k+1)/2 + (k+1) [by the inductive hypothesis]
= (k+1)[k/2 + 1] [factor out (k+1)]
= (k+1)(k + 2)/2 [= RHS for n = k+1] ✓
Step 4 — Conclusion:
Since P(1) is true, and P(k) ⇒ P(k+1) for all k ≥ 1, by the principle of mathematical induction, 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.
-
Q5 — Sum of Even Numbers
Claim: 2 + 4 + 6 + … + 2n = n(n+1) for all n ≥ 1.
Step 1 — Base case (n = 1):
LHS = 2 RHS = 1(2) = 2 LHS = RHS ✓
Step 2 — Inductive hypothesis:
Assume 2 + 4 + … + 2k = k(k+1) for some k ≥ 1.
Step 3 — Inductive step: Prove that 2 + 4 + … + 2(k+1) = (k+1)(k+2).
LHS = 2 + 4 + … + 2k + 2(k+1)
= k(k+1) + 2(k+1) [by the inductive hypothesis]
= (k+1)(k + 2) [factor out (k+1)]
= (k+1)((k+1)+1) [= RHS for n = k+1] ✓
Step 4 — Conclusion:
By the principle of mathematical induction, 2 + 4 + 6 + … + 2n = n(n+1) for all n ≥ 1.
-
Q6 — Sum of Odd Numbers
Claim: 1 + 3 + 5 + … + (2n − 1) = n² for all n ≥ 1.
Step 1 — Base case (n = 1):
LHS = 2(1) − 1 = 1 RHS = 1² = 1 LHS = RHS ✓
Step 2 — Inductive hypothesis:
Assume 1 + 3 + … + (2k − 1) = k² for some k ≥ 1.
Step 3 — Inductive step: Prove that 1 + 3 + … + (2(k+1) − 1) = (k+1)².
Note: the next odd number after (2k − 1) is 2k + 1 = 2(k+1) − 1.
LHS = 1 + 3 + … + (2k − 1) + (2k + 1)
= k² + (2k + 1) [by the inductive hypothesis]
= (k + 1)² [since k² + 2k + 1 = (k+1)²] ✓
Step 4 — Conclusion:
By the principle of mathematical induction, 1 + 3 + 5 + … + (2n − 1) = n² for all n ≥ 1.
-
Q7 — Sum of Squares
Claim: 1² + 2² + 3² + … + n² = n(n+1)(2n+1)/6 for all n ≥ 1.
Step 1 — Base case (n = 1):
LHS = 1 RHS = 1(2)(3)/6 = 6/6 = 1 LHS = RHS ✓
Step 2 — Inductive hypothesis:
Assume 1² + 2² + … + k² = k(k+1)(2k+1)/6 for some k ≥ 1.
Step 3 — Inductive step: Prove the sum = (k+1)(k+2)(2k+3)/6 for n = k+1.
LHS = 1² + 2² + … + k² + (k+1)²
= k(k+1)(2k+1)/6 + (k+1)² [by the inductive hypothesis]
= (k+1)[k(2k+1)/6 + (k+1)] [factor out (k+1)]
= (k+1)[(2k² + k + 6k + 6)/6]
= (k+1)(2k² + 7k + 6)/6
= (k+1)(k+2)(2k+3)/6 [since 2k²+7k+6 = (k+2)(2k+3)] ✓
This equals (k+1)((k+1)+1)(2(k+1)+1)/6 = RHS for n = k+1.
Step 4 — Conclusion:
By the principle of mathematical induction, 1² + 2² + … + n² = n(n+1)(2n+1)/6 for all n ≥ 1.
-
Q8 — Spot the Error
The error is that the student treated “I proved P(k)” as meaning P(k) is true for every k — which has not been established at this point in the proof. In the inductive step, P(k) is only an assumption, not a proved fact.
Furthermore, the student did not perform any algebraic manipulation connecting P(k) to P(k+1). Simply stating “therefore P(k+1) is true” without derivation is not a proof — it is circular reasoning. The inductive step requires you to:
- Write down what P(k+1) says explicitly.
- Start from the LHS for n = k+1.
- Isolate the sum to k and replace it using the inductive hypothesis.
- Simplify algebraically until the RHS for n = k+1 is obtained.
Only then has P(k) ⇒ P(k+1) been validly established.
-
Q9 — Sum of Odd Numbers (Verify then Prove)
Part (a) — Verification:
n = 1: Sum = 1 1² = 1 ✓
n = 2: Sum = 1 + 3 = 4 2² = 4 ✓
n = 3: Sum = 1 + 3 + 5 = 9 3² = 9 ✓
n = 4: Sum = 1 + 3 + 5 + 7 = 16 4² = 16 ✓
Part (b) — Proof by induction:
Let P(n): 1 + 3 + 5 + … + (2n − 1) = n².
Step 1 — Base case (n = 1): LHS = 1, RHS = 1² = 1 ✓
Step 2 — Inductive hypothesis: Assume 1 + 3 + … + (2k − 1) = k² for some k ≥ 1.
Step 3 — Inductive step: The (k+1)th odd number is 2(k+1) − 1 = 2k + 1.
LHS = [1 + 3 + … + (2k − 1)] + (2k + 1)
= k² + (2k + 1) [by the inductive hypothesis]
= (k + 1)² [= RHS for n = k+1] ✓
Step 4 — Conclusion: By the principle of mathematical induction, the sum of the first n odd numbers equals n² for all n ≥ 1.
-
Q10 — n² + n is Always Even
Part (a) — Verification:
n = 1: 1 + 1 = 2 (even) ✓
n = 2: 4 + 2 = 6 (even) ✓
n = 3: 9 + 3 = 12 (even) ✓
Part (b) — Proof by induction:
Let P(n): n² + n is even, i.e. n² + n = 2m for some integer m.
Step 1 — Base case (n = 1): 1² + 1 = 2 = 2(1), which is even ✓
Step 2 — Inductive hypothesis: Assume k² + k = 2m for some integer m, where k ≥ 1.
Step 3 — Inductive step: Show (k+1)² + (k+1) is even.
(k+1)² + (k+1) = k² + 2k + 1 + k + 1
= (k² + k) + 2k + 2
= 2m + 2(k + 1) [by the inductive hypothesis]
= 2(m + k + 1)
Since m + k + 1 is an integer, (k+1)² + (k+1) is even ✓
Step 4 — Conclusion: By the principle of mathematical induction, n² + n is even for all n ≥ 1.