Natural Numbers and Induction

Base: for $n = 1$ the left side is $1$ and the right side is $\frac{1\cdot 2}{2} = 1$, so $P(1)$ holds. The first domino falls.

Inductive step: assume $P(k)$ holds, i.e. $1+2+\cdots+k = \frac{k(k+1)}{2}$.

Adding $k+1$ to both sides gives $1+2+\cdots+k+(k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$, which is exactly $P(k+1)$. Hence $P(k) \Rightarrow P(k+1)$ — each fallen domino knocks over the next.

By the induction principle, $P(n)$ holds for every natural number $n$. Hence $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ — the base case plus one inductive step proves infinitely many statements at once.

Base: for $n = 1$, $(1+x)^1 = 1+x = 1+1\cdot x$, so the inequality holds with equality. The hypothesis $x > -1$ is not needed yet.

Inductive step: assume $(1+x)^k \ge 1+kx$. Since $x > -1$, we have $1+x > 0$, and multiplying both sides of the inequality by the positive number $1+x$ preserves its direction:

$(1+x)^{k+1} \ge (1+kx)(1+x) = 1 + (k+1)x + kx^2$. Because $kx^2 \ge 0$, the right side is at least $1+(k+1)x$. Hence $(1+x)^{k+1} \ge 1+(k+1)x$ — that is, $P(k) \Rightarrow P(k+1)$.

By the induction principle, $(1+x)^n \ge 1+nx$ holds for every natural number $n$. The condition $1+x > 0$ was the key to the inductive step — multiplying an inequality by a non-positive number would flip the inequality sign.

Base: for $n = 1$, $2^1 = 2 > 1$, so $P(1)$ holds.

Inductive step: assume $2^k > k$. Multiplying both sides by $2$ gives $2^{k+1} = 2\cdot 2^k > 2k$.

Since $k \ge 1$, we have $2k = k+k \ge k+1$. Hence $2^{k+1} > k+1$ — that is, $P(k) \Rightarrow P(k+1)$.

By the induction principle, $2^n > n$ for every natural number $n$. Exponential growth eventually dominates linear growth — this proof just repeats $n$ times the elementary observation that "doubling beats adding one".