The Inductive Hypothesis

What the Inductive Hypothesis Says

In the previous tutorial, the base case was the direct verification of the claim at its starting index. That check starts the argument, but it does not explain how truth at one index leads to truth at the next. The inductive hypothesis is the assumption used to establish that link. Understanding its exact scope helps make induction proofs both valid and clear.

Suppose $P(n)$ is a statement intended to hold for every integer $n\ge m$. In the usual induction step, we fix an arbitrary integer $n\ge m$ and temporarily assume $P(n)$. This temporary assumption is the inductive hypothesis. We then use it to prove $P(n+1)$. The hypothesis concerns this one arbitrary index $n$; it does not assert that $P(k)$ is true for every $k\ge m$.

Definition. In an induction argument for a claim $P(n)$ over the integers $n\ge m$, the inductive hypothesis is the assumption that $P(n)$ holds for a fixed but arbitrary integer $n\ge m$, made while proving $P(n+1)$.

The word “arbitrary” is essential. We do not choose a special value of $n$ that makes the algebra convenient. We take any integer in the required range, suppose the statement holds at that index, and show that the next case follows. Once this implication has been proved for an arbitrary $n\ge m$, it is available at each index in that range.

The Principle of Mathematical Induction, established earlier in this course, combines the base case with this step. The inductive hypothesis is not a separate proof that $P(n)$ is true. Rather, it is the assumption in a conditional argument: if $P(n)$ is true, then $P(n+1)$ is true. The base case supplies the first truth in the chain; the implication carries it forward.

Use the Hypothesis, Do Not Assume the Conclusion

A good induction step makes the role of the hypothesis visible. When the target statement contains an expression at $n+1$, we often separate that expression into a part described by $P(n)$ and a new term. Then the hypothesis lets us replace the earlier part with a known quantity. The rest of the argument is ordinary algebra, arithmetic, or reasoning.

There is a logical boundary to observe. In the step, we may use the specific assertion $P(n)$, together with definitions and previously established results. We may not use $P(n+1)$ itself as a premise, since it is precisely what the step must prove. Nor may we simply say “the formula is true for all $n$” and use that global claim: it is the conclusion of the induction argument, not an available assumption.

Worked Example: A Sum of Consecutive Powers of Two

Consider the claim that for every $n\in\mathbb{N}_0$,

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

To understand the inductive hypothesis, write $P(n)$ for this equality. In the step, fix an arbitrary $n\ge0$ and assume

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

This is the inductive hypothesis. The left side of the target case $P(n+1)$ has one additional term:

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

Now use the hypothesis to replace the parenthesized sum:

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

This is exactly the formula claimed at $n+1$. The hypothesis did not give the target equality directly; it provided the value of the earlier partial sum, which allowed us to calculate the enlarged sum. The base case $n=0$ is $2^0=1=2^1-1$, so the induction principle completes the proof for every $n\ge0$.

A Complete Proof That Displays the Hypothesis

Here is a second example in which the hypothesis replaces a substantial part of the expression being proved. The statement is new, but the structure is the same: name the case, state the temporary assumption, and use it at a clearly identified point in the argument.

Theorem. For every $n\in\mathbb{N}_0$, $$ \sum_{k=0}^{n-1}(2k+1)=n^2, $$ where the sum is defined to be $0$ when $n=0$.

Proof. Let $P(n)$ be the displayed equality. For the base case $n=0$, the sum is empty and therefore equals $0$, while $0^2=0$. Thus $P(0)$ holds.

For the inductive step, let $n\ge0$ be arbitrary and assume $P(n)$, so that

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

The sum in $P(n+1)$ includes all the terms from $P(n)$, together with the new term whose index is $k=n$. Hence

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

Apply the inductive hypothesis to the parenthesized sum and simplify:

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

This is $P(n+1)$. The base case and the inductive step have both been established, so the Principle of Mathematical Induction gives $P(n)$ for every $n\in\mathbb{N}_0$. $\square$

Notice what the hypothesis did and did not say. It gave the value of the sum ending at $n-1$, which is precisely the part shared with the next case. It did not say that the sum ending at $n$ already equals $(n+1)^2$; that equality was obtained by adding the new term and simplifying.

