Mathematical Induction

Induction proves a family of statements by showing how an established case supports later cases. It does not mean checking many examples and guessing that the pattern continues. The main work is choosing the statement precisely, supplying enough initial cases, and proving a step whose dependencies are all justified.

We use $\mathbb N=\{0,1,2,\ldots\}$ throughout. A theorem beginning at $1$ proves a claim for $n\ge1$; it does not establish the $n=0$ case unless that case is supplied separately. Ordinary and strong induction are equivalent principles with different convenient forms of hypothesis [1][1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf.

State the principle with its starting index

TheoremOrdinary induction

Fix $n_0\in\mathbb N$ and a statement $P(n)$ for each integer $n\ge n_0$. Suppose:

1. $P(n_0)$ holds.
2. For every integer $k\ge n_0$, $P(k)$ implies $P(k+1)$.

Then $P(n)$ holds for every integer $n\ge n_0$.

We take induction as an available principle of the natural numbers. One can justify a formulation from another characterization, such as well-ordering, but that characterization must first be established.

The inductive step is a conditional proof: fix an arbitrary $k\ge n_0$, temporarily assume $P(k)$, and establish $P(k+1)$. We are not assuming that some convenient $k$ exists, and we are not assuming the entire conclusion for every $k$. The base case supplies the start; the step supplies every transition afterward.

An ordinary induction with a visible use of the hypothesis

PropositionThe sum of the first positive integers

For every integer $n\ge1$,

$$\sum_{i=1}^{n}i=\frac{n(n+1)}2.$$

The sum notation means adding the indicated terms, one for each integer index from $1$ through $n$. To extend the sum from $k$ terms to $k+1$ terms, separate the last term. That creates the exact expression to which the hypothesis applies.

Proof

For $n=1$, both sides equal $1$. Fix an arbitrary $k\ge1$ and assume

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

Then

$$\begin{aligned} \sum_{i=1}^{k+1}i &=\sum_{i=1}^{k}i+(k+1)\\ &=\frac{k(k+1)}2+(k+1)\\ &=\frac{(k+1)(k+2)}2. \end{aligned}$$

The second equality uses the inductive hypothesis. The last expression is the required formula with $n=k+1$. Therefore induction proves the statement for all integers $n\ge1$.

Before simplifying, write down the target for $k+1$. This makes it easier to detect an omitted last term or a final expression that still has the wrong index. A proof verifies a proposed formula; discovering the formula may require examples or a separate argument.

Strong induction: use whichever smaller cases are needed

TheoremStrong induction

Fix $n_0\in\mathbb N$. Prove $P(n_0)$. For every $k\ge n_0$, prove $P(k+1)$ under the hypothesis that $P(j)$ holds for all integers $n_0\le j\le k$. Then $P(n)$ holds for every integer $n\ge n_0$.

Strong induction is convenient when the next instance depends on several earlier indices, or on an index not known until the object is decomposed. It is not stronger in what it can prove. To recover it from ordinary induction, apply ordinary induction to the strengthened statement “$P(j)$ holds for every $n_0\le j\le n$.” Conversely, a strong hypothesis always includes the immediately preceding instance needed by ordinary induction.

PropositionEvery integer at least two is a product of primes

For every integer $n\ge2$, $n$ can be written as a finite product of prime numbers. A single prime counts as a product with one factor.

Proof

For $n=2$, the claim holds because $2$ is prime. Fix $k\ge2$ and assume the claim for all integers from $2$ through $k$. Consider $k+1$.

If $k+1$ is prime, the one-factor representation suffices. If it is composite, write $k+1=ab$ with $2\le a,b<k+1$. The strong hypothesis applies to both $a$ and $b$, so each is a product of primes. Multiplying those two representations gives the required representation of $k+1$.

Induction proves the claim for every $n\ge2$.

The factors need not equal $k$, which is why having all smaller cases available is convenient. This establishes existence of a prime factorization, not uniqueness; uniqueness is a separate theorem.

Recurrences tell us how many base cases are needed

ExampleA recurrence using two earlier terms

Suppose $a_0=4$, $a_1=6$, and

$$a_{n+1}=2a_n-a_{n-1}\qquad(n\ge1).$$

The first terms suggest $a_n=2n+4$. Because the recurrence uses two preceding terms, both starting values need checking.

Proof

The formula holds for $n=0$ and $n=1$. Fix $k\ge1$ and assume it holds for every index from $0$ to $k$. In particular, it holds at $k$ and $k-1$, so

$$\begin{aligned} a_{k+1}&=2(2k+4)-\bigl(2(k-1)+4\bigr)\\ &=2k+6\\ &=2(k+1)+4. \end{aligned}$$

Thus the formula holds for all $n\ge0$ by strong induction with the two checked initial cases.

One may instead use ordinary induction on a statement containing two consecutive identities. The useful question is which earlier facts a step consumes, not whether its heading says “ordinary” or “strong.” The restriction $k\ge1$ keeps the reference to $a_{k-1}$ inside the defined sequence.

Diagnose gaps before doing more algebra

Gap	Why the argument fails
Only the base case is shown	No transition reaches larger indices
Only the inductive implication is shown	A chain of implications may have no true starting case
The step assumes $P(k+1)$	The target has been used as an unproved premise
The step proves $P(k)\to P(k+2)$	One base case reaches only one parity class
The step uses $P(k-1)$ at $k=0$	It calls a case outside the available range
The step works only after an extra threshold	All earlier indices up to that threshold need coverage

For example, let $P(n)$ be “$n$ is even.” Both $P(0)$ and the implication $P(k)\to P(k+2)$ hold, but they do not prove every natural number even. Missing reachability, rather than difficult arithmetic, is the problem.

Induction can also prove inequalities, divisibility, or properties of recursively defined objects. The object must reduce according to an appropriate well-founded structure; the natural-number principles here are not automatically proofs over arbitrary real numbers. For an algorithm, correctness and termination may require separate arguments even when both use induction.

Exercises: ordinary induction and counting

ExerciseThe first odd numbers

For every $n\in\mathbb N$, prove

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

Use the convention that the empty sum at $n=0$ equals zero. Decide whether ordinary induction is sufficient.

Show solution

Solution

At $n=0$, both sides are zero. Assume the formula at an arbitrary $k\ge0$. The next term is $2(k+1)-1=2k+1$, so

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

Only the immediately preceding sum was used, so ordinary induction suffices. The last term for $k+1$ terms is $2k+1$, not $2k+3$.

ExerciseSquare sums and the checkerboard

Prove, for integers $n\ge1$,

$$\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}6.$$

