MAT2033 · Week 3 · proof techniques and mathematical induction

Mathematical induction and strong induction

The induction skeleton for sum formulas, divisibility and inequalities; strong induction for stamp problems and recursively defined sequences. An almost certain 20-point question on the midterm.

mathematical inductionbasis stepinductive stepinductive hypothesisstrong inductionwell-ordering principledivisibilityinequalityrecursively defined sequence

Mathematical induction is the standard way to prove claims that start with “for every positive integer $n$ …”. It is an almost certain midterm question: a sum formula, a divisibility claim or an inequality. The good news: the skeleton is always the same. If you memorize the skeleton word for word, you only have to put the algebra inside it. Even the basis step alone earns marks.

Golden rules:

Two steps: basis and inductive step. Both are required.
The basis is the $n_0$ where the claim starts. If it says " $n \ge 4$ ", then $n = 4$ .
Always use the hypothesis. If you are not using it, you are not doing induction.
Write $P(k+1)$ explicitly first. Don’t set out without knowing where you are going.
Start from one side. Take the left side of $P(k+1)$ and reach the right side. Don’t work on both sides together.

The idea: dominoes

To knock down an infinite row of dominoes, two things are enough:

Knock down the first one (basis step): $P(n_0)$ is true.
Show that if any domino falls, it knocks down the next one (inductive step): $P(k) \to P(k+1)$ for every $k \ge n_0$ .

Formally:

$\big(P(n_0) \land \forall k \ge n_0\,(P(k) \to P(k+1))\big) \to \forall n \ge n_0\, P(n)$

In the inductive step you say “let $P(k)$ be true”. This is not assuming what you want to prove: you are only saying “if a domino falls”, you are not claiming that it falls. This assumption is called the inductive hypothesis (IH).

The skeleton (you will write it in English on the exam)

Let P(n) be the statement "...". We prove P(n) for all integers n ≥ n0.

Basis step. For n = n0: LHS = ..., RHS = .... They are equal, so P(n0) is true.

Inductive step. Assume P(k) is true for some arbitrary integer k ≥ n0, i.e.
  [write P(k)]                                    (inductive hypothesis)
We must show P(k+1):
  [write P(k+1)]
  [algebra: find the left side of P(k) in the left side of P(k+1), replace it using the IH]
So P(k+1) is true.

Conclusion. By the principle of mathematical induction, P(n) is true
for all integers n ≥ n0.  ∎

Type 1: Sum formula

Example. Prove that $2 + 5 + 8 + \dots + (3n - 1) = \dfrac{n(3n+1)}{2}$ for all $n \ge 1$ .

Basis $n = 1$ : LHS $= 3 \cdot 1 - 1 = 2$ . RHS $= \tfrac{1 \cdot 4}{2} = 2$ . Equal.

Inductive step. IH: $2 + 5 + \dots + (3k - 1) = \dfrac{k(3k+1)}{2}$ .

Goal $P(k+1)$ : $2 + 5 + \dots + (3k - 1) + (3k + 2) = \dfrac{(k+1)(3k+4)}{2}$ .

$\underbrace{2 + 5 + \dots + (3k-1)}_{\text{IH}} + (3k+2) = \frac{k(3k+1)}{2} + (3k+2) = \frac{3k^2 + k + 6k + 4}{2} = \frac{3k^2 + 7k + 4}{2} = \frac{(k+1)(3k+4)}{2}.$

This is exactly the right side of $P(k+1)$ . By induction, the formula holds for all $n \ge 1$ . ∎

TIP · Look at the goal when factoring. If you don’t know how to factor $3k^2 + 7k + 4$ , expand the $(k+1)(3k+4)$ in the goal: $3k^2 + 7k + 4$ . If it matches, you are done. The goal tells you the answer.

Type 2: Divisibility

The trick: expand $f(k+1)$ and create $f(k)$ inside it. Show that the rest is also a multiple of the divisor.

Example. Prove that $3 \mid 4^n + 5$ for all $n \ge 1$ .

