Natural Numbers and Induction

The natural numbers start from the Peano axioms: P(1)P(1) plus P(k)⇒P(k+1)P(k) \Rightarrow P(k+1) yields P(n)P(n) for every natural number nn — addition and multiplication are also defined recursively, and this one principle proves infinitely many statements at once.

P(1)∧(P(k)⇒P(k+1))⇒∀n∈N,  P(n)P(1) \land (P(k) \Rightarrow P(k+1)) \Rightarrow \forall n \in \mathbb{N},\; P(n)
∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n+1)}{2}
(1+x)n≥1+nx(x>−1)(1+x)^n \geq 1 + nx \quad (x > -1)
2n>n2^n > n

Part of these learning paths

Examples & Exercises

Let P(n)P(n) be the statement ∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n+1)}{2}. Prove by mathematical induction that it holds for every natural number nn.

1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}
n=6n = 6 — six dominoes, i.e. the case 1+2+⋯+6=211+2+\cdots+6 = 21.
Show proof
  1. Base: for n=1n = 1 the left side is 11 and the right side is 1⋅22=1\frac{1\cdot 2}{2} = 1, so P(1)P(1) holds. The first domino falls.
  2. Inductive step: assume P(k)P(k) holds, i.e. 1+2+⋯+k=k(k+1)21+2+\cdots+k = \frac{k(k+1)}{2}. Adding k+1k+1 to both sides gives 1+2+⋯+k+(k+1)=k(k+1)2+(k+1)=(k+1)(k+2)21+2+\cdots+k+(k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}, which is exactly P(k+1)P(k+1). Hence P(k)⇒P(k+1)P(k) \Rightarrow P(k+1) — each fallen domino knocks over the next.
  3. By the induction principle, P(n)P(n) holds for every natural number nn. Hence ∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n+1)}{2} — the base case plus one inductive step proves infinitely many statements at once.

Prove by mathematical induction that (1+x)n≥1+nx(1+x)^n \ge 1+nx for every real x>−1x > -1 and every natural number nn (Bernoulli's inequality).

(1+x)n≥1+nx(x>−1)(1+x)^n \geq 1 + nx \quad (x > -1)
n=6n = 6 — (1+x)6≥1+6x(1+x)^6 \ge 1+6x for every x>−1x > -1.
Show proof
  1. Base: for n=1n = 1, (1+x)1=1+x=1+1⋅x(1+x)^1 = 1+x = 1+1\cdot x, so the inequality holds with equality. The hypothesis x>−1x > -1 is not needed yet.
  2. Inductive step: assume (1+x)k≥1+kx(1+x)^k \ge 1+kx. Since x>−1x > -1, we have 1+x>01+x > 0, and multiplying both sides of the inequality by the positive number 1+x1+x preserves its direction: (1+x)k+1≥(1+kx)(1+x)=1+(k+1)x+kx2(1+x)^{k+1} \ge (1+kx)(1+x) = 1 + (k+1)x + kx^2. Because kx2≥0kx^2 \ge 0, the right side is at least 1+(k+1)x1+(k+1)x. Hence (1+x)k+1≥1+(k+1)x(1+x)^{k+1} \ge 1+(k+1)x — that is, P(k)⇒P(k+1)P(k) \Rightarrow P(k+1).
  3. By the induction principle, (1+x)n≥1+nx(1+x)^n \ge 1+nx holds for every natural number nn. The condition 1+x>01+x > 0 was the key to the inductive step — multiplying an inequality by a non-positive number would flip the inequality sign.

Prove by mathematical induction that 2n>n2^n > n for every natural number nn.

2n>n(n∈N)2^n > n \quad (n \in \mathbb{N})
n=6n = 6 — 26=64>62^6 = 64 > 6: the exponential pulls ahead of the linear term.
Show proof
  1. Base: for n=1n = 1, 21=2>12^1 = 2 > 1, so P(1)P(1) holds.
  2. Inductive step: assume 2k>k2^k > k. Multiplying both sides by 22 gives 2k+1=2⋅2k>2k2^{k+1} = 2\cdot 2^k > 2k. Since k≥1k \ge 1, we have 2k=k+k≥k+12k = k+k \ge k+1. Hence 2k+1>k+12^{k+1} > k+1 — that is, P(k)⇒P(k+1)P(k) \Rightarrow P(k+1).
  3. By the induction principle, 2n>n2^n > n for every natural number nn. Exponential growth eventually dominates linear growth — this proof just repeats nn times the elementary observation that "doubling beats adding one".

1. Number Systems