Use it to count all axis-aligned squares whose edges follow the grid lines of an $n$-by-$n$ checkerboard.

Show solution

Solution

The base case $n=1$ gives $1$. Assuming the formula at $k\ge1$, add the next square:

$$\begin{aligned} \sum_{i=1}^{k+1}i^2 &=\frac{k(k+1)(2k+1)}6+(k+1)^2\\ &=\frac{(k+1)(2k^2+7k+6)}6\\ &=\frac{(k+1)(k+2)(2k+3)}6. \end{aligned}$$

This is the required formula at $k+1$. A square of side length $s$ grid units has $(n-s+1)^2$ possible positions, so the total is

$$\sum_{s=1}^{n}(n-s+1)^2=\sum_{i=1}^{n}i^2.$$

For an $8$-by-$8$ board this equals $8\cdot9\cdot17/6=204$. Restricting the count to grid-aligned squares specifies exactly which objects are being counted.

ExerciseSquares of odd numbers

For $n\in\mathbb N$, prove

$$\sum_{i=1}^{n}(2i-1)^2=\frac{n(2n-1)(2n+1)}3.$$

Show solution

Solution

The case $n=0$ has both sides zero. If the formula holds at $k\ge0$, adding $(2k+1)^2$ gives

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

This is the formula at $k+1$, completing the induction.

ExerciseAn inequality

Prove $2^n\ge n+1$ for every $n\in\mathbb N$.

