2.1 Mathematical induction

Motivation

Many mathematical claims describe an infinite family of cases. The identity

$$1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}2\right)^2$$

contains one assertion for every positive integer $n$. Checking $n=1,2,3,4$ may reveal the pattern, but no finite list of checks proves all its cases. Mathematical induction supplies the missing logical link: establish a starting case, then prove that truth propagates through every required transition.

The statement, the base, and the legal step

Definition

Indexed proposition and ordinary induction data

An indexed proposition $P(n)$ is a statement with a definite truth value for each integer $n$ in a declared range. An ordinary induction proof on $n\ge n_0$ contains:

1. the base case $P(n_0)$;
2. the induction hypothesis $P(k)$ for an arbitrary $k\ge n_0$; and
3. the induction step $P(k)\Rightarrow P(k+1)$.

The hypothesis is assumed only inside the step. The conclusion is obtained only after invoking the induction principle.

Definition

Step size, consecutive bases, and strong hypotheses

For $d\in\mathbb Z^+$, a step-size-$d$ induction proves $P(k)\Rightarrow P(k+d)$. It reaches only the residue class of its starting value, so all claimed residue classes need bases. A consecutive-base induction begins with several adjacent cases and uses the corresponding window of hypotheses, as for $P(k),P(k+1)\Rightarrow P(k+2)$. In strong induction, the step to $k+1$ may use every earlier case $P(n_0),\ldots,P(k)$.

Definition

Forward-backward induction

Forward-backward induction starts from $P(1)$ and uses two implications:

$$P(k)\Rightarrow P(2k)\quad(k\ge1), \qquad P(k)\Rightarrow P(k-1)\quad(k\ge2).$$

The doubling move reaches powers of two; the backward move fills every gap below such a power.

For an existential claim, $P(n)$ must retain the quantifier. For example, in a coin problem the statement is not merely $n=3a+5b$, but “there exist $a,b\in\mathbb Z_{\ge0}$ such that $n=3a+5b$.” For a statement about arbitrary real inputs, $P(n)$ must also quantify those inputs and preserve every domain condition.

Why induction reaches every required index

Theorem

Ordinary induction from an arbitrary start

Let $n_0\in\mathbb Z$, and let $P(n)$ be defined for every integer $n\ge n_0$. If $P(n_0)$ is true and, for every integer $k\ge n_0$, $P(k)\Rightarrow P(k+1)$, then $P(n)$ is true for every $n\ge n_0$.

Theorem

Step-size and consecutive-base induction

Let $d\in\mathbb Z^+$ and $n_0\in\mathbb Z$, and let $P(n)$ be defined for every integer $n\ge n_0$. If $P(n_0),\ldots,P(n_0+d-1)$ are true and, for every $k\in\mathbb Z$ with $k\ge n_0$, $P(k)\Rightarrow P(k+d)$, then $P(n)$ is true for every $n\ge n_0$. More generally, if $P(1),\ldots,P(d)$ are true and, for every $k\in\mathbb Z$ with $k\ge1$, the $d$ statements $P(k),\ldots,P(k+d-1)$ imply $P(k+d)$, then $P(n)$ holds for every positive integer $n$.

Theorem

Strong induction

Let $n_0\in\mathbb Z$, and let $P(n)$ be defined for every integer $n\ge n_0$. Suppose $P(n_0)$ is true and, for every integer $k\ge n_0$, the joint assumption $P(n_0),P(n_0+1),\ldots,P(k)$ implies $P(k+1)$. Then $P(n)$ is true for every $n\ge n_0$.

Theorem

Forward-backward induction

Let $P(n)$ be defined for $n\in\mathbb Z^+$. If $P(1)$ is true, $P(k)\Rightarrow P(2k)$ for $k\ge1$, and $P(k)\Rightarrow P(k-1)$ for $k\ge2$, then $P(n)$ is true for every positive integer $n$.

Reachability and the least-counterexample argument

