Induction proofs where plugging in n+1 is not the step

Induction is taught as a ritual with two lines. Check $n = 1$. Then assume the statement for $n$, plug in $n+1$, and grind the algebra until the two sides agree. For a sum formula that is honestly all there is, and a student who has only ever proved $1 + 2 + \cdots + n = \tfrac{n(n+1)}{2}$ leaves with the impression that induction is bookkeeping.

Then they meet a problem where the step is the entire difficulty, and the ritual has nothing to offer. There is no expression to substitute into and no algebra to grind. The question was never what happens when you plug in $n+1$. It is what the size-$(n+1)$ object is made of, and whether it contains the size-$n$ one anywhere you can reach.

This is a guide to the four ways that containment fails, and what each failure asks you to change. None of the repairs is more algebra.

What the step is actually asking

The induction technique page puts the craft in one sentence: find where the size-$(k+1)$ problem contains a size-$k$ copy of itself. Remove a disk, delete a vertex, strip the last term.

Hold on to that phrasing, because it is doing real work. An inductive step is not a manipulation. It is a claim that the big object contains the small one, and that the containment is tight enough to hand the conclusion back. Four things can go wrong with that claim.

One predecessor is not enough

Take the problem: if $x + \tfrac1x$ is an integer, so is $x^n + \tfrac1{x^n}$. Write $a_n = x^n + x^{-n}$ and $t = x + \tfrac1x$. Plugging in $n+1$ means asking what $a_{n+1}$ is in terms of what you already have. Multiply $a_n$ by $t$, expand, and the answer arrives with a passenger:

$$a_n t = a_{n+1} + a_{n-1}, \quad \text{so} \quad a_{n+1} = t\,a_n - a_{n-1}.$$

The hypothesis you were carrying, that $a_n$ is an integer, does not close this. It leaves $a_{n-1}$ floating, and no amount of rearranging removes it. With $t = 3$ the sequence runs $2, 3, 7, 18, 47$, while $t\,a_n$ on its own would produce $9$ where the truth is $7$. The extra term is not an accounting slip. The object genuinely depends on two predecessors, not one.

The repair is to carry more. Assume the statement for every index up to $n$ rather than for $n$ alone. Strong induction is not a stronger axiom, since it follows from ordinary induction applied to the statement "it holds for all $m \le n$". It is a stronger hypothesis, and a hypothesis is the fuel a step runs on.

The statement is too weak to carry itself

Prove that $\sum_{k=1}^{n} \tfrac{1}{k^2} < 2$ for every $n$. Induct directly and watch it die: assume $S_n < 2$, add $\tfrac{1}{(n+1)^2}$, and conclude nothing at all. For all the hypothesis tells you, $S_n$ is $1.9$, and $1.9 + \tfrac14$ is already past $2$. The assumption is perfectly true and completely useless, because it says the sum is under the bar without saying by how much.

So prove something harder. The claim $S_n \le 2 - \tfrac1n$ carries a margin, and the margin is exactly what the next term has to fit inside. The step reduces to $\tfrac{1}{(n+1)^2} \le \tfrac{1}{n} - \tfrac{1}{n+1} = \tfrac{1}{n(n+1)}$, which holds because $n(n+1) < (n+1)^2$. One line, where the weaker statement gave none.

This is the paradox worth internalising: proving more can be easier than proving less. A weak statement is harder to want and harder to use. When your step stalls because the hypothesis "is not enough", the fix is almost never a cleverer manipulation. It is a bolder claim.

You have to choose what to remove

Every tournament has a Hamiltonian path: in any set of players where each pair has played and someone won, the players can be lined up so each beats the next. Delete a player, order the rest by hypothesis, and put the deleted one back. That last clause is where the proof is.

Two placements are free. If the returning player beats the current leader, they go in front. If the current tail beats them, they go on the end. The temptation is to stop there, and it is wrong: search the tournaments on four players and you find one where an ordering of three exists that the fourth can neither lead nor trail, and where a full ordering exists anyway, somewhere in the middle. Appending is not a proof, it is two of the cases.

The step is insertion, not attachment. Walk along the ordering to the first player the newcomer beats, and slide in immediately before them. Everyone earlier beats the newcomer, and that is guaranteed by the word first rather than by luck.

The same shape governs any $n$ points not all collinear determining at least $n$ lines. The induction only starts if you delete a point that leaves the remaining ones non-collinear, and the configurations where no such point exists are a separate argument rather than an oversight. Both problems teach one lesson: the hypothesis does not apply itself. You choose the smaller object, and a careless choice makes the step false rather than merely hard.

The step that quietly assumes n is large

The classic fake proof that all horses are the same colour is worth taking seriously, because its failure is a failure people reproduce sincerely. Base case: one horse matches itself. Step: given $n+1$ horses, the first $n$ share a colour and the last $n$ share a colour, the two groups overlap, so all $n+1$ match.

Every line is correct except at one value. The two overlapping groups have a horse in common whenever $n \ge 2$, and at $n = 1$ they are the two single horses of a pair, which share nothing. So the step is valid for every $n$ from $2$ upward, and false at exactly the value the base case hands it.

That is the whole disease: an argument that is sound for large $n$ and silently assumes it. Whenever a step needs two things to overlap, or a set to be non-empty, or three chosen items to be distinct, write down the smallest $n$ at which that is genuinely true, and check that the base case reaches it. The gap is always one value wide, which is why it survives reading.

The question that replaces the ritual

Before writing anything, ask: what shrinks, and by exactly how much?

The cleanest answer in the archive belongs to a polynomial of degree $n$ having at most $n$ real roots. A root peels off a linear factor with nothing left over, and the degree falls by precisely one. The measure is explicit, the descent is finite, and the induction is then a formality. That is what a healthy step looks like from the outside.

Answering that question tells you the object you delete, the hypothesis you need to carry, and how many base cases you owe. All three are decisions, and all three are made before a single symbol of algebra. Plugging in $n+1$ is what you do afterwards, once there is something to plug in.

Practising the part that is hard

The recognition here is trained by writing steps, not proofs. Take ten induction problems and, for each, write only three lines: what you delete, what the hypothesis must say for the deletion to pay off, and the smallest $n$ at which the step is honest. Do not finish any of them. You will get through ten in the time one full write-up costs, and the three lines are where every one of these proofs is won or lost.

Lemma teaches induction as a named technique with the strengthening trick attached, rather than as a formula ritual met once and forgotten. The problem archive has the four problems above in full, with difficulty and expected time on each, and the daily problem posts a new one every day in three tiers with no account needed.