Show solution

Solution

At $n=0$, both sides equal $1$. Assume $2^k\ge k+1$ with $k\ge0$. Multiplying by the positive number $2$ preserves the inequality, so

$$2^{k+1}\ge2(k+1)\ge k+2.$$

The second inequality uses $k\ge0$. The last bound is the target at $k+1$, so induction applies.

Exercises: preserve parameters and indices

ExerciseA telescoping sum can also be proved inductively

For $n\ge1$, prove

$$\sum_{i=1}^{n}\frac1{(2i-1)(2i+1)}=\frac{n}{2n+1}.$$

Show solution

Solution

The base case gives $1/3$. At the next index, use the hypothesis and combine fractions:

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

This is the target at $k+1$. Alternatively,

$$\frac1{(2i-1)(2i+1)} =\frac12\left(\frac1{2i-1}-\frac1{2i+1}\right)$$

makes the finite sum telescope directly. The two methods establish the same identity using different organizations.

ExerciseKeep one parameter fixed

Fix an integer $q\ge0$. For every integer $n\ge1$, prove

$$\sum_{j=1}^{n}j(j+1)\cdots(j+q) =\frac{n(n+1)\cdots(n+q+1)}{q+2}.$$

When $q=0$, the summand is just $j$.

Show solution

Solution

Hold $q$ fixed throughout the induction on $n$. At $n=1$, cancellation of $q+2$ on the right gives $1\cdot2\cdots(q+1)$, the left side. If the formula holds at $k$, factor the new sum as

$$\begin{aligned} &\frac{k(k+1)\cdots(k+q+1)}{q+2} +(k+1)\cdots(k+q+1)\\ &\qquad=(k+1)\cdots(k+q+1) \left(\frac{k}{q+2}+1\right)\\ &\qquad=\frac{(k+1)\cdots(k+q+2)}{q+2}. \end{aligned}$$

The denominator is nonzero because $q\ge0$, and the result is the target at $k+1$. Since the fixed $q$ was arbitrary, the identity holds for every allowed parameter.

ExerciseA weighted geometric sum

Fix a real number $r\ne1$. Prove for all $n\in\mathbb N$ that

$$\sum_{j=0}^{n}(j+1)r^j =\frac{[(r-1)n+(r-2)]r^{n+1}+1}{(r-1)^2}.$$

The constant term is $1$, including when $r=0$. Recover the cases $r=2$ and $r=3$, and handle $r=1$ separately.

Show solution

Solution

At $n=0$, the right numerator is $(r-2)r+1=(r-1)^2$, giving $1$. Define $A_k=(r-1)k+(r-2)$. The coefficient identity

$$A_{k+1}r-A_k=(k+2)(r-1)^2$$

follows by expansion. Write $S_n$ for the sum on the left. Under the inductive hypothesis at $k\ge0$,

$$S_k=\frac{A_k r^{k+1}+1}{(r-1)^2}.$$

The new term is $(k+2)r^{k+1}$. Substituting this expression for $S_k$ and using the coefficient identity gives

$$\begin{aligned} S_{k+1}&=S_k+(k+2)r^{k+1}\\ &=\frac{A_{k+1}r^{k+2}+1}{(r-1)^2}. \end{aligned}$$

This is the formula at $k+1$. In particular,

$$\sum_{j=0}^{n}(j+1)2^j=n2^{n+1}+1,$$$$\sum_{j=0}^{n}(j+1)3^j=\frac{(2n+1)3^{n+1}+1}{4}.$$

For $r=1$, use the direct integer-sum formula to obtain $(n+1)(n+2)/2$; substituting into the displayed quotient would divide by zero. The proof also fixes a common indexing error: the added coefficient is $k+2$, not $k+1$.

Continue from the proof to the structure

For each induction, state the precise range, identify the base cases, and name the earlier instances consumed by the step. Number Systems, Algorithms, and Recursion connects these dependencies to recursive definitions; Sets, Functions, Sequences, and Summation develops the notation used in the examples.

References

1. [1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf ↩