Worked Examples: Tracking the Assumption Precisely

Worked Example: Divisibility by Seven

For each $n\in\mathbb{N}_0$, let $P(n)$ assert that $8^n-1$ is divisible by $7$. In other words, $P(n)$ says there is an integer $q$ such that $8^n-1=7q$.

The base case is $8^0-1=1-1=0=7\cdot0$, so $P(0)$ holds. For the step, fix $n\ge0$ and assume the inductive hypothesis $8^n-1=7q$ for some integer $q$. Then

8^{n+1}-1 = 8\cdot8^n-1 = 8(8^n-1)+7.

Using the hypothesis gives

8^{n+1}-1 = 8(7q)+7 = 7(8q+1).

Because $q$ is an integer, $8q+1$ is an integer, so $8^{n+1}-1$ is divisible by $7$. This proves $P(n+1)$ from $P(n)$. The hypothesis is used to produce the required integer multiple; it is not necessary to know the value of that integer in advance.

Worked Example: An Inequality for Powers of Three

Let $P(n)$ be the inequality $3^n\ge2n+1$, for $n\in\mathbb{N}_0$. At $n=0$, both sides equal $1$, so the base case holds. Now fix $n\ge0$ and assume the inductive hypothesis

3^n\ge2n+1.

Since $3>0$, multiplication by $3$ preserves the inequality. Therefore,

3^{n+1}=3\cdot3^n\ge3(2n+1)=6n+3.

Also $n\ge0$ implies $4n\ge0$, and hence $6n+3\ge2n+3=2(n+1)+1$. Chaining these inequalities gives

3^{n+1}\ge2(n+1)+1.

That is $P(n+1)$. This example shows that the inductive hypothesis may be an inequality rather than an equality. It also shows that the range condition $n\ge0$ can be needed for the final comparison.

Common Misunderstandings

One common mistake is to treat the hypothesis as though it were the theorem. In the step, $P(n)$ is assumed only for the purpose of proving the implication to $P(n+1)$. It is not an independent conclusion that can be cited without qualification. The induction principle is what turns the verified base case and the proved implications into the claim for every index.

A different mistake is to assume several cases when the argument only needs one. In ordinary induction, the step from $n$ to $n+1$ uses $P(n)$. If a proof needs both $P(n)$ and $P(n-1)$, that is a different setup: it must state and justify the appropriate assumptions and initial cases. Do not silently add an assumption that the proof has not established.

Finally, an inductive hypothesis must match the statement exactly. If $P(n)$ is an equality, use that equality as written; if it includes a condition or a specified range, retain that condition. An algebraic expression resembling the hypothesis is not enough if its index or terms differ. Before using the hypothesis, check that the piece you want to replace is exactly the quantity $P(n)$ describes.

Fix an arbitrary index.
Choose an integer $n$ in the range where the step is required.

State the hypothesis explicitly.
Write down $P(n)$, including its equality, inequality, or other precise assertion.

Work toward the next case.
Manipulate the expression or statement in $P(n+1)$ until the hypothesis can be applied.

Identify the conclusion.
Show that the result is exactly $P(n+1)$, without assuming it along the way.

Key takeaway. The inductive hypothesis is a temporary assumption of $P(n)$ for an arbitrary index in the stated range. Its purpose is to help prove $P(n+1)$; the base case and the induction principle then extend the result to all required indices.

Check Your Understanding

For each question, distinguish the assumed case from the case that the induction step must establish.

If $P(n)$ is the formula for a sum ending at $n$, what should you check before using the hypothesis to evaluate the sum ending at $n+1$?
In an induction step, why is it not valid to assume $P(n+1)$ while proving $P(n+1)$?
For the claim that $8^n-1$ is divisible by $7$, what does the inductive hypothesis provide, and why must its quotient be an integer?
In the inequality example, where is the condition $n\ge0$ used to compare $6n+3$ with $2n+3$?
What is the difference between assuming $P(n)$ for a fixed arbitrary $n$ and assuming $P(k)$ for every $k\ge m$?

What You'll Learn