Ordinary induction can be justified by the least-counterexample principle. If some $P(n)$ with $n\ge n_0$ were false, choose the least false index $m$. The base case gives $m\ne n_0$, so $m-1\ge n_0$. Minimality makes $P(m-1)$ true, and the induction step then makes $P(m)$ true, a contradiction. Strong induction has the same logic: minimality supplies every earlier case required by the stronger hypothesis.

For step size $d$, draw $d$ separate chains. Starting from $r$, the implication reaches $r+d,r+2d,\ldots$ and no other residue class. For a two-term recurrence, two bases seed a sliding window: $P(1),P(2)$ give $P(3)$; then $P(2),P(3)$ give $P(4)$, in the declared order.

Forward-backward induction requires an explicit reachability argument. Given a target $n$, choose $r\in\mathbb Z_{\ge0}$ with $2^r\ge n$. Repeated doubling gives $P(1),P(2),P(4),\ldots,P(2^r)$. Repeated decrementing then gives $P(2^r-1),\ldots,P(n)$. Every backward step begins at an index at least $2$, so its hypothesis is respected.

Choosing the hypothesis to match the recurrence

Proof: The dependencies in the sum-of-cubes proof

Goal and base. For $n\in\mathbb Z^+$, let $P(n)$ be $\sum_{r=1}^n r^3=n^2(n+1)^2/4$. At $n=1$, both sides equal $1$.

Hypothesis and target. Fix an arbitrary integer $k\ge1$ and assume $P(k)$. The target is $P(k+1)$, not another rearrangement of $P(k)$.

Legal move and dependency. Separate the last summand, use the hypothesis only for the sum through $k$, and then factor:

$$\sum_{r=1}^{k+1}r^3 =\underbrace{\sum_{r=1}^{k}r^3}_{\text{use }P(k)}+(k+1)^3 =\frac{(k+1)^2}{4}\bigl(k^2+4(k+1)\bigr) =\frac{(k+1)^2(k+2)^2}{4}.$$

Boundary and closing. The split is valid for every $k\ge1$, including the first transition $1\to2$. The final expression is exactly the target; the base and this arbitrary-$k$ step prove every $P(n)$ by ordinary induction.

Worked example

1. Ordinary induction: a divisibility claim

Let $P(n)$ assert $3\mid(n^3-n)$ for $n\in\mathbb Z^+$. The base is $1^3-1=0=3\cdot0$. For an arbitrary integer $k\ge1$, assume $k^3-k=3q$ with $q\in\mathbb Z$. Then

$$(k+1)^3-(k+1)=3(q+k^2+k),$$

so the next value is again divisible by $3$. Induction proves the claim for every positive integer $n$; the witness $q$ makes the hypothesis precise.

Worked example

2. A trigonometric telescoping identity with its domain

For each $n\ge1$, let $P(n)$ assert that, for every real $x$ satisfying $\sin(jx)\ne0$ for $j=1,\ldots,n+1$,

$$\sum_{r=1}^{n}\frac1{\sin(rx)\sin((r+1)x)} =\frac{\sin(nx)}{\sin^2x\sin((n+1)x)}.$$

The case $n=1$ follows by cancellation, permitted because $\sin x\ne0$. For the step, an $x$ admissible for $k+1$ is also admissible for $k$. Add the new term and use

$$\sin(kx)\sin((k+2)x)+\sin^2x=\sin^2((k+1)x).$$

After cancellation by the declared nonzero factors, the result is $\sin((k+1)x)/(\sin^2x\sin((k+2)x))$. Thus both the formula and every division are justified.

Worked example

3. An arbitrary starting index

Let $P(n)$ be $n^2\lt2^n$ for $n\ge5$. The base is $25\lt32$. If $k^2\lt2^k$ and $k\ge5$, then $2k+1\lt k^2$, so

$$(k+1)^2=k^2+2k+1\lt2k^2\lt2^{k+1}.$$

The proof starts at $5$ because the displayed estimate and the claim are both needed only from that index onward.

Counterexample mode

Repeating a hypothesis proves no next case

