Strong induction: Question bank — Maths deep dive

True or false — justify

Strong induction can prove statements that ordinary induction cannot.

False — they are logically equivalent; we derived strong induction from ordinary induction applied to the cumulative statement

Q (n)

. It is a convenience, never extra power.

If the inductive step only ever uses

P (n - 1)

, you must still use strong induction.

False — reaching back exactly one step is ordinary induction; the strong hypothesis is just unused overkill, so plain induction suffices.

The strong induction hypothesis includes

P (n)

itself.

False — the hypothesis is strictly

P (k)

for

n_{0} \leq k < n

. Assuming

P (n)

to prove

P (n)

would be circular.

Every strong-induction proof needs at least two base cases.

False — the prime-factorisation proof needs only

P (2)

; the number of base cases depends on how far the step reaches back, not on being "strong".

"Assume

P (k)

for all

k < n

" and "assume

P (n - 1)

" give the same proving power.

False — the first hands you the entire history so you can invoke any smaller case (like

a, b

n = ab

), which the single-predecessor form cannot reach.

A statement proven by strong induction for all

n \geq 12

says nothing about

n = 11

True — the base zone begins at

n_{0} = 12

; the claim is simply not asserted below it, and there is no chain reaching

11

Strong induction and the Well-Ordering Principle can each be used to prove the other.

True — they are equivalent formulations; see Well-Ordering Principle. You may prove strong induction directly by taking a least counterexample.

If you forget one base case, the proof might still be complete by luck.

False — a missing base leaves a value the step can never reach validly, so the logical chain has a permanent gap even if the formula happens to hold there.

Spot the error

"Base:

a_{1} = 1

. Step: assume

a_{n - 1} = 2 n - 3

; then

a_{n} = 2 a_{n - 1} - a_{n - 2} = 2 n - 1

." Find the flaw.

The step uses

a_{n - 2}

but only one base case (

a_{1}

) was given; for

n = 3

the term

a_{n - 2} = a_{1}

is fine, but

a_{2}

was never established as a base, so the chain for

n = 3

has no valid

a_{2}

. Two bases are required.

"To factor

n

, assume

P (k)

for all

k < n

, write

n = ab

, done — no base case needed." Error?

The base case

P (2)

is missing; without it the smallest cases have nothing beneath them and the whole tower is unfounded, even though the step itself is correct.

"Strong step for stamps: for

n \geq 12

assume the claim for all

k < n

; then

n - 4 \geq 12

." Error?

For

n = 13, 14, 15

the value

n - 4

9, 10, 11

, which is below

12

and not payable — so the step only works for

n \geq 16

, and

12

–

15

must be handled as base cases.

"Assume

P (k)

for all

k \leq n

, then prove

P (n)

." Error?

The hypothesis illegally includes

k = n

, i.e. it assumes exactly what must be proven. The correct bound is

k < n

"We proved

Q (n)

by ordinary induction, where

Q (n)

means

P (n)

only." Error?

Q (n)

must mean "

P (k)

for all

k \leq n

" (cumulative); if it meant only

P (n)

, its single-step hypothesis would be just

P (n)

and would not deliver the full history the strong step needs.

"Base cases

12, 13, 14, 15

all check out, so the claim holds for every

n \geq 12

." Complete?

Not yet — bases alone prove only those four values; you still need the inductive step showing

n

follows from

n - 4

to cover all larger

n

Why questions

Why does the prime-factorisation proof require the full history rather than just

P (n - 1)

A composite

n = ab

splits into

a, b < n

but neither need equal

n - 1

; you cannot predict which smaller values appear, so you must have them all available.

Why do we introduce the auxiliary statement

Q (n)

when justifying strong induction?

Q (n) =

P (k)

holds for all

k \leq n

" converts the many-predecessor assumption into a single-predecessor one, letting ordinary induction do the work.

Why must the number of base cases match how far the step reaches back?

If the step invokes

P (n - 2)

, the smallest

n

where the step fires would reference a value below the base — undefined or unproven — unless that value is a base case too.

Why is calling strong induction "more powerful" a category error?

Power is about which theorems are provable, and both prove exactly the same set; strong induction only changes convenience of expression, not reach.

Why can a two-term recurrence like

a_{n} = 2 a_{n - 1} - a_{n - 2}

not be handled cleanly by ordinary induction?

Ordinary induction gives only

P (n - 1)

, but the recurrence also needs

P (n - 2)

; without the extra predecessor the substitution in the step is impossible. See Recurrence Relations.

Why does anchoring induction on

Q

(not

P

) make strong induction "not a new axiom"?

Because the entire justification stays inside ordinary induction — strong induction is a theorem about ordinary induction, so no new assumption is added.

Edge cases

What happens if

n_{0}

is not the true smallest case, e.g. you start at

n_{0} = 2

but the step needs

P (0)

The step would reference values below your base zone that were never established, so the proof is invalid; the base must cover everything the step can reach.

Can strong induction start with zero explicit base cases if the step covers the smallest value trivially?

Only if the inductive step genuinely proves the smallest case with an empty hypothesis (vacuously); otherwise the smallest case is unsupported and you need at least one base.

For the stamp claim, why exactly four base cases and not three or five?

The step subtracts

4

, so residues

12, 13, 14, 15 (mod 4)

each need a direct anchor to land inside the base zone; three would leave one residue class unreachable, five is redundant.

Is a single base case ever wrong for a step reaching back one?

No — one-step-back needs exactly one base; adding extras is harmless but unnecessary. The danger is too few, never too many.

What does the strong hypothesis reduce to for the very first inductive value

n = n_{0} + 1

It contains only the base cases already proven (e.g. just

P (n_{0})

), so the step must succeed using only what the base guaranteed — a good sanity check on your base count.

Recall One-sentence rule of thumb

Count how far the step reaches back — that many base cases — and never let the hypothesis touch $n$ itself.

Connections

Parent: Strong induction — the full derivation and worked examples.
Mathematical Induction (ordinary) — the equivalent parent principle.
Well-Ordering Principle — alternative equivalent tool for these traps.
Recurrence Relations — source of the multi-base-case pitfalls.
Prime Factorisation — the "full history" application.
Sequences & Series — home chapter.