Students often get stuck in the inductive step because they treat it as a blank algebra problem. It is not. The inductive step is a targeted manoeuvre: rewrite the (k+1)-expression until the k-expression is visible inside it, then swap the k-expression for whatever the inductive hypothesis says it equals. That substitution is where the hypothesis "injects" into the proof, and the rest is simplification.

Every standard technique for inductive steps — peel the last term, factor out a common piece, split the sum, rewrite using the recurrence — is a way of exposing the k-case inside the (k+1)-case so the hypothesis can be substituted in.

Once you internalise this, the step stops feeling creative and starts feeling like a search pattern: find the spot, inject, simplify.

The shape of every inductive step

Call the target formula, inequality, or divisibility claim P(n). The step has to prove P(k+1) assuming P(k). Write both explicitly.

Now stare at \text{LHS}(k+1). Your job is to rewrite it until \text{LHS}(k) appears as a sub-expression. The moment it does, the hypothesis lets you replace \text{LHS}(k) by \text{RHS}(k), and the rest is algebra.

That rewriting — the search for where \text{LHS}(k) lives inside \text{LHS}(k+1) — is the entire creative content of the proof.

Injecting the hypothesis into the inductive stepA diagram showing the LHS of P(k+1) on the left, with a highlighted sub-expression labelled "LHS(k) hidden here". An arrow labelled "substitute via hypothesis" points to a second expression where LHS(k) has been replaced by RHS(k). A further arrow labelled "simplify" leads to RHS(k+1), the goal. LHS(k+1) find LHS(k) inside [LHS(k)] + extra inject substitute via hypothesis RHS(k) + extra now pure algebra simplify RHS(k+1) goal Three phases: expose, substitute, simplify. The "creative" part is Phase 1 — finding where LHS(k) is hiding. Phases 2 and 3 are mechanical.
Every inductive step follows the same three-phase rhythm. Phase 1 is the rewrite that exposes $\text{LHS}(k)$ inside $\text{LHS}(k+1)$. Phase 2 substitutes using the hypothesis. Phase 3 is algebra to reach $\text{RHS}(k+1)$. The first phase is where thinking happens; the other two are bookkeeping.

Four standard injection patterns

The patterns that expose \text{LHS}(k) inside \text{LHS}(k+1) are not infinite — a handful of moves cover most problems. Here are the four you meet constantly.

Pattern 1: peel the last term (summation)

When the \text{LHS} is a sum, \text{LHS}(k+1) includes one more term than \text{LHS}(k). Split off that term.

\underbrace{a_1 + a_2 + \dots + a_k}_{\text{LHS}(k)} + a_{k+1} = \text{LHS}(k+1)

Substitute \text{LHS}(k) = \text{RHS}(k) by the hypothesis, then add a_{k+1} and simplify. This is the go-to pattern for sum formulas.

Pattern 2: factor the base (divisibility, exponential)

When the \text{LHS} has a power like r^{k+1}, rewrite it as r \cdot r^k. The r^k is the hypothesis's handle.

For 7^{k+1} - 1: write it as 7 \cdot 7^k - 1 = 7(7^k - 1) + 6. Now 7^k - 1 is exposed; the hypothesis says it is divisible by 6, and +6 is obviously divisible by 6.

Pattern 3: split the recurrence (sequences)

When a sequence obeys a_{k+1} = f(a_k, a_{k-1}, \dots), the recurrence itself exposes the previous cases. For a_{k+1} = 2 a_k - a_{k-1}, substitute the hypothesis's formulas for a_k and a_{k-1} directly, then simplify.

Pattern 4: decompose into sub-objects (structural)

When P(n) is a statement about a structure (a polygon's diagonals, a graph's edges, a tower of Hanoi configuration), build the (k+1)-structure by taking a k-structure and adding one piece. The hypothesis covers the k-structure; you handle only the new piece.

Each pattern is a template for the rewrite. When you recognise which pattern the problem fits, the rewrite is forced — not invented.

Worked walkthrough: peeling the last term

Claim: \sum_{i=1}^n i^3 = \left(\frac{n(n+1)}{2}\right)^2 for all n \geq 1.

Hypothesis. \sum_{i=1}^k i^3 = \left(\frac{k(k+1)}{2}\right)^2.

Goal. \sum_{i=1}^{k+1} i^3 = \left(\frac{(k+1)(k+2)}{2}\right)^2.

Rewrite — find \text{LHS}(k) inside \text{LHS}(k+1).

\sum_{i=1}^{k+1} i^3 = \underbrace{\sum_{i=1}^{k} i^3}_{\text{LHS}(k)} + (k+1)^3.

Why: the sum up to k+1 is the sum up to k plus one more term. This is the "peel the last term" pattern, and it exposes the hypothesis's handle cleanly.

Inject. Substitute using the hypothesis:

\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3.

Simplify. Factor (k+1)^2 from both terms:

= \frac{k^2 (k+1)^2}{4} + (k+1)^3 = (k+1)^2 \left[\frac{k^2}{4} + (k+1)\right] = (k+1)^2 \cdot \frac{k^2 + 4(k+1)}{4} = \frac{(k+1)^2 (k+2)^2}{4}.

