Mathematical induction: five proof patterns and worked examples

Why induction proves infinitely many cases

To prove a statement $P(n)$ for every positive integer, establish $P(1)$ and prove that $P(k)$ implies $P(k+1)$ for an arbitrary positive integer $k$. The base case starts the chain; the implication carries it to every subsequent integer.

Despite its name, mathematical induction is deductive. Examining several cases may suggest a conjecture, but the implication and base case are what prove it. An argument that merely checks many examples leaves all later cases unresolved.

Three common forms move forward: ordinary induction, induction using two consecutive cases, and strong induction using all earlier cases. Two related techniques discussed below are descent and forward–backward induction. These are useful patterns rather than a list of every possible inductive argument.

1. Ordinary induction

Example: the sum of squares

Prove

$$\sum_{j=1}^nj^2=\frac{n(n+1)(2n+1)}6\quad(n\ge1).$$

At $n=1$, both sides equal one. Suppose the formula holds for $n=k$, where $k\ge1$. Adding the next square gives

$$\begin{aligned} \sum_{j=1}^{k+1}j^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 exactly the formula at $n=k+1$, so induction proves it. There is also a telescoping proof of the power-sum formulas. When writing a proof, make sure the algebra between the induction hypothesis and the desired expression is actually valid; knowing the target does not replace that calculation.

2. Induction using two consecutive cases

Example: integer reciprocal-power sums

Let $x\ne0$ and suppose $c=x+1/x$ is an integer. Prove $u_n=x^n+x^{-n}$ is an integer for every positive integer $n$.

The relation is

$$u_{n+2}=cu_{n+1}-u_n.$$

One previous case alone does not supply both terms needed on the right. Check two base cases: $u_1=c$ and $u_2=c^2-2$ are integers. If $u_k$ and $u_{k+1}$ are integers, the recurrence makes $u_{k+2}$ an integer. This proves all cases.

Equivalently, you could start with $u_0=2$ and $u_1=c$. Either choice works when its two base cases match the induction step.

3. Strong induction

Example: a sequence constrained by all preceding terms

Suppose every $a_n$ is positive and, for each $n\ge1$,

$$(a_1+\cdots+a_n)^2=a_1^3+\cdots+a_n^3.$$

Find the sequence. At $n=1$, positivity and $a_1^2=a_1^3$ give $a_1=1$. Subsequent small cases suggest $a_n=n$.

Assume $a_j=j$ for all $1\le j\le k$. Put $u=a_{k+1}$ and $T=k(k+1)/2$. Using the sums of integers and cubes, the condition at $k+1$ becomes

$$(T+u)^2=T^2+u^3,$$ $$u\{u^2-u-k(k+1)\}=u(u+k)(u-k-1)=0.$$

Since $u>0$, only $u=k+1$ is allowed. Strong induction gives $a_n=n$. Conversely, the known sum-of-cubes identity verifies that this sequence satisfies the original condition.

Here all earlier terms appear in the defining equation, so explicitly assuming their values is more natural than assuming only the last one.

4. Descent and the impossibility of decreasing forever

A descent argument often assumes a counterexample and constructs one with a smaller positive integer parameter. Choosing a smallest counterexample, or continuing toward an impossible base case, gives a contradiction. There cannot be an infinite strictly decreasing sequence of positive integers.

Example: consecutive Fibonacci numbers are coprime

Let $a_1=a_2=1$ and $a_{n+2}=a_{n+1}+a_n$. Suppose $a_k,a_{k+1}$ have a common divisor $d>1$. For $k\ge2$, their difference $a_{k-1}=a_{k+1}-a_k$ is also divisible by $d$. Repeating reduces the index until $d$ divides both $a_1$ and $a_2$, which is impossible because both are one. The case $k=1$ is already impossible.

Thus

$$\boxed{\gcd(a_n,a_{n+1})=1.}$$

The same conclusion can be written as a finite Euclidean descent:

