How to Prove a Closed Form for n = k + 1 by Induction

A proof for the case $n=k+1$ is the inductive step. It is not a separate guess: you start by assuming the proposed formula is true at $n=k$, then show that this assumption makes it true at $n=k+1$.

The title does not identify a particular closed-form expression, so there is no specific identity to prove. The method below applies to formulas such as sums, products, and recursively defined sequences. A complete induction proof still needs both a base case and the inductive step.

Write the claim as a statement

Call the proposed formula $P(n)$. For example, if you want to prove a formula for a sum, write the statement with its index range and claimed value. The inductive step has this logical form:

1. Choose an arbitrary allowed integer $k$.
2. Assume $P(k)$ is true. This is the induction hypothesis.
3. Use it to establish $P(k+1)$.

The hypothesis is available only for the case $k$. You may use definitions or known identities as well, but you cannot assume the desired $k+1$ case—that would make the reasoning circular.

A reliable way to handle the k + 1 case

Begin with the expression in the $k+1$ case and rewrite it so that the $k$ case appears. For a sum, this usually means separating the final term:

$$\sum_{i=1}^{k+1} a_i = \sum_{i=1}^{k} a_i + a_{k+1}.$$

Now substitute the induction hypothesis for the sum through $k$. Simplify the result until it matches the claimed formula with $n=k+1$. State that match explicitly; it is the point of the step.

For a sequence defined recursively, use the recurrence to express the term at $k+1$ in terms of earlier terms, then substitute the applicable induction hypotheses and simplify. If the recurrence depends on more than the term at $k$, ensure your induction hypothesis covers the earlier cases needed—for example, by using strong induction.

Worked example: sum of the first n odd numbers

Prove that

$$1+3+5+\cdots +(2n-1)=n^2$$

for every integer $n\geq 1$.

Base case: For $n=1$, the left side is $1$, and the right side is $1^2=1$. Thus $P(1)$ is true.

Induction hypothesis: Assume for an arbitrary $k\geq 1$ that

$$1+3+5+\cdots +(2k-1)=k^2.$$

Inductive step: The next sum adds the next odd number, which is $2(k+1)-1=2k+1$:

$$\begin{aligned} 1+3+\cdots +(2k-1)+(2k+1) &= k^2+(2k+1) \\ &= k^2+2k+1 \\ &= (k+1)^2. \end{aligned}$$

The first equality uses the induction hypothesis. The last expression is exactly the claimed formula with $n=k+1$. Therefore $P(k)$ implies $P(k+1)$. Together with the base case, this proves the formula for every integer $n\geq 1$.

Why the base case and step prove all cases

The base case establishes the first instance. The inductive step says that whenever one instance is true, the next one is true. Starting at the base case, this carries truth to the next integer, then the one after that, and so on. This is why the statement must specify an appropriate starting value and why the step must work for an arbitrary allowed $k$, not just one numerical example.

If the formula begins at $n=0$, prove $P(0)$ and use $k\geq 0$ in the step. If the statement is intended only for $n\geq m$, prove $P(m)$ and establish the step for all $k\geq m$.

Common mistakes

• Skipping the base case: An inductive step alone does not establish that any case is true.
• Assuming what you need to prove: You may assume $P(k)$, but must derive $P(k+1)$ from it. Do not insert the claimed $k+1$ formula as an intermediate fact.
• Not showing where the hypothesis is used: In a sum proof, separate the last term and replace the earlier sum using $P(k)$.
• Using a special value of k: Checking that the step works for, say, $k=3$ is not a proof for arbitrary $k$.
• Losing the index range: Make sure the base case and the condition on $k$ match the domain of the claim.
• Stopping before the target form: Simplify until your expression is visibly the proposed closed form at $k+1$.

When applying this template to a particular problem, write down its exact formula for $P(n)$. The algebra in the inductive step depends on that formula; without it, only the general proof structure can be given.