Difficulty: Intermediate | Prerequisites: Summation notation, basic induction structure (base case, hypothesis, inductive step)
Mathematical induction is one of the most important proof techniques in discrete mathematics and computer science. This set of notes covers two flavours: proving a summation identity holds for all positive integers, and proving a divisibility property holds for all non-negative integers. Both follow the same three-part skeleton (base case, inductive hypothesis, inductive step) but the algebraic moves inside the inductive step differ. If you are shaky on the basic structure of an induction proof, review that first before diving into these worked examples.
To prove a summation formula by induction, you assume it holds for n = k, then show the (k+1) case follows by peeling off the last term and applying the hypothesis. For divisibility proofs, you rewrite the expression at n = k+1 to expose a factor of the expression at n = k (which you assumed is divisible), then show everything left over is also divisible.
Mathematical induction
A proof technique with three parts: verify a base case, assume the statement holds for an arbitrary value k (the inductive hypothesis), then prove it holds for k+1. Think of it as a domino chain: if the first domino falls and each domino knocks over the next, they all fall.
Base case
The starting value of n for which you directly verify the statement is true. This anchors the entire proof.
Inductive hypothesis (IH)
The assumption that the statement holds for some arbitrary but fixed value n = k. You treat this as a known fact inside the inductive step.
Inductive step
The argument that, given the IH, the statement must also hold for n = k+1. This is where the real algebra happens.
Divisibility notation: a | b
Means "a divides b," i.e. b = a·c for some integer c. In simple terms, b is a whole-number multiple of a.
Base case (n = 1):
LHS: 1·3¹ = 3
RHS: (3/4)[(2·1 − 1)·3¹ + 1] = (3/4)[3 + 1] = (3/4)(4) = 3
LHS = RHS. Base case holds.
Inductive hypothesis:
Assume for an arbitrary positive integer k that ∑ i·3ⁱ from i = 1 to k = (3/4)[(2k − 1)·3ᵏ + 1].
Inductive step (prove for n = k+1):
The sum to k+1 equals the sum to k, plus the new term:
∑ i·3ⁱ (to k+1) = ∑ i·3ⁱ (to k) + (k+1)·3ᵏ⁺¹
Apply the IH to the first part:
= (3/4)[(2k − 1)·3ᵏ + 1] + (k+1)·3ᵏ⁺¹
Expand and combine. The key algebraic steps:
= (3/4)(2k − 1)·3ᵏ + 3/4 + (k+1)·3ᵏ⁺¹
= (3/4)(2k − 1)·3ᵏ + (3/4)(k+1)·4·3ᵏ + 3/4 (rewrite (k+1)·3ᵏ⁺¹ = (k+1)·3·3ᵏ and find a common factor of 3/4)
After collecting terms with 3ᵏ:
= (3/4)[(2k − 1)·3ᵏ + 4(k+1)·3ᵏ + 1]
= (3/4)[(2k − 1 + 4k + 4)·3ᵏ + 1]
= (3/4)[(6k + 3)·3ᵏ + 1]
= (3/4)[3(2k + 1)·3ᵏ + 1]
= (3/4)[(2k + 1)·3ᵏ⁺¹ + 1]
This matches the formula with n = k+1, since 2(k+1) − 1 = 2k + 1.
Conclusion: By induction, the identity holds for all positive integers n.
Base case (n = 0):
9⁰ − 8(0) − 1 = 1 − 0 − 1 = 0.
64 | 0 is true (0 = 64·0). Base case holds.
Inductive hypothesis:
Assume for an arbitrary non-negative integer k that 64 | (9ᵏ − 8k − 1).
This means 9ᵏ − 8k − 1 = 64c for some integer c.
Equivalently: 9ᵏ = 64c + 8k + 1.
Inductive step (prove for n = k+1):
Evaluate 9ᵏ⁺¹ − 8(k+1) − 1:
= 9·9ᵏ − 8k − 8 − 1
= 9·9ᵏ − 8k − 9
Substitute the IH expression 9ᵏ = 64c + 8k + 1:
= 9(64c + 8k + 1) − 8k − 9
= 576c + 72k + 9 − 8k − 9
= 576c + 64k
= 64(9c + k)
Since c and k are integers, 9c + k is an integer, so 64 divides the expression.
Conclusion: By induction, 64 | (9ⁿ − 8n − 1) for all non-negative integers n.
Identity | Domain |
|---|---|
∑ i·3ⁱ (i = 1 to n) = (3/4)[(2n − 1)·3ⁿ + 1] | Positive integers n |
64 | (9ⁿ − 8n − 1) | Non-negative integers n |
Summation identities like the one in Proof 1 appear when analysing algorithms with geometrically growing work per level (think of certain divide-and-conquer recurrences). Divisibility results like Proof 2 connect to modular arithmetic, which underpins cryptography, hashing, and error-detection codes.
Students sometimes start the base case at n = 1 when the statement says "all non-negative integers" (which starts at n = 0). Always check the domain.
In the summation proof, a frequent error is adding the new term (k+1)·3ᵏ⁺¹ but forgetting to properly combine it with the IH expression under a common factor.
For the divisibility proof, students often try to show 64 | 9ᵏ⁺¹ directly rather than rewriting 9ᵏ⁺¹ in terms of 9ᵏ. The trick is always to expose the IH quantity inside the new expression.
Writing "assume true for all k" in ordinary induction is incorrect. You assume it for one arbitrary k, not all values up to k (that would be strong induction).
⚠️ Induction proofs are near-guaranteed exam questions. Know the skeleton cold: state the base case, state the IH with "for an arbitrary chosen [positive/non-negative] integer k," then prove for k+1.
⚠️ The algebra inside the inductive step is where most marks are lost. Show every line of working; do not skip steps.
⚠️ For divisibility proofs, you must explicitly state what the IH gives you (i.e. "there exists an integer c such that ...") and use that substitution. Examiners look for this.
⚠️ Pay careful attention to whether the domain is "positive integers" (n ≥ 1) or "non-negative integers" (n ≥ 0). Using the wrong base case loses marks.
True or False: In an induction proof for n ≥ 0, the base case should be n = 1.
Fill in the blank: In the inductive step, we assume the statement holds for n = k and prove it for n = ______.
True or False: If 64 | (9ᵏ − 8k − 1), then 9ᵏ = 64c + 8k + 1 for some integer c.
Fill in the blank: The key algebraic move in the summation induction is separating ∑ (to k+1) into ∑ (to k) + ______.
True or False: 64 | 0 is a true statement.
Answers: 1. False (base case is n = 0). 2. k + 1. 3. True. 4. The (k+1)th term. 5. True (0 = 64·0).
Q: In the proof that ∑ i·3ⁱ = (3/4)[(2n−1)·3ⁿ + 1], what does the inductive step reduce to showing?
A: That (3/4)[(2k−1)·3ᵏ + 1] + (k+1)·3ᵏ⁺¹ simplifies to (3/4)[(2(k+1)−1)·3ᵏ⁺¹ + 1]. The entire step is algebraic manipulation.
Q: Why do we rewrite 9ᵏ⁺¹ as 9·9ᵏ in the divisibility proof?
A: Because the IH gives us information about 9ᵏ (namely that 9ᵏ = 64c + 8k + 1). Writing 9ᵏ⁺¹ = 9·9ᵏ lets us substitute that expression directly.
Q: What would go wrong if you assumed the statement for all integers from 0 to k in an ordinary induction proof?
A: That is strong induction, not ordinary induction. In ordinary induction, you assume only that the statement holds for one specific value k. Using the wrong form is a logical error, even if it does not affect the algebra.
Q: Verify the base case for ∑ i·3ⁱ = (3/4)[(2n−1)·3ⁿ + 1] at n = 1.
A: LHS = 1·3 = 3. RHS = (3/4)[(2−1)·3 + 1] = (3/4)(4) = 3. They match.
These proofs connect to the summation evaluation techniques from earlier in the homework (you need closed forms to set up the induction target). The divisibility proof technique reappears whenever you study modular arithmetic or number theory. Strong induction, covered in the next set of notes, extends the method used here by allowing the hypothesis to cover all values up to k.
mathematical induction, proof by induction, base case, inductive hypothesis, inductive step, summation identity, divisibility proof, 64 divides, modular arithmetic, COT 3100, discrete mathematics, UCF, i times 3 to the i, 9 to the n minus 8n minus 1