§1 The Set ℕ of Natural Numbers

We write $\mathbb{N}$ for the set $\{1, 2, 3, \dots\}$ of positive integers. Every $n \in \mathbb{N}$ has a successor, $n + 1$. The following properties of $\mathbb{N}$ probably look obvious, at least the first four.

Why this matters

Analysis is full of statements indexed by $n$: “the $n$th term is at most $2$”, “the first $n$ terms are increasing”. Induction is how we prove infinitely many such statements with a finite argument. It comes back constantly: in the inequality $(1+b)^n \ge 1 + nb$ behind Theorem 9.7, in sequences defined recursively (§10, Example 2), and in the step-by-step construction of subsequences (§11).

Peano Axioms.

• N1. $1$ belongs to $\mathbb{N}$.
• N2. If $n$ belongs to $\mathbb{N}$, then its successor $n + 1$ belongs to $\mathbb{N}$.
• N3. $1$ is not the successor of any element of $\mathbb{N}$.
• N4. If $n$ and $m$ in $\mathbb{N}$ have the same successor, then $n = m$.
• N5. A subset of $\mathbb{N}$ that contains $1$, and contains $n + 1$ whenever it contains $n$, must equal $\mathbb{N}$.

Most familiar properties of $\mathbb{N}$ can be proved from these five axioms. The only one that is not obvious is N5, so it is worth seeing what it says.

Suppose $S \subseteq \mathbb{N}$ satisfies the hypotheses of N5. Then $1 \in S$, so $2 = 1 + 1 \in S$, so $3 = 2 + 1 \in S$, and so on. This “and so on” can never be completed by finitely many steps of reasoning. N5 is exactly the axiom that lets us conclude $S = \mathbb{N}$ anyway.

Another way to see it: if N5 failed, there would be a set $S$ with (i) $1 \in S$ and (ii) $n \in S \Rightarrow n + 1 \in S$, yet $S \ne \mathbb{N}$. Let $n_0$ be the smallest element of $\mathbb{N}$ not in $S$. Then $n_0 \neq 1$ by (i), so $n_0 - 1 \in \mathbb{N}$, and $n_0 - 1 \in S$ by minimality. By (ii), $n_0 \in S$, which is a contradiction. This is persuasive but it is not a proof of N5, because it quietly assumes that every nonempty subset of $\mathbb{N}$ has a least element and that every $n_0 \ne 1$ is a successor.

Mathematical induction

Axiom N5 is the basis of mathematical induction. Let $P_1, P_2, P_3, \dots$ be a list of statements. All of them are true provided

$$\begin{aligned} &(I_1)\quad P_1 \text{ is true,} \\ &(I_2)\quad P_{n+1} \text{ is true whenever } P_n \text{ is true.} \end{aligned}$$

$(I_1)$ is the basis for induction and $(I_2)$ is the induction step. A proof by induction must check both.

Example 1.

Prove $1 + 2 + \cdots + n = \tfrac12 n(n+1)$ for all positive integers $n$.

Solution

Let $P_n$ be the statement “$1 + 2 + \cdots + n = \tfrac12 n(n+1)$.” For example, $P_{37}$ says $1 + 2 + \cdots + 37 = \tfrac12 \cdot 37 \cdot 38 = 703$. $P_1$ says $1 = \tfrac12 \cdot 1 \cdot 2$, which is true. That is the basis.

For the induction step, suppose $P_n$ is true. Adding $n + 1$ to both sides,

$$\begin{aligned} 1 + 2 + \cdots + n + (n+1) &= \tfrac12 n(n+1) + (n+1) \\ &= \tfrac12\bigl[n(n+1) + 2(n+1)\bigr] = \tfrac12 (n+1)\bigl((n+1)+1\bigr), \end{aligned}$$

which is $P_{n+1}$. By induction, $P_n$ holds for all $n$.

∎

Notice that before the final sentence we never proved “$P_{n+1}$ is true.” We proved an implication, “if $P_n$ then $P_{n+1}$,” which stands for infinitely many implications: $P_1 \Rightarrow P_2$, $P_2 \Rightarrow P_3$, and so on. Induction then strings them together. Also, formulas like this one are much easier to prove than to discover. Finding them often takes trial and error.

Intuition

