The Inductive Step

The Inductive Step as an Implication

The inductive hypothesis is the assumption used within an induction step. The step itself is the argument that shows this assumption is enough to establish the next case. Keeping those roles distinct makes it easier to see what must be proved and what may be used.

Suppose $P(n)$ is a statement for integers $n\ge m$. The inductive step fixes an arbitrary such integer $n$, assumes $P(n)$, and proves $P(n+1)$. In logical form, it establishes the implication $P(n)\Rightarrow P(n+1)$ for every $n\ge m$. The assumption is temporary: the step does not claim that $P(n)$ has already been proved at this particular index.

Definition. For a statement $P(n)$ intended to hold for all integers $n\ge m$, the inductive step is the proof that, for an arbitrary integer $n\ge m$, $P(n)$ implies $P(n+1)$.

An induction proof uses the Principle of Mathematical Induction, established earlier in this course. That principle combines a verified base case with the inductive step to conclude that all required cases hold. Here we concentrate on the step: how to make the implication valid and how to show, explicitly, that its conclusion is $P(n+1)$.

A useful way to begin is to write down the target case before manipulating anything. Ask what $P(n+1)$ says, identify the portion of it that is described by $P(n)$, and determine what additional fact is needed. Often the target expression consists of an old part plus a new term, or of an old quantity multiplied by a new factor. The hypothesis supplies the old part; the rest of the step must account for the change.

A General Pattern for Sums

For a sum, the cases at $n$ and $n+1$ often differ by one term. This gives a reliable structure: write the longer sum as the shorter sum plus its new final term, substitute the hypothesis for the shorter sum, and simplify. The following theorem records a useful instance of that pattern.

Theorem. Let $m$ be an integer and let $a_k$ and $b_k$ be real numbers defined for integers $k\ge m$. Suppose $$ a_k=b_{k+1}-b_k $$ for every $k\ge m$. Then, for every integer $n\ge m$, $$ \sum_{k=m}^{n-1}a_k=b_n-b_m, $$ where the sum is defined to be $0$ when $n=m$.

Proof. We use induction on $n$, starting at $m$. When $n=m$, the sum is empty and equals $0$, while $b_m-b_m=0$. Thus the claim holds at the starting index.

For the inductive step, fix an arbitrary integer $n\ge m$ and assume $$ \sum_{k=m}^{n-1}a_k=b_n-b_m. $$ The sum in the next case includes the terms through $k=n$, so

\sum_{k=m}^{n}a_k = \left(\sum_{k=m}^{n-1}a_k\right)+a_n.

By the inductive hypothesis, the sum in parentheses is $b_n-b_m$. By the assumed relation between $a_n$ and the $b$'s, $a_n=b_{n+1}-b_n$. Therefore,

\sum_{k=m}^{n}a_k = (b_n-b_m)+(b_{n+1}-b_n) = b_{n+1}-b_m.

This is precisely the claimed formula with $n+1$ in place of $n$. The base case and the step are proved, so induction gives the formula for every $n\ge m$. $\square$

The proof illustrates the central task of a step: the hypothesis describes the part already present, and the defining relation for the new term completes the next case. The index matters. The added term is $a_n$, and the relation needed for it is the relation at $k=n$, not at $k=n+1$.

Worked Example: A Sum of Consecutive Odd Numbers

We prove that for every integer $n\ge1$,

\sum_{k=1}^{n}(2k-1)=n^2.

Let $P(n)$ be this equality. At $n=1$, the left side is $2(1)-1=1$, and the right side is $1^2=1$, so the base case holds.

For the step, fix $n\ge1$ and assume $P(n)$, namely

\sum_{k=1}^{n}(2k-1)=n^2.

The next sum includes the new term with index $n+1$. Hence

\sum_{k=1}^{n+1}(2k-1) = \left(\sum_{k=1}^{n}(2k-1)\right)+(2(n+1)-1).

Use the hypothesis for the parenthesized sum and simplify the new term:

\sum_{k=1}^{n+1}(2k-1) = n^2+2n+1 = (n+1)^2.

This is $P(n+1)$. Thus the step is complete, and induction proves the formula for all $n\ge1$. The key was not merely to add a term, but to identify that term correctly and then use the hypothesis on exactly the shared portion.

Worked Examples: Other Forms of a Step

Worked Example: A Lower Bound for Factorials

For every integer $n\ge1$, we claim

n!\ge 2^{n-1}.

At $n=1$, $1!=1=2^0$, so the base case holds. Now fix $n\ge1$ and assume the inductive hypothesis $n!\ge2^{n-1}$. By the definition of factorial,

$$ (n+1)!=(n+1)n!. $$

Since $n\ge1$, we have $n+1\ge2>0$. Multiplying the hypothesis by the positive number $n+1$ preserves its direction, giving

(n+1)! \ge (n+1)2^{n-1} \ge 2\cdot2^{n-1} = 2^n.