$$\gcd(a_{k+1},a_k)=\gcd(a_k,a_{k-1})=\cdots=\gcd(1,1)=1.$$

The source calls this infinite descent; in this particular example the backwards propagation terminates directly at the initial pair.

5. Forward–backward induction

Sometimes it is easy to prove a statement at indices $2,4,8,16,\ldots$, and then propagate it backward one index at a time. To reach a chosen $n$, first select a power of two at least as large as $n$, then descend finitely many times.

Example: general AM–GM

For nonnegative real numbers $a_1,\ldots,a_n$, prove

$$\frac{a_1+\cdots+a_n}{n}\ge(a_1\cdots a_n)^{1/n}.$$

The two-term case follows from $(\sqrt{a_1}-\sqrt{a_2})^2\ge0$.

If the inequality holds for $m$ numbers, apply it separately to two groups of $m$, with arithmetic means $A,B$ and geometric means $G,H$. Then

$$\frac{A+B}{2}\ge\frac{G+H}{2}\ge\sqrt{GH}.$$

This is AM–GM for $2m$ numbers. Starting at two proves all powers of two.

Now suppose it holds for $k\ge3$ numbers, and take any $k-1$ nonnegative numbers with arithmetic mean $M$. Append $M$ as the $k$th number. The new arithmetic mean is still $M$, so

$$M^k\ge M\,a_1\cdots a_{k-1}.$$

If $M=0$, all the original numbers are zero and the desired result is immediate. If $M>0$, divide by $M$ to obtain $M^{k-1}\ge a_1\cdots a_{k-1}$. This proves the $k-1$ case. Together, doubling and backward steps reach every integer $n\ge2$; the case one is equality.

The source's diagram can be read as start at 2 → double to a sufficiently large power of two → step backward to the desired index. This textual version retains its logical structure without Japanese image labels. Equality holds exactly when all numbers are equal; see the AM–GM guide for a second proof and applications.

When induction is worth trying

Recurrences explicitly connect consecutive cases; divisibility problems often preserve an integer expression from one index to the next; inequalities may let you add or multiply an induction hypothesis to reach the next case. Work out the proposed step before committing to a proof template, so you know whether you need one base case, two, or all earlier cases.

State the proposition and index range, verify every required base case, define the arbitrary integer used in the step, and identify exactly where you use the hypothesis. A clear conclusion matters more than repeating a particular phrase. Merely announcing induction does not by itself justify a claim or guarantee examination credit.

Practice 1: powers of two real numbers

Let $a,b$ be real with $a^2+b^2=16$ and $a^3+b^3=44$.

1. Find $a+b$.
2. Prove that $a^n+b^n$ is an integer divisible by four for every integer $n\ge2$.

Set $s=a+b$, $p=ab$. Then $p=(s^2-16)/2$ and

$$44=s(16-p),\qquad s^3-48s+88=0.$$

Factorization gives

$$(s-2)(s^2+2s-44)=0, \qquad s=2,\ -1\pm3\sqrt5.$$

The numbers $a,b$ are real roots of $t^2-st+p=0$, so its discriminant must satisfy

$$s^2-4p=32-s^2\ge0.$$

For $s=2$ this is $28>0$. For $s=-1+3\sqrt5$, it is $-14+6\sqrt5<0$; for $s=-1-3\sqrt5$, it is $-14-6\sqrt5<0$. Thus only

$$\boxed{a+b=2,\qquad ab=-6}$$

is possible.

Put $u_n=a^n+b^n$. The base values $u_2=16$, $u_3=44$ are integers divisible by four, and

$$u_{n+2}=2u_{n+1}+6u_n.$$

If $u_k=4r$ and $u_{k+1}=4s$ with integers $r,s$, then $u_{k+2}=4(2s+6r)$. Two-step induction proves the result.

Practice 2: conjugate powers and an adjacent gcd