Basis $n = 1$ : $4 + 5 = 9 = 3 \cdot 3$ .

IH: $4^k + 5 = 3m$ for some integer $m$ .

$4^{k+1} + 5 = 4 \cdot 4^k + 5 = 4(4^k + 5) - 20 + 5 = 4(4^k + 5) - 15 = 4 \cdot 3m - 15 = 3(4m - 5).$

$4m - 5$ is an integer, so $3 \mid 4^{k+1} + 5$ . By induction ∎.

The move here: when you see $4 \cdot 4^k$ , write $4(4^k + 5)$ and subtract the extra $20$ you added. Almost all divisibility questions are solved with this move.

Type 3: Inequality

Start from the hypothesis, then close the gap with a simple fact that comes from $k \ge n_0$ .

Example. Prove that $2^n > n^2$ for all integers $n \ge 5$ .

Basis $n = 5$ : $32 > 25$ .

IH: $2^k > k^2$ for some $k \ge 5$ . Then

$2^{k+1} = 2 \cdot 2^k > 2k^2.$

Now I need to show that $2k^2 \ge (k+1)^2$ . $2k^2 - (k+1)^2 = k^2 - 2k - 1$ . For $k \ge 3$ , $k^2 - 2k - 1 = k(k-2) - 1 \ge 3 - 1 > 0$ . So it is also true for $k \ge 5$ . Chain:

$2^{k+1} > 2k^2 \ge (k+1)^2.$

So $P(k+1)$ holds. By induction ∎.

PITFALL · Losing the direction of the inequality. Every link in the chain must point the same way ( $>$ and $\ge$ can be mixed, and the result is $>$ ). If one link comes out as $\le$ , the chain breaks. Write in one sentence why each intermediate inequality is true.

Strong induction

Sometimes $P(k)$ alone is not enough to show $P(k+1)$ , and you need earlier values as well. In strong induction the hypothesis is broader:

$\text{IH: } P(n_0), P(n_0+1), \dots, P(k) \text{ all true} \quad\Rightarrow\quad P(k+1).$

Logically it has the same power as ordinary induction; it only makes the writing easier. Both are based on the well-ordering principle: every nonempty subset of the positive integers has a least element.

Example: stamp problem

Theorem. Every amount of postage of 12 cents or more can be formed using 4-cent and 5-cent stamps.

Basis. 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5.
Inductive step. Let k ≥ 15 and assume every amount j with 12 ≤ j ≤ k
can be formed (strong IH). Then k + 1 = (k − 3) + 4, and
12 ≤ k − 3 ≤ k, so k − 3 can be formed. Add one 4-cent stamp.
Hence k + 1 can be formed. By strong induction, every n ≥ 12 works.  ∎

Why four basis cases? The step goes back by 4. For $k + 1 = 16$ we look at $12$ ; but stepping back from $13, 14, 15$ would take us below 12, so we have to show them separately. Below 12, the amounts 1, 2, 3, 6, 7, 11 cannot be formed; that is why the claim starts at 12.

Example: prime factorization

Theorem. Every integer $n \ge 2$ is a prime or a product of primes.

Basis $n = 2$ : 2 is prime. Step: let it be true for all $j$ with $2 \le j \le k$ . If $k + 1$ is prime, we are done. If not, $k + 1 = ab$ with $2 \le a, b \le k$ . By the IH, $a$ and $b$ are products of primes, so $ab$ is too. ∎ (Example: $360 = 2^3 \cdot 3^2 \cdot 5$ .) Here we do not know what $a$ and $b$ are, only that they are smaller than $k$ . Ordinary induction ( $P(k) \to P(k+1)$ ) does not work here; strong induction exists for exactly this.

Why the basis is required: a fake proof

Claim: ” $n^2 + n$ is odd for all $n \ge 1$ .” Inductive step: let $k^2 + k$ be odd. $(k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)$ , odd + even = odd. The step is flawless! But for $n = 1$ , $1 + 1 = 2$ is even. The basis collapses and the claim is false from the start. The dominoes knock each other down, but the first one never falls.