The second inequality follows from $n+1\ge2$ and $2^{n-1}>0$. The final expression is the claimed bound at $n+1$. The restriction $n\ge1$ is used in the comparison $n+1\ge2$; without checking that range, the step would not be justified.

Worked Example: Divisibility of a Power Difference

For every $n\in\mathbb{N}_0$, the integer $11^n-1$ is divisible by $10$. To prove this, let $P(n)$ be the assertion that there is an integer $q$ such that $11^n-1=10q$.

At $n=0$, $11^0-1=1-1=0=10\cdot0$, so $P(0)$ holds. For the step, fix $n\ge0$ and assume $P(n)$. Thus $11^n-1=10q$ for some integer $q$. Rewrite the target expression as

11^{n+1}-1 = 11\cdot11^n-1 = 11(11^n-1)+10.

The identity can be checked by expanding its right-hand side: $11(11^n-1)+10=11^{n+1}-11+10=11^{n+1}-1$. Now substitute the inductive hypothesis:

11^{n+1}-1 = 11(10q)+10 = 10(11q+1).

Because $q$ is an integer, $11q+1$ is an integer. Therefore $11^{n+1}-1$ is divisible by $10$, which proves $P(n+1)$. The hypothesis supplies an integer multiple of $10$; the extra $10$ in the rewritten expression is what allows the next case to have the same form.

Theorem. For every integer $n\ge1$, $$ \sum_{k=1}^{n}(3k-2)=\frac{n(3n-1)}{2}. $$

Proof. At $n=1$, the sum is $3(1)-2=1$, and the right-hand side is $1(3-1)/2=1$. Suppose now that $n\ge1$ and that $$ \sum_{k=1}^{n}(3k-2)=\frac{n(3n-1)}{2}. $$ Separate the last new term in the next case and apply the hypothesis:

\begin{aligned} \sum_{k=1}^{n+1}(3k-2) &=\left(\sum_{k=1}^{n}(3k-2)\right)+(3(n+1)-2)\\ &=\frac{n(3n-1)}{2}+3n+1\\ &=\frac{3n^2-n+6n+2}{2}\\ &=\frac{3n^2+5n+2}{2}\\ &=\frac{(n+1)(3n+2)}{2}\\ &=\frac{(n+1)(3(n+1)-1)}{2}. \end{aligned}

This is the stated formula at $n+1$. The base case and inductive step are established, so the Principle of Mathematical Induction proves the theorem for every $n\ge1$. $\square$

What to Check Before Declaring the Step Complete

A step can contain correct algebra and still fail as an induction argument if its logic is unclear. Before finishing, check that the index was arbitrary in the required range, that the hypothesis was stated accurately, and that every extra comparison or divisibility claim has been justified. Then compare the final line with the exact definition of $P(n+1)$. A result that is close to the target is not enough; it must establish the target itself.

A common error is to begin with $P(n+1)$ and manipulate it until the hypothesis appears, then claim that the implication has been proved. Working backward can help discover a route, but the written proof must explain why the transformations are reversible, or present a forward argument that derives the target from the hypothesis. For example, multiplying an inequality by a negative number reverses its direction, and dividing by a quantity requires knowing it is nonzero. Such conditions cannot be left implicit.

Another error is to make a special choice of $n$. The step must hold for every index in the required range, not merely for a value that happens to make the calculation work. If the argument uses $n\ge1$, $n\ge0$, or some other condition, state it and identify where it is needed. The factorial example used $n\ge1$ to obtain $n+1\ge2$; the same comparison would not follow from an unstated or weaker range.

Fix an arbitrary index.
Choose $n$ in the full range for which the step is required.

State the hypothesis and target.
Write $P(n)$ as the temporary assumption and $P(n+1)$ as the conclusion to establish.

Find the connection.
Separate the part shared by the two cases from the new term, factor, or condition.

Use the hypothesis with its conditions.
Substitute or compare only where the hypothesis applies, and justify any sign or range requirements.

Identify the next case exactly.
Show that the final equality, inequality, or divisibility statement is $P(n+1)$, not merely a related claim.

Key takeaway. The inductive step proves a conditional statement: for an arbitrary permitted $n$, assuming $P(n)$ leads to $P(n+1)$. Its success depends on using the hypothesis precisely, accounting for what changes from one case to the next, and verifying the conclusion in the exact form required.

Check Your Understanding

For each question, identify what the inductive step assumes and what it must establish.

In the proof about factorials, why is the condition $n\ge1$ needed to compare $n+1$ with $2$?
When a sum at $n+1$ is written as a sum at $n$ plus one term, which index gives the new term?
In the divisibility example, what information does the inductive hypothesis provide about $11^n-1$?
Why does working backward from $P(n+1)$ require care before it can serve as a proof of the step?
What must be checked about the final line of an inductive step before concluding that $P(n+1)$ has been proved?

What You'll Learn