Think of the induction step as one argument about an unspecified $n$: a machine that takes a proof of $P_n$ and turns it into a proof of $P_{n+1}$. The basis gets the machine started, and N5 says that running it forever reaches every natural number. A good self-check: does your induction step use anything about $n$ other than “$P_n$ is true” and “$n \ge 1$”? If it quietly uses, say, $n \ge 2$, then the step has not been proved for $n = 1$.

Example 2.

All numbers of the form $5^n - 4n - 1$ are divisible by $16$.

Solution

Let $P_n$ be “$5^n - 4n - 1$ is divisible by $16$.” $P_1$ is true because $5 - 4 - 1 = 0$. For the induction step, the trick is to write

$$5^{n+1} - 4(n+1) - 1 = 5\,(5^n - 4n - 1) + 16n.$$

If $5^n - 4n - 1 = 16m$, then $5^{n+1} - 4(n+1) - 1 = 16(5m + n)$, a multiple of $16$. So $P_n \Rightarrow P_{n+1}$, and induction finishes the proof.

∎

Example 3.

Show $|\sin nx| \le n\,|\sin x|$ for all $n \in \mathbb{N}$ and all real $x$.

Solution

Let $P_n$ be “$|\sin nx| \le n|\sin x|$ for all real $x$.” $P_1$ is clear. Assume $P_n$. By the addition formula and the Triangle Inequality (§3),

$$|\sin(n+1)x| = |\sin nx \cos x + \cos nx \sin x| \le |\sin nx|\,|\cos x| + |\cos nx|\,|\sin x| \le |\sin nx| + |\sin x|,$$

using $|\cos y| \le 1$. By $P_n$ this is at most $n|\sin x| + |\sin x| = (n+1)|\sin x|$, which is $P_{n+1}$.

∎

Common pitfalla step that breaks at the bottom

Here is a flawed “proof” that in every group of $n$ people, all have the same birthday. The basis $n = 1$ is true. For the step, take $n + 1$ people. Send one person, $A$, out of the room: the $n$ who remain share a birthday by $P_n$. Bring $A$ back and send out someone else, $B$: again the $n$ who remain share a birthday. The two groups overlap, so all $n + 1$ share a birthday.

The step fails when $n = 1$. With two people, the two groups are $\{B\}$ and $\{A\}$, and they do not overlap. One broken link ruins the whole chain, so always check that the step works for the smallest $n$ it will be used for.

Common pitfallstarting somewhere else

Induction can start at any integer $n_0$: prove $P_{n_0}$, and prove $P_n \Rightarrow P_{n+1}$ for every $n \ge n_0$. The conclusion is then “$P_n$ for all $n \ge n_0$”, and nothing is claimed below $n_0$. For example, $2^n > n^2$ is false for $n = 2, 3, 4$ but true for all $n \ge 5$. The step works only once $n$ is large enough (from $2^n > n^2$ you need $2n^2 \ge (n+1)^2$, true for $n \ge 3$), so the basis must be $n_0 = 5$. Try both bases in the widget below.

Try it: build the chain

Pick a statement, check the basis, then apply the induction step to extend the chain of proved statements. The last three statements show what goes wrong when one of $(I_1)$ or $(I_2)$ is missing. For $2^n > n^2$, try the bases $n_0 = 1$ and $n_0 = 5$.

Basis n₀1

Check the basis P₁Apply the step onceApply it repeatedlyReset

1. P₁
2. P₂
3. P₃
4. P₄
5. P₅
6. P₆
7. P₇
8. P₈
9. P₉
10. P₁₀
11. P₁₁
12. P₁₂
13. P₁₃
14. P₁₄
15. P₁₅
16. P₁₆
17. P₁₇
18. P₁₈
19. P₁₉
20. P₂₀

proved by the chain so farnot proved (press to check one case)

Start by checking the basis.

Reading alongside Abbott

Abbott treats induction in Section 1.2 as one of a few basic proof techniques, stated directly for subsets of $\mathbb{N}$, which is exactly axiom N5. Abbott does not list the Peano axioms; it takes $\mathbb{N}$ as known and spends its effort on $\mathbb{Q}$ and $\mathbb{R}$. The principle, and how you use it, are the same in both books.

Check your understanding

Take the quiz (3 questions)

To prove a statement $P_n$ for every $n \in \mathbb{N}$ by induction, what must you show?