Consider the false claim $Q(n):n^2\lt2^n$ for every positive integer $n$. $Q(1)$ is true since $1\lt2$, but $Q(2)$ is false since $4=4$; $n=3,4$ also fail, giving $9\gt8$ and $16=16$. Nevertheless, $Q(k)\Rightarrow Q(k)$ is true for every $k$: it merely repeats the assumption. Thus a true base and this implication cannot replace an induction step; initial checks alone also supply no transition.

The repair is the preceding example's claim for $n\ge5$: verify $25\lt32$, then prove $Q(k)\Rightarrow Q(k+1)$ for every integer $k\ge5$, using $2k+1\lt k^2$. Both the domain and the next-case obligation matter.

Worked example

4. Two consecutive bases for a second-order linear recurrence

Put $\alpha=3+\sqrt5$, $\beta=3-\sqrt5$, and $a_n=\alpha^n+\beta^n$. Since $\alpha+\beta=6$ and $\alpha\beta=4$,

$$a_{n+2}=6a_{n+1}-4a_n.$$

Now $a_1=6$ and $a_2=28$. If $a_k=2^kM$ and $a_{k+1}=2^{k+1}N$ for integers $M,N$, then

$$a_{k+2}=2^{k+2}(3N-M).$$

Hence $2^n\mid a_n$ for all $n\ge1$. Two bases are indispensable because the recurrence uses two preceding values.

Worked example

5. Three residue classes in the coin problem

For $t\in\mathbb Z_{\ge8}$, let $P(t)$ mean that $t=3a+5b$ for some $a,b\in\mathbb Z_{\ge0}$. The bases

$$8=3+5,\qquad9=3+3+3,\qquad10=5+5$$

cover all residues modulo $3$. If $P(t)$ holds, adding one $3$-cent coin proves $P(t+3)$. The three chains beginning at $8,9,10$ therefore prove that every integer amount $t\ge8$ is payable. Merely checking the three bases without naming the step and the residue classes would leave the coverage unexplained.

Worked example

6. Strong induction: prime products and distinct powers of two

For prime products, let $P(n)$ assert only existence of a factorization for $n\ge2$. The base $2$ is prime. If all values from $2$ through $k$ have such a factorization, then $k+1$ is prime, or $k+1=ab$ with $2\le a,b\le k$; factor $a$ and $b$ by the strong hypothesis. This proves existence, not uniqueness.

For distinct powers of two, let $P(n)$ assert that $n$ is a sum of distinct nonnegative powers of two. The base is $P(1)$ because $1=2^0$. Assume $P(1),\ldots,P(k)$, choose the largest $2^\ell\le k+1$ with $\ell\in\mathbb Z_{\ge0}$, and put $m=k+1-2^\ell$. If $m=0$, the one-term representation is complete. If $m\ge1$, then $m\le k$ and strong induction represents $m$; moreover $m\lt2^\ell$, so none of its powers equals $2^\ell$. Thus adjoining $2^\ell$ preserves distinctness. The separate $m=0$ case is necessary because $P(0)$ was never assumed.

Worked example

7. Exactly how many chocolate-bar breaks?

Let $n,m\in\mathbb Z^+$. Assume one break selects one existing rectangular piece, with no stacking or simultaneous cuts, and splits it along a grid line into two pieces. Starting from one piece, each break raises the piece count by exactly one, so reaching $nm$ unit squares needs at least $nm-1$ breaks. This bound is attainable: make $n-1$ horizontal breaks to obtain $n$ rows, then make $m-1$ breaks within each row. The total is

$$(n-1)+n(m-1)=nm-1.$$

Equivalently, induction on $n+m$ splits the bar first and applies the result to the two smaller rectangles. The invariant proves necessity; the construction proves sufficiency.

Worked example

8. Forward-backward induction for the mean-square inequality

Let $P(n)$ be the universal statement that every $n$-tuple of positive reals satisfies

$$\left(\frac{x_1+\cdots+x_n}{n}\right)^2 \le\frac{x_1^2+\cdots+x_n^2}{n}.$$

