Mathematical induction 用来证明一个连续整数范围中的每个 statement。Base case 启动整条 implication chain；induction step 则说明一个 case 成立时，下一个 case 也一定成立。

Induction principle

设 proposition $P(n)$ 对每个整数 $n\ge n_0$ 都有定义。要证明这些 propositions 全部成立，需要：

1. **Base case：**证明 $P(n_0)$。
2. **Induction hypothesis：**任取 $n\ge n_0$，暂时假设 $P(n)$ 成立。
3. **Induction step：**利用这个假设证明 $P(n+1)$。
4. 得出 $P(n)$ 对每个整数 $n\ge n_0$ 都成立。

Induction step 要对任意允许的 $n$ 证明 implication $P(n)\Rightarrow P(n+1)$，并不是直接假设整个 theorem 成立。它与 base case 合在一起，形成

$$P(n_0) \Rightarrow P(n_0+1) \Rightarrow P(n_0+2) \Rightarrow\cdots.$$

这种向前推进的方法适用于 $n\ge n_0$ 这样的 natural-number range。一个 base case 加一个 forward step，并不会自动覆盖全部整数、rational numbers 或 real numbers。

例：前 $n$ 个正整数之和

要证明

$$1+2+\cdots+n=\frac{n(n+1)}2 \qquad(n\ge1).$$

Base case。 当 $n=1$ 时，

$$1=\frac{1(1+1)}2.$$

Induction hypothesis。 任取 $n\ge1$，假设

$$1+2+\cdots+n=\frac{n(n+1)}2.$$

Induction step。 加上下一个整数，再对已经知道的部分使用 induction hypothesis：

$$\begin{aligned} 1+2+\cdots+n+(n+1) &=\frac{n(n+1)}2+(n+1)\\ &=\frac{n(n+1)+2(n+1)}2\\ &=\frac{(n+1)(n+2)}2\\ &=\frac{(n+1)((n+1)+1)}2. \end{aligned}$$

这正是 $P(n+1)$，所以 formula 对每个整数 $n\ge1$ 都成立。

例：exponential 最终快过 linear expression

要证明

$$2n+1<2^n \qquad(n\ge3).$$

起始下标不能省略：这个 inequality 在 $n=0,1,2$ 时都不成立。

Base case。 当 $n=3$ 时，

$$2(3)+1=7<8=2^3.$$

Induction hypothesis。 任取 $n\ge3$，假设 $2n+1<2^n$。

Induction step。 有

$$\begin{aligned} 2(n+1)+1 &=(2n+1)+2\\ &<2^n+2 &&\text{by the induction hypothesis}\\ &<2^n+2^n &&\text{because }2<2^n\text{ for }n\ge3\\ &=2^{n+1}. \end{aligned}$$

因此 inequality 对所有整数 $n\ge3$ 成立。

Pascal's triangle 与 binomial pattern

$x+y$ 的前几次幂的 coefficients 组成 Pascal's triangle 的各行：

$$\begin{aligned} (x+y)^1&=x+y,\\ (x+y)^2&=x^2+2xy+y^2,\\ (x+y)^3&=x^3+3x^2y+3xy^2+y^3,\\ (x+y)^4&=x^4+4x^3y+6x^2y^2+4xy^3+y^4. \end{aligned}$$

对应的 coefficient rows 是

$$\begin{array}{ccccccccc} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1. \end{array}$$

每个内部元素等于上一行相邻两项之和，也就是 Pascal's identity：

$$\binom nk+\binom n{k-1}=\binom{n+1}k \qquad(1\le k\le n).$$

可以通过计数证明它。对一个含 $n+1$ 个元素的 set，指定一个特殊元素，再数 $k$-element subsets。不包含它时有 $\binom nk$ 种；包含它时，还要从其余 $n$ 个元素中选择 $k-1$ 个，有 $\binom n{k-1}$ 种。

Binomial theorem

对于每个非负整数 $n$，

$$\boxed{ (x+y)^n=\sum_{k=0}^{n}\binom nk x^{n-k}y^k }.$$

下标为 $k$ 的 term 含有 $k$ 个 $y$ 和 $n-k$ 个 $x$。从 $n$ 个 factors 中选择哪 $k$ 个提供 $y$，共有 $\binom nk$ 种，因此这就是该 term 的 coefficient。

例：找出指定 coefficient

在

$$(2x+y)^{25} =\sum_{k=0}^{25}\binom{25}{k}(2x)^{25-k}y^k,$$

中，要得到 $y^{13}$，必须取 $k=13$，于是 $x$ 的 exponent 是 $25-13=12$：

$$\binom{25}{13}(2x)^{12}y^{13} =\binom{25}{13}2^{12}x^{12}y^{13}.$$

所以 $x^{12}y^{13}$ 的 coefficient 是

$$\boxed{\binom{25}{13}2^{12}}.$$

用 induction 证明 binomial theorem

令 $P(n)$ 表示上面的 binomial identity。

Base case。 当 $n=0$ 时，两边都是 constant polynomial $1$：

$$(x+y)^0=1 =\binom00x^0y^0.$$

Induction hypothesis。 假设对某个 $n\ge0$，

$$(x+y)^n=\sum_{k=0}^{n}\binom nkx^{n-k}y^k.$$

Induction step。 现在把指数从 $n$ 提高到 $(n+1)$。要得到 $P(n+1)$，两边乘以 $x+y$，再使用 hypothesis：

$$\begin{aligned} (x+y)^{n+1} &=(x+y)(x+y)^n\\ &=x\sum_{k=0}^{n}\binom nkx^{n-k}y^k +y\sum_{k=0}^{n}\binom nkx^{n-k}y^k\\ &=\sum_{k=0}^{n}\binom nkx^{n+1-k}y^k +\sum_{k=1}^{n+1}\binom n{k-1}x^{n+1-k}y^k. \end{aligned}$$

对内部下标 $1\le k\le n$，monomial $x^{n+1-k}y^k$ 从两个 sums 各得到一份贡献，所以 coefficient 为

$$\binom nk+\binom n{k-1}=\binom{n+1}k.$$

两个 endpoints 只有一种来源。$k=0$ 时，只有第一个 sum 提供 $x^{n+1}$；$k=n+1$ 时，只有第二个 sum 提供 $y^{n+1}$。由于

$$\binom{n+1}{0}=\binom{n+1}{n+1}=1,$$

得到

$$\begin{aligned} (x+y)^{n+1} &=x^{n+1} +\sum_{k=1}^{n}\binom{n+1}kx^{n+1-k}y^k +y^{n+1}\\ &=\sum_{k=0}^{n+1}\binom{n+1}kx^{n+1-k}y^k. \end{aligned}$$

因此 $P(n+1)$ 成立，binomial theorem 对所有 $n\ge0$ 成立。

为什么 Pascal's triangle 的一行之和是 $2^n$

对每个 $n\ge0$，

$$\boxed{\sum_{k=0}^{n}\binom nk=2^n}.$$

有两种有用的证明。

按 subset 的大小计数。 一个 $n$-element set 有 $2^n$ 个 subsets，因为每个元素都可以选入或不选入。其中恰有 $k$ 个元素的 subsets 有 $\binom nk$ 个。$k=0,1,\ldots,n$ 这些 size classes 互不重叠，又覆盖全部 subsets，所以它们的数量之和是 $2^n$。

使用 binomial theorem。 令 $x=y=1$：

$$2^n=(1+1)^n =\sum_{k=0}^{n}\binom nk1^{n-k}1^k =\sum_{k=0}^{n}\binom nk.$$

$n=0$ 的 endpoint 也成立：empty set 恰有一个 subset，就是它本身。