Common mistakes

Wrong idea	The truth
Skipping the basis or saying “obvious”	Always compute both sides separately with the number
Doing the basis at $n = 1$ when the claim is $n \ge 5$	The basis must be $n_0$
IH: “Assume $P(n)$ is true for all $n$ ”	That is what you want to prove. Write “for some arbitrary $k$ ”
Working on both sides of $P(k+1)$ together and reaching $0 = 0$	Start from one side, arrive at the other
Never using the hypothesis	If you don’t use it, it is not induction
Writing the last term of $P(k+1)$ wrongly	Replace $n$ by $k+1$ in the formula: $3(k+1) - 1 = 3k + 2$
A single basis case in strong induction	As many basis cases as the step goes back
Forgetting the closing sentence	“By the principle of mathematical induction …” is part of your marks

Test yourself

Exam-style questions. Solve them on paper first, then reveal the answer.

Question 1easy

You want to prove $2^n > n^2$ for all integers $n \ge 5$ by induction. State the basis step and check it.

Show answer

n = 5: 2⁵ = 32 > 25 = 5²

The basis is where the claim starts: $n_0 = 5$ . Not $n = 1$ . $2^5 = 32$ , $5^2 = 25$ , $32 > 25$ is true. (The claim is false for $n = 2, 3, 4$ : $4 = 4$ , $8 < 9$ , $16 = 16$ . That is why it starts at 5.)

Question 2easy

Let $P(n)$ be $1 + 4 + 7 + \dots + (3n - 2) = \dfrac{n(3n - 1)}{2}$ . Write $P(k+1)$ explicitly.

Show answer

1 + 4 + ... + (3k − 2) + (3k + 1) = (k + 1)(3k + 2)/2

Replace every $n$ in the formula with $k+1$ . The last term is $3(k+1) - 2 = 3k + 1$ . The right side is $\tfrac{(k+1)(3(k+1) - 1)}{2} = \tfrac{(k+1)(3k+2)}{2}$ . Writing the term before the last one ( $3k - 2$ ) on the left side as well shows where you will use the hypothesis.

Question 3medium

Prove by induction that $\displaystyle\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$ for all $n \ge 1$ .

Show answer

Basis 1/2 = 1/2; step: k/(k+1) + 1/((k+1)(k+2)) = (k+1)/(k+2).

Basis $n = 1$ : left $\tfrac{1}{1 \cdot 2} = \tfrac12$ , right $\tfrac{1}{2}$ . Equal.
Inductive step: let $\sum_{i=1}^{k} \tfrac{1}{i(i+1)} = \tfrac{k}{k+1}$ (IH). Then $\sum_{i=1}^{k+1} \frac{1}{i(i+1)} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}.$ This is exactly $P(k+1)$ . By induction, $P(n)$ holds for all $n \ge 1$ . ∎ The key: $k^2 + 2k + 1 = (k+1)^2$ .

Question 4hard

Prove by induction that $6 \mid n^3 + 5n$ for every positive integer $n$ .

Show answer

(k+1)³ + 5(k+1) = (k³ + 5k) + 3k(k+1) + 6, and 6 divides each part.

Basis $n = 1$ : $1 + 5 = 6 = 6 \cdot 1$ .
IH: $k^3 + 5k = 6m$ . Expand: $(k+1)^3 + 5(k+1) = k^3 + 3k^2 + 3k + 1 + 5k + 5 = (k^3 + 5k) + 3k^2 + 3k + 6 = 6m + 3k(k+1) + 6$ . $k(k+1)$ is the product of two consecutive numbers, so it is even: $k(k+1) = 2t$ . Then $3k(k+1) = 6t$ . The total is $6(m + t + 1)$ , divisible by 6. By induction ∎. Pitfall: writing that $3k(k+1)$ is divisible by 6 without a reason.

Question 5medium

Prove by induction that $5 \mid 6^n - 1$ for all integers $n \ge 0$ .

