Mathematical induction — principle, steps, problems: Question bank

Reminder of the vocabulary the parent note built, so no symbol here is unearned:

$P (n)$ — a statement about a natural number $n$ (one domino).
Base case — the first domino, $P (n_{0})$ , checked directly.
Inductive hypothesis (IH) — the assumed truth of $P (k)$ for one fixed $k$ .
Inductive step — the proof that $P (k) \Rightarrow P (k + 1)$ (each domino knocks the next).
PMI — Principle of Mathematical Induction; strong induction assumes all of $P (n_{0}), \dots, P (k)$ .

True or false — justify

A truthful domino falls only if both the base and the step hold. Each item hides a place where one of them silently breaks.

If a statement's inductive step

P (k) \Rightarrow P (k + 1)

is valid but the base case is false, the statement is still proved for all

n

False — the chain has no starting domino, so nothing is forced to fall; a working step over a false base proves nothing.

P (k) \Rightarrow P (k + 1)

is true for every

k

" alone guarantees

P (n)

holds for all

n

False — the implication may be vacuously true while every

P (n)

is false; you still need one true

P (n_{0})

to ignite it.

Checking

P (1), P (2), \dots, P (1000)

all true is enough to conclude

P (n)

for all

n

False — finitely many checks never cover the infinite tail; e.g.

n^{2} - n + 41

is prime for

n = 1..40

but composite at

41

Induction can prove statements about all integers (including negatives) directly.

False — ordinary PMI walks upward from a starting value; negatives need a separate downward argument or a re-indexing, not the plain template.

Strong induction can prove theorems that ordinary induction cannot.

False — they are logically equivalent; strong induction is only a convenience when

P (k + 1)

leans on several earlier cases.

In a proof of "

2^{n} > n

", the base case

n = 1

is optional because the step is obvious.

False — the step

2^{k + 1} > 2 k \geq k + 1

only chains once

2^{1} > 1

is verified; drop the base and the whole implication chain is untethered.

If the inductive step secretly uses

P (k + 1)

to prove

P (k + 1)

, the proof is still fine as long as the algebra checks.

False — that is circular (assuming what you must prove); a correct step derives

P (k + 1)

using only earlier cases.

Well-Ordering (every nonempty set of naturals has a least element) is a consequence of induction but not equivalent to it.

False — they are logically equivalent; each can be derived from the other, which is why a "smallest counterexample" argument justifies PMI.

A single valid inductive step lets you start the chain at any

n_{0}

you like without checking that particular

n_{0}

False — the base case must be verified at the exact

n_{0}

where you claim the chain begins; the step preserves truth but cannot create it.

Spot the error

Each of these is a plausible-looking proof with one fatal flaw. Name the exact broken link.

"To prove all horses are the same colour: base

n = 1

trivial; for

k \to k + 1

, drop one horse then another and overlap." Where does it fail?

The overlap argument needs two horses to share, so the step

P (1) \Rightarrow P (2)

fails — the very first genuine step is broken even though later steps look fine.

A student writes "Assume

P (k + 1)

is true; adding the next term gives

P (k + 2)

." What's wrong?

They assumed

P (k + 1)

, the thing to be proved at that stage — the IH must assume

P (k)

and derive the next case.

P (n)

\sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2}

. Step:

\sum_{i = 1}^{k + 1} i = \frac{( k + 1 ) ( k + 2 )}{2}

because both sides are polynomials." Flaw?

No use of the IH occurs — a genuine step must rebuild

P (k + 1)

's LHS from

P (k)

's LHS by adding the

(k + 1)

-th term, not just assert the target.

P (n)

n < n + 1

. Base

n = 1

✓. Step: since

k < k + 1

, obviously

k + 1 < k + 2

." Is this valid induction?

The step doesn't use the IH at all —

k + 1 < k + 2

is true independently, so nothing was inferred from

P (k)

; the "induction" is decorative (though the statement is trivially true anyway).

"Prove

6 ∣ n^{3} - n

. Step:

(k + 1)^{3} - (k + 1) = (k^{3} - k) + 3 k (k + 1)

, and

3 k (k + 1)

is divisible by 6." Which claim is unjustified without a reason?

That

3 k (k + 1)

is divisible by 6 — it needs the fact that

