Strong induction

WHY does strong induction exist?

WHAT is it?

HOW is it justified? (Derivation from first principles)

We do not just accept strong induction — we derive it from ordinary induction. That is the whole point of "derivation-from-scratch."

Formula Strong induction

$\iff$ ordinary induction Claim: If ordinary induction is valid, so is strong induction.

Setup. Suppose we have proved:

$P(n_0)$ , and
for every $n>n_0$ : $\big(P(k)\text{ for all } n_0\le k<n\big)\Rightarrow P(n)$ .

Define an auxiliary statement: $Q(n): \quad P(k)\ \text{holds for every } k \text{ with } n_0 \le k \le n.$ So $Q(n)$ says "everything up to and including $n$ is true."

Step 1 — base of $Q$ . $Q(n_0)$ means " $P(n_0)$ is true," which we assumed. ✅ Why this step? We must anchor the ordinary induction on $Q$ .

Step 2 — inductive step of $Q$ . Assume $Q(n)$ : $P(n_0),\dots,P(n)$ all true. This is exactly the strong hypothesis " $P(k)$ for all $k<n+1$ ", so by our assumed inductive step, $P(n+1)$ holds. Combined with $Q(n)$ we get $P(n_0),\dots,P(n+1)$ , i.e. $Q(n+1)$ . ✅ Why this step? We converted the "all-history" assumption into a single-predecessor assumption on $Q$ .

Conclusion. By ordinary induction, $Q(n)$ holds for all $n\ge n_0$ . Since $Q(n)$ contains $P(n)$ , $P(n)$ holds for all $n\ge n_0$ . $\blacksquare$

So strong induction is not a new axiom — it is ordinary induction applied to the "cumulative" statement $Q$ .

Worked Example 1 — Every integer $\ge 2$ is a product of primes

Worked example

Claim $P(n)$ : every integer $n\ge 2$ can be written as a product of primes.

Base: $P(2)$ : $2$ is prime, so it's a (one-factor) product of primes. ✅ Why? $2$ is the smallest case; nothing smaller exists to lean on.

Strong step: assume $P(k)$ for all $2\le k<n$ . Show $P(n)$ .

If $n$ is prime, done (it's its own product).
If $n$ is composite, $n=ab$ with $2\le a,b<n$ . Why this matters: both $a,b$ are below $n$ , so the strong hypothesis applies to both.
By hypothesis $a$ and $b$ are each products of primes; multiplying them, $n$ is a product of primes. ✅

Why ordinary induction fails here: $a$ and $b$ need not equal $n-1$ ; you cannot control which smaller number appears, so you need the whole history.

Worked Example 2 — A recurrence with two predecessors

Worked example

Define $a_1=1,\ a_2=3,\ a_n = 2a_{n-1} - a_{n-2}$ for $n\ge3$ . Prove $a_n = 2n-1$ .

Base: $a_1=1=2(1)-1$ ✅ and $a_2=3=2(2)-1$ ✅. Why two base cases? The recurrence reaches back two steps, so we must anchor two starting values or the step has nothing to stand on.

Strong step: assume $a_k=2k-1$ for all $k<n$ (in particular for $n-1$ and $n-2$ ). $a_n = 2a_{n-1}-a_{n-2} = 2(2(n-1)-1) - (2(n-2)-1).$ Why this step? Substitute the hypothesis for both needed predecessors. $= (4n-6) - (2n-5) = 2n-1.\ ✅$

Worked Example 3 — Postage stamps (chicken-nugget flavour)

Common mistakes (Steel-manned)

Flashcards

What extra information does strong induction assume compared to ordinary induction?

It assumes

P(k)

for all

k

with

n_0\le k<n

, not just

P(n-1)

Why can strong induction be derived from ordinary induction?

Apply ordinary induction to

Q(n)

= "

P(k)

true for all

k\le n

"; its single-step hypothesis equals the strong hypothesis.

How many base cases do you need if the inductive step uses

P(n-2)

At least two, so the step never references an undefined/unproven predecessor.

In the prime-factorisation proof, why is ordinary induction insufficient?

A composite

n=ab

has

a,b<n

but not necessarily

=n-1

; you need the whole history, not the immediate predecessor.

Is the strong induction hypothesis allowed to include

k=n

No — strictly

k<n

;

P(n)

is what you must prove.

Are strong and ordinary induction logically equivalent?

Yes; each implies the other.

Recall Feynman: explain to a 12-year-old

Imagine climbing a staircase. Normal induction: to reach a step you only need to be standing on the step just below it. But some steps are big — to reach step 10 you might need to push off from steps 6 and 8. Strong induction says: "I get to stand on every step below me at once, then jump up." As long as the bottom few steps are solid to start, you can reach the top of the infinite staircase.

Connections

Mathematical Induction (ordinary) — the parent principle strong induction is derived from.
Well-Ordering Principle — equivalent formulation; often used to prove strong induction directly.
Recurrence Relations — multi-term recurrences are the natural home of strong induction.
Prime Factorisation — classic application (Fundamental Theorem of Arithmetic).
Sequences & Series — proving closed forms of recursively defined sequences.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, normal induction ek domino chain jaisa hai: har domino sirf apne theek pehle wale domino ko girta dekh kar khud girta hai. Yaani $P(n)$ prove karne ke liye tumhe sirf $P(n-1)$ chahiye. Lekin kabhi-kabhi ek case ko prove karne ke liye sirf ek pichhla case kaafi nahi hota — tumhe bahut saare pichhle cases ki zaroorat padti hai. Jaise prime factorisation mein $n=ab$ , yahaan $a$ aur $b$ dono $n$ se chhote hain, par zaroori nahi ki $n-1$ ke barabar hon. Isi liye strong induction aati hai: tum maan lete ho ki $n$ se chhote saare $k$ ke liye $P(k)$ sach hai, phir $P(n)$ prove karte ho.

Sabse important baat: strong induction koi naya jaadu nahi hai — hum ise ordinary induction se hi derive kar sakte hain. Trick yeh hai ki ek naya statement $Q(n)$ banao jo kahe " $n$ tak sab kuch sach hai." Tab $Q$ pe normal induction lagao, aur strong hypothesis apne aap $Q$ ke single-step hypothesis ban jaata hai. Isliye dono logically equivalent hain, bas strong wala likhne mein convenient hota hai.

Ek practical tip jo exams mein marks bachati hai: agar recurrence ya step do (ya zyada) steps pichhe jaata hai — jaise $a_n=2a_{n-1}-a_{n-2}$ — to tumhe utne hi base cases dene padenge. Sirf ek base case doge to $P(3)$ prove karte waqt $a_1$ hoga par $a_2$ ... ya definition tootegi. So rule yaad rakho: "jitna peechhe step jaata hai, utne base cases do." Yeh chhoti si baat bahut logo ko marwa deti hai.

WHY does strong induction exist?

WHAT is it?

HOW is it justified? (Derivation from first principles)

Worked Example 1 — Every integer $\ge 2$ is a product of primes

Worked Example 2 — A recurrence with two predecessors

Worked Example 3 — Postage stamps (chicken-nugget flavour)

Common mistakes (Steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Sequences & Series

Connections