Show answer

6^(k+1) − 1 = 6(6^k − 1) + 5

Basis $n = 0$ : $6^0 - 1 = 0 = 5 \cdot 0$ . 0 is divisible by every number.
IH: $6^k - 1 = 5m$ . Then $6^{k+1} - 1 = 6 \cdot 6^k - 6 + 5 = 6(6^k - 1) + 5 = 6 \cdot 5m + 5 = 5(6m + 1)$ . $6m + 1$ is an integer, so $5 \mid 6^{k+1} - 1$ . ∎ The trick: expand $6^{k+1}$ and create the old expression ( $6^k - 1$ ) inside it.

Question 6medium

Prove that $n! > 2^n$ for every integer $n \ge 4$ .

Show answer

Basis 24 > 16; step: (k+1)! = (k+1)k! > (k+1)2^k ≥ 2·2^k = 2^(k+1).

Basis $n = 4$ : $4! = 24 > 16 = 2^4$ .
IH: $k! > 2^k$ for some $k \ge 4$ . Then $(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k$ . Since $k \ge 4$ , $k + 1 \ge 2$ , so $(k+1) \cdot 2^k \ge 2 \cdot 2^k = 2^{k+1}$ . Chain: $(k+1)! > 2^{k+1}$ . ∎ In an inequality you may make things "a bit smaller/bigger" as long as the direction is not broken and you state the fact you used ( $k+1 \ge 2$ ).

Question 7hard

Prove that $\displaystyle\sum_{i=1}^{n} i \cdot 2^i = (n-1)2^{n+1} + 2$ for all $n \ge 1$ .

Show answer

Step: (k−1)2^(k+1) + 2 + (k+1)2^(k+1) = 2k·2^(k+1) + 2 = k·2^(k+2) + 2.

Basis $n = 1$ : left $1 \cdot 2 = 2$ , right $0 \cdot 4 + 2 = 2$ .
IH: $\sum_{i=1}^{k} i 2^i = (k-1)2^{k+1} + 2$ . The new term is $(k+1)2^{k+1}$ . $\sum_{i=1}^{k+1} i 2^i = (k-1)2^{k+1} + 2 + (k+1)2^{k+1} = 2k \cdot 2^{k+1} + 2 = k \cdot 2^{k+2} + 2.$ The goal is $((k+1) - 1)2^{(k+1)+1} + 2 = k \cdot 2^{k+2} + 2$ . The same. ∎ Taking the common factor $2^{k+1}$ out finishes the job.

Question 8easy

A student "proves" that $n^2 + n$ is odd for all $n \ge 1$ : "Assume $k^2 + k$ is odd. Then $(k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)$ is odd + even = odd." What is wrong?

Show answer

The basis step fails: for n = 1, 1² + 1 = 2 is even.

The inductive step is actually correct: odd + even = odd. But the first domino in the chain never falls: for $n = 1$ , $2$ is even. Without a basis, the inductive step proves nothing. In fact $n^2 + n$ is always even.

Question 9medium

Which positive integer amounts of postage cannot be formed using only 3-cent and 7-cent stamps? Explain why strong induction shows every amount $n \ge 12$ can be formed.

Show answer

1, 2, 4, 5, 8, 11

Try small values: 3, 6, 7, 9, 10 work; 1, 2, 4, 5, 8, 11 do not. Basis: $12 = 4 \cdot 3$ , $13 = 2 \cdot 3 + 7$ , $14 = 2 \cdot 7$ . Inductive step: if $k \ge 14$ and every $j$ with $12 \le j \le k$ can be formed, then $k + 1 = (k - 2) + 3$ and $k - 2 \ge 12$ ; add one 3-cent stamp to the stamps used for $k-2$ . You need three consecutive basis cases, because we step back by 3.

Question 10hard

Let $a_0 = 2$ , $a_1 = 1$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$ . Prove by strong induction that $a_n = 2^n + (-1)^n$ , and find $a_5$ .

Show answer

a_5 = 31

Basis: $a_0 = 2 = 1 + 1$ , $a_1 = 1 = 2 - 1$ . Two basis cases are needed, because the rule looks at the two previous terms.
Step: let $k \ge 1$ and $a_j = 2^j + (-1)^j$ for all $j \le k$ (strong IH). Then $a_{k+1} = a_k + 2a_{k-1} = 2^k + (-1)^k + 2 \cdot 2^{k-1} + 2(-1)^{k-1} = 2^{k+1} + (-1)^{k-1}(-1 + 2) = 2^{k+1} + (-1)^{k+1}$ .
( $(-1)^k = -(-1)^{k-1}$ and $(-1)^{k-1} = (-1)^{k+1}$ .) ∎ $a_5 = 32 - 1 = 31$ . Check: 2, 1, 5, 7, 17, 31.

Question 11hard

Prove that $1 + \dfrac14 + \dfrac19 + \dots + \dfrac{1}{n^2} \le 2 - \dfrac1n$ for all $n \ge 1$ .

Show answer

Step reduces to 1/(k+1)² ≤ 1/k − 1/(k+1) = 1/(k(k+1)), which is true.

Basis $n = 1$ : $1 \le 2 - 1 = 1$ . True.
IH: $\sum_{i=1}^{k} \tfrac{1}{i^2} \le 2 - \tfrac1k$ . Then $\sum_{i=1}^{k+1} \tfrac{1}{i^2} \le 2 - \tfrac1k + \tfrac{1}{(k+1)^2}$ . To show this is $\le 2 - \tfrac{1}{k+1}$ it is enough to show $\tfrac{1}{(k+1)^2} \le \tfrac1k - \tfrac{1}{k+1} = \tfrac{1}{k(k+1)}$ ; this is true because $k(k+1) \le (k+1)^2$ . ∎ In inequality inductions, work backwards by asking "what do I need to reach the goal?", then write it forwards.

Question 12medium

To prove that every postage of $n \ge 12$ cents can be formed with 4-cent and 5-cent stamps using strong induction and the step " $k+1 = (k-3) + 4$ ", how many basis cases are needed?

Show answer

4 (n = 12, 13, 14, 15)

The step goes back by 4: we obtain $k + 1$ from $k - 3$ . For $k - 3 \ge 12$ we need $k + 1 \ge 16$ . So you must show 12, 13, 14, 15 separately: $12 = 3 \cdot 4$ , $13 = 2 \cdot 4 + 5$ , $14 = 4 + 2 \cdot 5$ , $15 = 3 \cdot 5$ .

Verification: Every sum formula was checked for n = 1..80 with integers/BigInt, divisibility for n ≤ 500, inequalities for n ≤ 200 (fractions with exact fraction arithmetic), stamp problems by trying all combinations, and the recursive sequence by iterating 60 terms in node (verify/MAT2033/03.mjs).

Review card

SKELETON: Let P(n): "...". Basis: n=n0, LHS=..., RHS=..., equal. Inductive step: Assume P(k) for arbitrary k≥n0 (IH). Show P(k+1). Conclusion: By mathematical induction, P(n) holds for all n≥n0. ∎ Take n0 from the claim: if "n≥4" the basis is n=4, if "n≥0" it is n=0. SUM: LHS(k+1) = LHS(k) + new term → plug in IH → factor out the common factor DIVISIBILITY: write f(k)=dm; expand f(k+1), create f(k) inside it, the rest is a multiple of d 6^(k+1)−1 = 6(6^k−1)+5 4^(k+1)+5 = 4(4^k+5)−15 INEQUALITY: start from the IH, close with a small fact from k≥n0 (k+1≥2, 2k+1≤k² ...) k(k+1) is always even → 3k(k+1) is a multiple of 6 STRONG: assume P(n0),...,P(k) all → P(k+1) as many basis cases as the step goes back (stamps 4-5: 12,13,14,15) if a_n looks at the two previous terms, two basis cases No basis, no proof (the n²+n odd "proof" collapses at the basis)