k (k + 1)

(two consecutive integers) is even; skipping that leaves a gap.

"Base

n = 0

, but the claim was stated for all

n \geq 1

." Why is this a mismatch even if

P (0)

is true?

The base must be checked at the stated starting value

n_{0} = 1

; verifying a different value doesn't ignite the chain you actually claimed.

Why questions

These probe why the machinery is built the way it is.

Why must the inductive hypothesis fix

k

as one arbitrary value rather than "all

k

If you assumed it for all

k

you'd be assuming the theorem; fixing one arbitrary

k

and deriving

k + 1

is what actually chains the dominoes.

Why does adding "the next term to both sides" work so often in sum-formula proofs?

Because

P (k + 1)

's left side is literally

P (k)

's left side plus one more term, so adding exactly that term converts the assumed equality into the target.

Why is factoring out the common

(k + 1)

early (as in the sum-of-squares proof) a smart move?

The target formula for

P (k + 1)

already contains

(k + 1)

as a factor, so pulling it out immediately steers the algebra toward the desired shape.

Why is induction equivalent to the Well-Ordering Principle?

A failing statement would have a least counterexample

m

; the base rules out

m = n_{0}

and the step forces

P (m)

from

P (m - 1)

— a contradiction, so no least counterexample exists.

Why does Fibonacci naturally call for strong induction rather than ordinary?

Each term depends on the two previous terms, so proving

P (k + 1)

needs both

P (k)

and

P (k - 1)

— you must assume all earlier cases, which is exactly strong induction.

Why can the Binomial Theorem be proved by induction on

n

Multiplying

(a + b)^{k}

by one more factor

(a + b)

turns the assumed expansion into the next one, so

P (k) \Rightarrow P (k + 1)

mirrors the domino step.

Why is "the step looks like the whole proof" a dangerous feeling?

The step only says "if a domino falls, the next does" — it is a conditional; without the base case nothing is ever unconditionally established.

Edge cases

Boundary situations where the template needs care.

If a statement is true for all

n \geq 3

but false for

n = 1, 2

, can induction still prove it?

Yes — set the base case at

n_{0} = 3

and run the step for

k \geq 3

; the chain simply starts later and covers

n \geq 3

What happens if the inductive step is valid only for

k \geq 4

but you set the base at

n_{0} = 1

The chain breaks between the base and where the step becomes valid; you must either fix the base at

n_{0} = 4

(and check

1, 2, 3

separately) or make the step hold from

n_{0}

on.

Is checking a base case at

n_{0} = 0

ever legitimate?

Yes — if the statement is claimed for all

n \geq 0

; the "starting value" is whatever

n_{0}

the theorem specifies, and

0

is a perfectly valid natural starting point.

For "

2^{n} > n

", why does the step need

2 k \geq k + 1

, and does this hold for the smallest

k

We reach

2^{k + 1} > 2 k

from the IH, then need

2 k \geq k + 1

i.e.

k \geq 1

— which holds at the base

k = 1

, so the chain is unbroken from the start.

A degenerate empty sum:

\sum_{i = 1}^{0} i = 0

. Does the formula

\frac{n ( n + 1 )}{2}

still give the right value at

n = 0

Yes —

\frac{0 \cdot 1}{2} = 0

matches the empty sum, so

n = 0

is a valid (if trivial) extra base check.

P (k) \Rightarrow P (k + 1)

fails at exactly one value

k = 7

, what can still be salvaged?

The chain proves

P (n)

only up to

n = 7

(from a valid base); beyond the break you'd need a fresh base at

n_{0} = 8

and a step valid there.

Can strong induction get by with no explicit base case?

No — at

k = n_{0}

the "assume all earlier cases" set is empty, so proving

P (n_{0})

then requires a genuine direct verification, which is the base case in disguise.

Connections

Mathematical induction — principle, steps, problems — parent: the full principle and worked proofs.
Well-Ordering Principle — the equivalence that justifies "smallest counterexample" reasoning.
Recurrence Relations & Fibonacci — where strong induction is essential.
Binomial Theorem — a classic induction-on- $n$ target.
Sum of Squares and Cubes · Arithmetic & Geometric Series · Divisibility and Modular Arithmetic — the proof families these traps draw from.