$P_1$ is true, and $P_n$ implies $P_{n+1}$ for each $n$.$P_n$ is true for $n = 1, 2, 3$, so the pattern continues.$P_{n+1}$ implies $P_n$ for each $n$.

In the inductive step for $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$, you assume the formula for $n$. What do you add to both sides?

$n + 1$$n$$\frac{n(n+1)}{2}$

Let $P_n$ be the statement “$n^2 + n$ is odd”. If $P_n$ holds, then $(n+1)^2 + (n+1) = (n^2 + n) + 2(n+1)$ is odd too, so $P_n$ implies $P_{n+1}$. What can you conclude?

$P_n$ is true for every $n$.Nothing yet: the basis $P_1$ fails, and in fact $n^2 + n = n(n+1)$ is always even.Induction is unreliable for statements about parity.

Exercises

Exercise 1.1

Prove $1^2 + 2^2 + \cdots + n^2 = \tfrac16 n(n+1)(2n+1)$ for all positive integers $n$.

Hint

In the induction step, add $(n+1)^2$ to both sides and factor out $\tfrac16(n+1)$.

Solution

$P_1$: $1 = \tfrac16 \cdot 1 \cdot 2 \cdot 3$. Assuming $P_n$, $\tfrac16 n(n+1)(2n+1) + (n+1)^2 = \tfrac16 (n+1)\bigl[n(2n+1) + 6(n+1)\bigr] = \tfrac16 (n+1)(2n^2 + 7n + 6) = \tfrac16 (n+1)(n+2)(2n+3)$, which is $P_{n+1}$.

Tags: StandardInduction

Exercise 1.2

Prove $3 + 11 + \cdots + (8n - 5) = 4n^2 - n$ for all positive integers $n$.

Solution

$P_1$: $3 = 4 - 1$. Assuming $P_n$, adding the next term $8(n+1) - 5 = 8n + 3$ gives $4n^2 - n + 8n + 3 = 4n^2 + 7n + 3 = 4(n+1)^2 - (n+1)$.

Tags: Warm-upInduction

Exercise 1.3

Prove $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ for all positive integers $n$.

Hint

By Example 1 the right side is $\tfrac14 n^2 (n+1)^2$. Prove $\sum_{k=1}^n k^3 = \tfrac14 n^2(n+1)^2$ by induction.

Solution

$\tfrac14 n^2(n+1)^2 + (n+1)^3 = \tfrac14 (n+1)^2 (n^2 + 4n + 4) = \tfrac14 (n+1)^2 (n+2)^2$.

Tags: StandardInduction

Exercise 1.4

1. Guess a formula for $1 + 3 + \cdots + (2n-1)$ by evaluating the sum for $n = 1, 2, 3, 4$.
2. Prove your formula using mathematical induction.

Solution

(a) The sums are $1, 4, 9, 16$, suggesting $n^2$. (b) $n^2 + (2(n+1) - 1) = n^2 + 2n + 1 = (n+1)^2$.

Tags: Warm-upInductionComputation

Exercise 1.5

Prove $1 + \tfrac12 + \tfrac14 + \cdots + \tfrac{1}{2^n} = 2 - \tfrac{1}{2^n}$ for all positive integers $n$.

Solution

$P_1$: $1 + \tfrac12 = 2 - \tfrac12$. Then $2 - \tfrac1{2^n} + \tfrac1{2^{n+1}} = 2 - \tfrac{2}{2^{n+1}} + \tfrac1{2^{n+1}} = 2 - \tfrac1{2^{n+1}}$.

Tags: Warm-upInduction

Exercise 1.6

Prove $11^n - 4^n$ is divisible by $7$ when $n$ is a positive integer.

Hint

Write $11^{n+1} - 4^{n+1} = 11(11^n - 4^n) + 7 \cdot 4^n$.

Solution

Induct on $n$. For $n = 1$, $11 - 4 = 7$. Suppose $7 \mid 11^n - 4^n$. Then $11^{n+1} - 4^{n+1} = 11(11^n - 4^n) + 11\cdot4^n - 4\cdot4^n = 11(11^n - 4^n) + 7\cdot4^n .$ Both terms are divisible by $7$, so $7 \mid 11^{n+1} - 4^{n+1}$.

Tags: StandardInduction

Exercise 1.7

Prove $7^n - 6n - 1$ is divisible by $36$ for all positive integers $n$.