For $p=2+\sqrt5$, define $a_n=p^n+(-1/p)^n$ for $n\ge1$. Find $a_1,a_2$, express $a_1a_n$ using neighboring terms, prove integrality, and determine $\gcd(a_{n+1},a_n)$.

Because $-1/p=2-\sqrt5$, the two conjugates have sum four and product minus one. Therefore

$$a_1=4,\quad a_2=18,\quad a_{n+1}=4a_n+a_{n-1}\quad(n\ge2).$$

Equivalently, $a_1a_n=a_{n+1}-a_{n-1}$. The two initial values and recurrence prove that every term is a positive integer. Euclidean descent gives

$$\gcd(a_{n+1},a_n)=\gcd(a_n,a_{n-1})=\cdots=\gcd(18,4)=2.$$

The conjugate-power guide develops the full solution and related integer arguments.

Practice 3: an inequality forces a zero sequence

Suppose a real sequence satisfies

$$0\le3a_n\le\sum_{j=1}^na_j\quad(n\ge1).$$

Prove every term is zero. At $n=1$, $0\le3a_1\le a_1$ gives $a_1=0$. Assume the first $k$ terms vanish. At $k+1$ the condition reduces to

$$0\le3a_{k+1}\le a_{k+1},$$

which again forces $a_{k+1}=0$. Strong induction completes the proof. Keep the factor three: removing it would destroy the deduction.

Practice 4: choose signs to make a sum small

For each $n\ge1$, choose signs in

$$S_n=\pm1\pm\frac12\pm\cdots\pm\frac1n$$

so that $|S_n|\le1/n$.

For $n=1$, choose $S_1=1$. Suppose a choice satisfies $|S_k|\le1/k$. If $S_k\ge0$, choose the next term negative. Then

$$-\frac1{k+1}\le S_{k+1}=S_k-\frac1{k+1} \le\frac1k-\frac1{k+1}=\frac1{k(k+1)}\le\frac1{k+1}.$$

If $S_k\le0$, choose the next term positive. Similarly,

$$-\frac1{k+1}\le-\frac1{k(k+1)} \le S_{k+1}=S_k+\frac1{k+1}\le\frac1{k+1}.$$

Either choice works at zero. This proves the claim and gives a constructive strategy: choose each new sign opposite to the current sum.

For example, $1-1/2-1/3-1/4=-1/12$, whose absolute value is at most $1/4$. A construction avoids enumerating all $2^n$ sign combinations.

Practice 5: simultaneous induction for integral polynomials

Define

$$f_0(x)=1,\qquad f_{n+1}(x)=1+\int_0^xf_n(t)\,dt.$$

Find $f_n$, then prove that even-indexed functions are positive on the whole real line, while each odd-indexed function has exactly one real zero.

Computing a few cases suggests

$$f_n(x)=\sum_{j=0}^n\frac{x^j}{j!}.$$

The base $n=0$ is immediate. Integrating the finite sum at index $k$ and adding one produces precisely the sum at $k+1$, proving the formula.

The fundamental theorem of calculus gives $f_n'=f_{n-1}$ for $n\ge1$. The two desired properties support one another:

• If $f_{2m}>0$ everywhere, then $f_{2m+1}$ is strictly increasing. It is an odd-degree polynomial with positive leading coefficient, so its limits are $-\infty$ and $+\infty$. It has exactly one root $\alpha$, which is negative because its value at zero is one.
• The derivative of $f_{2m+2}$ is $f_{2m+1}$, so $f_{2m+2}$ decreases up to $\alpha$ and increases afterward. Its minimum is

$$f_{2m+2}(\alpha)=f_{2m+1}(\alpha)+\frac{\alpha^{2m+2}}{(2m+2)!} =\frac{\alpha^{2m+2}}{(2m+2)!}>0.$$

Starting with $f_0=1>0$ proves the odd case at one, the even case at two, and so on. This is simultaneous induction on two linked assertions. Choosing a statement strong enough to carry the next step is often the decisive part of an induction proof.