$P(1)$ is equality. For $k\ge1$, to obtain $P(2k)$ from $P(k)$, split the $2k$ numbers into two blocks, apply $((u+v)/2)^2\le(u^2+v^2)/2$ to their means, then apply $P(k)$ to each block. For $k\ge2$, to obtain $P(k-1)$ from $P(k)$, append to $x_1,\ldots,x_{k-1}$ their mean $\mu$. Applying $P(k)$ gives

$$\mu^2\le\frac{\sum_{i=1}^{k-1}x_i^2+\mu^2}{k}, \qquad (k-1)\mu^2\le\sum_{i=1}^{k-1}x_i^2.$$

Dividing the last inequality by $k-1>0$ gives $\mu^2\le\sum_{i=1}^{k-1}x_i^2/(k-1)$, exactly $P(k-1)$. The reachability argument now proves every $P(n)$. If $\mu$ is the mean of $x_1,\ldots,x_n$, then

$$\frac1n\sum_{i=1}^n x_i^2-\mu^2 =\frac1n\sum_{i=1}^n(x_i-\mu)^2,$$

so equality holds exactly when $x_1=\cdots=x_n$.

Common Mistakes

Common mistake

The false horse proof loses overlap at the first step

The alleged proof that all horses have the same colour compares $\{h_1,\ldots,h_n\}$ and $\{h_2,\ldots,h_{n+1}\}$. They overlap only for $n\ge2$. At the required transition $P(1)\Rightarrow P(2)$, the two singleton sets are disjoint, so no common horse transfers a colour between them. A true base with a broken first transition starts no chain.

Common mistake

The step may not reach every claimed index

A $k\mapsto k+2$ step with only $P(1)$ proves odd indices, not even ones. A two-term recurrence cannot begin from one base. List the reachable indices before claiming the conclusion.

Common mistake

Domain conditions and quantifiers belong to P(n)

Cancelling a sine without excluding its zeros, applying a strong hypothesis to $0$ when it begins at $1$, or proving one convenient input tuple when the claim says “every tuple” changes the proposition. State these restrictions before the induction starts.

Checkpoint

Q1. A proof has P(2) and P(k) implies P(k+2). Which positive indices are established?

Trace the reachable residue class rather than guessing from the notation.

Checkpoint

Q2. In the distinct-powers proof, why must the remainder m=0 be separated?

Compare the range of the strong induction hypothesis with the remainder.

Summary

Induction proves an infinite indexed claim by combining verified seeds with a transition that reaches every desired index. Ordinary induction advances by one; arbitrary-start induction begins at the first claimed case; step-size induction needs every relevant residue; consecutive-base induction matches a multi-term recurrence; strong induction permits any earlier case; and forward-backward induction doubles to a large power of two and then descends.

The reliable workflow is: define $P(n)$ with its quantifiers and domain, state the start, verify all bases, declare an arbitrary $k$ in range, use only the available hypotheses, prove the exact target, check reachability, and invoke the matching theorem. Edge cases such as zero remainders, vanished denominators, or a missing first transition are logical parts of the proof.

Exercises

1. For $n\in\mathbb Z^+$, prove the following statements by induction; in (e), prove the stronger claim for $n\in\mathbb Z_{\ge0}$. In (e) and (f), first prove the cross-multiplied identity, which is valid for every real angle; state the extra nonzero-denominator condition for the quotient form.

   (a) $\displaystyle\sum_{r=1}^n r(r+1)(r+2)=\frac14n(n+1)(n+2)(n+3)$.

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

   (c) $5\mid(3^{2n}-2^{2n})$.

   (d) $64\mid(9^n-8n-1)$.

   (e) $\displaystyle 2^{n+1}\sin\theta\prod_{r=0}^n\cos(2^r\theta) =\sin(2^{n+1}\theta)$.

   (f) $\displaystyle \sin\frac{x}{2}\sum_{r=1}^n\sin(rx) =\sin\frac{(n+1)x}{2}\sin\frac{nx}{2}$.

   Thus, when $\sin\theta\ne0$, (e) may be divided by $2^{n+1}\sin\theta$ to obtain the corresponding quotient of sines. When $\sin(x/2)\ne0$, (f) may similarly be divided by $\sin(x/2)$.