Hint

Mimic Example 2: $7^{n+1} - 6(n+1) - 1 = 7(7^n - 6n - 1) + 36n$.

Solution

Induct on $n$. For $n = 1$, $7 - 6 - 1 = 0$, which is divisible by $36$. Suppose $36 \mid 7^n - 6n - 1$. Then $7^{n+1} - 6(n+1) - 1 = 7(7^n - 6n - 1) + 42n + 7 - 6n - 7 = 7(7^n - 6n - 1) + 36n,$ which is divisible by $36$.

Tags: StandardInduction

Exercise 1.8

The principle of induction extends as follows: $P_m, P_{m+1}, \dots$ are all true provided (i) $P_m$ is true and (ii) $P_{n+1}$ is true whenever $P_n$ is true and $n \ge m$.

1. Prove $n^2 > n + 1$ for all integers $n \ge 2$.
2. Prove $n! > n^2$ for all integers $n \ge 4$.

Solution

(a) $4 > 3$. If $n^2 > n + 1$ then $(n+1)^2 = n^2 + 2n + 1 > (n+1) + 2n + 1 > n + 2$.

(b) $24 > 16$. If $n! > n^2$ then $(n+1)! = (n+1)\,n! > (n+1)n^2 > (n+1)^2$, the last step because $n^2 > n + 1$ by (a).

Tags: StandardInductionInequalities

Exercise 1.9

1. Decide for which integers the inequality $2^n > n^2$ is true.
2. Prove your claim in (a) by mathematical induction.

Solution

(a) It holds for $n = 1$ and for all $n \ge 5$, and fails for $n = 2, 3, 4$.

(b) Basis $n = 5$: $32 > 25$. If $2^n > n^2$ with $n \ge 5$, then $2^{n+1} > 2n^2 = n^2 + n^2 > n^2 + 2n + 1 = (n+1)^2$, since $n^2 > 2n + 1$ when $n \ge 3$.

Tags: StandardInductionInequalities

Exercise 1.10

Prove $(2n+1) + (2n+3) + (2n+5) + \cdots + (4n-1) = 3n^2$ for all positive integers $n$.

Hint

Going from $n$ to $n+1$, the sum loses its first term $2n+1$ and gains the two terms $4n+1$ and $4n+3$.

Solution

$3n^2 - (2n+1) + (4n+1) + (4n+3) = 3n^2 + 6n + 3 = 3(n+1)^2$.

Tags: StandardInduction

Exercise 1.11

For each $n \in \mathbb{N}$, let $P_n$ denote the assertion “$n^2 + 5n + 1$ is an even integer.”

1. Prove $P_{n+1}$ is true whenever $P_n$ is true.
2. For which $n$ is $P_n$ actually true? What is the moral of this exercise?

Solution

(a) $(n+1)^2 + 5(n+1) + 1 = (n^2 + 5n + 1) + 2n + 6$, and $2n + 6$ is even.

(b) Never: $n^2 + 5n = n(n+5)$ is always even, so $n^2 + 5n + 1$ is always odd. The moral is that the induction step alone proves nothing. You must also check the basis.

Tags: Warm-upInductionComputation

Exercise 1.12

For $n \in \mathbb{N}$ let $n! = 1 \cdot 2 \cdots n$, let $0! = 1$, and define $\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ for $k = 0, 1, \dots, n$. The binomial theorem asserts

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k = a^n + n a^{n-1} b + \tfrac12 n(n-1) a^{n-2} b^2 + \cdots + n a b^{n-1} + b^n.$$

1. Verify the binomial theorem for $n = 1, 2, 3$.
2. Show $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ for $k = 1, 2, \dots, n$.
3. Prove the binomial theorem using mathematical induction and part (b).

Hint

For (c), write $(a+b)^{n+1} = (a+b)(a+b)^n$, expand using $P_n$, and collect the coefficient of $a^{n+1-k} b^k$. It is $\binom{n}{k} + \binom{n}{k-1}$.

Solution

(b) Over the common denominator $k!\,(n+1-k)!$: $\dfrac{n!\,(n+1-k) + n!\,k}{k!\,(n+1-k)!} = \dfrac{(n+1)!}{k!\,(n+1-k)!}$.

Tags: ChallengeInduction

Used in Theorem 9.7