That is \left(\frac{(k+1)(k+2)}{2}\right)^2, exactly \text{RHS}(k+1). \square

Notice the structure: the thinking happened in one line — "peel the last term." Everything after was mechanical.

Worked walkthrough: factoring the base

Claim: 8 \mid (3^{2n} - 1) for all n \geq 1.

Hypothesis. 3^{2k} - 1 = 8m for some integer m, i.e., 3^{2k} = 8m + 1.

Goal. 3^{2(k+1)} - 1 is divisible by 8.

Rewrite.

3^{2(k+1)} - 1 = 3^{2k+2} - 1 = 9 \cdot 3^{2k} - 1.

Why: rewrite 3^{2(k+1)} as 9 \cdot 3^{2k}. The factor 3^{2k} is the handle. Pattern 2 in action.

Inject. Substitute 3^{2k} = 8m + 1:

= 9(8m + 1) - 1 = 72m + 9 - 1 = 72m + 8 = 8(9m + 1).

Why: the expression is now manifestly a multiple of 8. The hypothesis handed you exactly what you needed.

That establishes 8 \mid (3^{2(k+1)} - 1). \square

How to find the injection spot when it is not obvious

Sometimes the rewrite does not suggest itself. Two habits help.

Habit 1: write \text{LHS}(k+1) and \text{LHS}(k) side by side. Literally. Put them on two lines. The difference between them — the extra stuff in \text{LHS}(k+1) that is not in \text{LHS}(k) — tells you what to isolate.

For \sum_{i=1}^n i^2: \text{LHS}(k+1) - \text{LHS}(k) = (k+1)^2. So peel off (k+1)^2.

For 3^{2n}: \frac{3^{2(k+1)}}{3^{2k}} = 9. So factor out 9.

Habit 2: ask "what do I want a copy of \text{LHS}(k) for?" The answer is always the same: to replace it with \text{RHS}(k). So arrange your rewrite until \text{LHS}(k) appears as a grouped sub-expression you can literally substitute for.

If you cannot find the spot after two minutes of honest effort, the problem may need strong induction (the reach-back is more than one step), or the statement is wrong, or you need to strengthen the hypothesis. Those are the three real escape routes.

A sneaky injection: telescoping sums

Claim. \sum_{i=1}^n \frac{1}{i(i+1)} = 1 - \frac{1}{n+1} for all n \geq 1.

Hypothesis. \sum_{i=1}^k \frac{1}{i(i+1)} = 1 - \frac{1}{k+1}.

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

Rewrite. Peel the last term:

\sum_{i=1}^{k+1} \frac{1}{i(i+1)} = \underbrace{\sum_{i=1}^{k} \frac{1}{i(i+1)}}_{\text{LHS}(k)} + \frac{1}{(k+1)(k+2)}.

Inject.

= \left(1 - \frac{1}{k+1}\right) + \frac{1}{(k+1)(k+2)}.

Simplify. Common denominator (k+1)(k+2):

= 1 - \frac{k+2}{(k+1)(k+2)} + \frac{1}{(k+1)(k+2)} = 1 - \frac{k+2 - 1}{(k+1)(k+2)} = 1 - \frac{k+1}{(k+1)(k+2)} = 1 - \frac{1}{k+2}.

That matches \text{RHS}(k+1). \square

Why this example matters: the algebra looked unfamiliar — fractions with different denominators — but the shape was identical to every summation proof. Peel, inject, simplify. The unfamiliar surface hides a completely routine skeleton.

When the injection does not happen directly

Sometimes the hypothesis does not slot into \text{LHS}(k+1) as-is. It needs to be transformed first.

Example: in inequality proofs, you may need to use the hypothesis and an auxiliary inequality like k \geq 3 or k^2 \geq 2k + 3. In that case:

  1. Inject the hypothesis.
  2. Apply the auxiliary bound.
  3. Simplify to the goal.

The structure is the same — expose, substitute, simplify — but the "simplify" phase requires an extra tool. Recognising that the step has a two-tool structure (hypothesis + auxiliary inequality) is the core skill for inequality induction.

See Recognition: Inequality Induction Proofs Need the Hypothesis Plus One Extra Inequality — Plan for the Gap for more on this.

The one-line takeaway

The inductive step is a three-phase move: rewrite \text{LHS}(k+1) to expose \text{LHS}(k) inside it, substitute using the hypothesis, then simplify to \text{RHS}(k+1). Every "technique" for inductive steps is a named way of doing the exposure. Find the spot to inject, and the rest is bookkeeping.

Once you see proofs this way, the inductive step stops being a wall and becomes a pattern match. You look at \text{LHS}(k+1), ask "where is \text{LHS}(k) hiding?", inject, and finish.

Related: Mathematical Induction · Intuition: Write P(k+1) Explicitly on a Fresh Line Before Starting the Inductive Step · The Inductive Step Does Not Prove P(k) — It Only Transports Its Truth · What's the Difference Between the Inductive Hypothesis and the Inductive Step? · Recognition: Inequality Induction Proofs Need the Hypothesis Plus One Extra Inequality