2. A right triomino is an L-shape made from three edge-adjacent unit squares. Prove that a $2^n\times2^n$ checkerboard with any one square removed can be tiled by right triominoes for every $n\in\mathbb Z^+$.

3. Use step-size-$2$ induction to prove: (a) $23\mid(12^n-11^n)$ for every positive even $n$; (b) $11\mid(7^n+4^n)$ for every positive odd $n$.

4. Let $x\in\mathbb R\setminus\{0\}$ and suppose $s=x+x^{-1}$ is an integer. Prove that $x^n+x^{-n}$ is an integer for every $n\in\mathbb Z_{\ge0}$.

5. Prove that every postage amount of at least $12$ cents can be formed from $4$-cent and $5$-cent stamps.

6. With $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ for $n\ge0$, prove that every natural number is a Fibonacci number or a sum of distinct positive Fibonacci values; the repeated value $F_1=F_2=1$ counts only once. Prove existence only.

7. For the same Fibonacci sequence, prove: (a), for $n\ge0$, $\sum_{i=0}^nF_i^2=F_nF_{n+1}$; (b) $F_nF_m+F_{n+1}F_{m+1}=F_{n+m+1}$ for $m,n\ge0$; and (c), if $\phi\gt\psi$ are the roots of $t^2-t-1=0$, then, for $n\ge0$, $F_n=(\phi^n-\psi^n)/\sqrt5$.

8. For $m,n\in\mathbb Z^+$ and nonnegative real numbers $x_1,\ldots,x_n$, prove

$$\left(\frac{x_1+\cdots+x_n}{n}\right)^m \le\frac{x_1^m+\cdots+x_n^m}{n}.$$

Solutions

Solution · Quick-check Q1

Only the positive even indices $2,4,6,\ldots$ are reached. A base in the odd residue class would be needed to prove odd indices as well.

Solution · Quick-check Q2

The strong hypothesis covers positive integers through $k$, not $0$. When $m=0$, use the one-term representation $k+1=2^\ell$ directly.

Solution · Solution 1

(a) At $n=1$, both sides are $6$. Add $(k+1)(k+2)(k+3)$ to the induction hypothesis and factor $\tfrac14(k+1)(k+2)(k+3)(k+4)$. (b) The base is $1/3=1/3$. If the sum through $k$ is $k/(2k+1)$, then adding the next term gives $k/(2k+1)+1/((2k+1)(2k+3))=(k+1)/(2k+3)$. The partial fraction $1/((2r-1)(2r+1))=\tfrac12(1/(2r-1)-1/(2r+1))$ also gives the same endpoint formula. Evaluating the first two terms provides a quick check on the endpoint.

(c) The base is $9-4=5$; and $3^{2(k+1)}-2^{2(k+1)}=9(3^{2k}-2^{2k})+5\cdot2^{2k}$. (d) At the base $n=1$, the expression is $9-8-1=0$; subtracting the $k$ expression gives $9^{k+1}-8(k+1)-1-(9^k-8k-1)=8(9^k-1)$, divisible by $64$ because $9^k-1$ is divisible by $8$.

(e) We prove the stronger range $n\ge0$. Its base is $2\sin\theta\cos\theta=\sin2\theta$; multiply the $k$ identity by $2\cos(2^{k+1}\theta)$. The quotient formula requires $\sin\theta\ne0$. (f) At $n=1$, both sides equal $\sin(x/2)\sin x$. After applying the hypothesis and adding $\sin((k+1)x)$, use

$$\sin\frac{(k+1)x}{2} \left(\sin\frac{(k+2)x}{2}-\sin\frac{kx}{2}\right) =\sin\frac{x}{2}\sin((k+1)x).$$

The quotient form requires $\sin(x/2)\ne0$.

Solution · Solution 2

