More Examples of Induction

Induction is more than a summation trick. Once the principle is in your hands, the same two-step ritual proves divisibility theorems, polynomial inequalities, geometric-series formulas, and product identities. The hard part is no longer the logic, that's settled by Section 6.1, but the algebra: how do you reshape $P(k+1)$ until the inductive hypothesis can be plugged in? This section is a tour of the algebraic moves that show up over and over: factoring out a common piece, peeling off the last term, bounding a sum by its largest summand. Walk through each example with pen in hand and the pattern starts to feel mechanical.

Divisibility by induction

To prove $d \mid f(n)$ for all $n \geq n_0$, assume $d \mid f(k)$ and arrange $f(k+1)$ so a multiple of $d$ pops out. The most common move is to write $f(k+1) = (\text{something involving } f(k)) + (\text{a multiple of } d)$. Example: prove $3 \mid (4^n - 1)$ for every $n \geq 1$.

Base ($n = 1$): $4 - 1 = 3$, divisible by 3. $\checkmark$

Step: assume $4^k - 1 = 3m$ for some integer $m$. Then $4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(3m + 1) - 1 = 12m + 3 = 3(4m + 1)$, which is divisible by 3. $\blacksquare$

Inequality by induction

Bernoulli's inequality: for $x \geq -1$ and $n \geq 1$, $(1+x)^n \geq 1 + nx$. (The boundary case $x = -1$ holds because the left side is $0$ and the right side is $1 - n \leq 0$.)

Base ($n = 1$): $(1+x)^1 = 1 + x = 1 + 1 \cdot x$. $\checkmark$

Step: assume $(1+x)^k \geq 1 + kx$. Multiply both sides by the non-negative quantity $(1+x)$:

The last step uses $kx^2 \geq 0$. $\blacksquare$

The geometric sum

For $r \neq 1$ and $n \geq 0$, $\sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1}$.

Base ($n = 0$): left side $= r^0 = 1$; right side $= \frac{r - 1}{r - 1} = 1$. $\checkmark$

Step: assume $\sum_{i=0}^{k} r^i = \frac{r^{k+1} - 1}{r - 1}$. Add $r^{k+1}$ to both sides:

That is the formula at $n = k+1$. $\blacksquare$

Pause and think: in the divisibility example above we wrote $4^{k+1} = 4 \cdot 4^k$, a tiny algebraic move that unlocks the whole step. What if we had used $4^{k+1} = 4^k + 4^k + 4^k + 4^k$ instead? Would the proof still go through? Try it.

Try it

• Predict $\sum_{i=1}^{10} i^2$ using the closed form $\frac{n(n+1)(2n+1)}{6}$. Then verify by computing $1 + 4 + 9 + \cdots + 100$ in your head or on paper.
• Before checking: is $5 \mid (6^n - 1)$ for every $n \geq 1$? Test $n = 1, 2, 3$ by hand. Then sketch the induction.
• Bernoulli check: at $x = 0.1$ and $n = 5$, compute $(1.1)^5$ to four decimals. Is it at least $1 + 5(0.1) = 1.5$?
• Geometric sum at $r = 2$: predict $\sum_{i=0}^{n} 2^i$ at $n = 4$ using the closed form, then add the terms by hand.

A trap to watch for

The most seductive mistake in induction proofs is the "all horses are the same colour" fallacy. The argument runs: base case, one horse is obviously the same colour as itself. Inductive step, given any group of $k+1$ horses, remove one to get a group of $k$ which by hypothesis are all the same colour; remove a different one to get another group of $k$ same-coloured horses; the overlap forces the whole $k+1$ to share a colour. The conclusion is absurd. Where is the bug? The inductive step silently assumes the two sub-groups overlap, i.e., that $k \geq 2$. The implication $P(1) \Rightarrow P(2)$ is the link that breaks. Moral: when the inductive step relies on a structural assumption (overlap, splitting, non-degeneracy), check that the assumption holds at the very first transition out of the base case.

What you now know

You can pick the right algebraic move in an induction proof: factor for divisibility, multiply for inequalities, add the next term for sums. You've seen Bernoulli's inequality and the geometric-sum formula and you understand why subtle assumptions inside the inductive step (like the overlap in the horse-colour fallacy) must be verified at the first transition. Next we'll see how induction extends naturally to recursive definitions, where a function's value at $n$ is computed from earlier values.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, Section 6.2.
• Graham, R. L., Knuth, D. E., Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley, Sections 1.2–1.4.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, app. A.
• Wilf, H. S. (1994). generatingfunctionology. Academic Press, ch. 1.
• Aigner, M., Ziegler, G. M. (2018). Proofs from THE BOOK (6th ed.). Springer.