For $n=1$, the three remaining squares of a $2\times2$ board form one right triomino. Divide a $2^{k+1}\times2^{k+1}$ board into four $2^k\times2^k$ quadrants. One contains the removed square. Place one central triomino over the central square of each other quadrant. Every quadrant now has exactly one square missing, so the induction hypothesis tiles all four.

Solution · Solution 3

(a) Start at $n=2$, where $12^2-11^2=23$. If the claim holds at an even $k$, then $12^{k+2}-11^{k+2}=121(12^k-11^k)+23\cdot12^k$, so it holds at $k+2$. (b) Start at $n=1$, where $7+4=11$. If it holds at an odd $k$, then $7^{k+2}+4^{k+2}=16(7^k+4^k)+33\cdot7^k$, so it holds at $k+2$.

Solution · Solution 4

Set $a_n=x^n+x^{-n}$. Then $a_0=2$, $a_1=s$, and direct multiplication gives $a_{n+2}=sa_{n+1}-a_n$. Two consecutive-base induction now shows $a_n\in\mathbb Z$ for all $n\ge0$.

Solution · Solution 5

Use bases $12=3\cdot4$, $13=2\cdot4+5$, $14=4+2\cdot5$, and $15=3\cdot5$. If an amount $t$ is possible, adding a $4$-cent stamp makes $t+4$ possible. These four residue-class chains cover every integer at least $12$.

Solution · Solution 6

The case $0=F_0$ is immediate. For $n\gt0$, use strong induction. Choose the largest Fibonacci value $F_j\le n$. If $n=F_j$, stop. Otherwise $r=n-F_j$ satisfies $0\lt r\lt F_{j-1}$ because $n\lt F_{j+1}=F_j+F_{j-1}$. By induction, $r$ is a Fibonacci value or a sum of distinct such values, all smaller than $F_{j-1}$; adjoining $F_j$ keeps the summands distinct. This establishes existence, without asserting uniqueness.

Solution · Solution 7

(a) The base $n=0$ is immediate. Adding $F_{k+1}^2$ gives $F_kF_{k+1}+F_{k+1}^2=F_{k+1}F_{k+2}$.

(b) Fix $n$. At $m=0$ both sides are $F_{n+1}$, and at $m=1$ both are $F_{n+2}$. If the formula holds for $m$ and $m+1$, adding the two left sides gives the left side for $m+2$, while adding $F_{n+m+1}$ and $F_{n+m+2}$ gives $F_{n+m+3}$.

(c) Since each root $u$ satisfies $u^{k+2}=u^{k+1}+u^k$, the proposed formula obeys the Fibonacci recurrence. Its values at $n=0,1$ are $0,1$ because $\phi-\psi=\sqrt5$. Two consecutive bases finish the proof.

Solution · Solution 8

First prove by induction on $m$ that $(u+v)^m\le2^{m-1}(u^m+v^m)$ for $u,v\ge0$. At $m=1$ there is equality. Assume the result at $m$ and multiply it by $u+v$; in the step, use $u^mv+uv^m\le u^{m+1}+v^{m+1}$, equivalent to $(u-v)(u^m-v^m)\ge0$. Hence

$$(u+v)^{m+1} \le2^{m-1}(u^m+v^m)(u+v) \le2^m(u^{m+1}+v^{m+1}).$$

Thus the displayed inequality holds for every $m\in\mathbb Z^+$. Returning to that exponent-$m$ inequality and dividing it by $2^m$ gives

$$\left(\frac{u+v}{2}\right)^m\le\frac{u^m+v^m}{2}.$$

Now repeat the forward-backward proof from Worked Example 8: split $2k$ inputs into equal blocks for the doubling step; for the backward step, append the mean of the first $k-1$ inputs. Choose $2^r\ge n$, double from $1$ to $2^r$, and decrement to $n$. Equality is automatic when $n=1$ or $m=1$. When $n\ge2$ and $m\ge2$, strict convexity (or the equality conditions in the binary step) shows that equality holds exactly when all $x_i$ are equal.