首先需要证明一个引理：

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

证：首先，左边

$$ \binom{n}{k-1}+\binom{n}{k} = \frac{n!}{(k-1)!(n-k+1)!} + \frac{n!}{k!(n-k)!}. $$

而右边

$$ \binom{n+1}{k} = \frac{(n+1)!}{k!(n+1-k)!}. $$

试图使左右两边相等，需要使得左边分母为$k!(n+1-k)!$，所以通分得：

$$ \begin{align*} & \frac{n!}{(k-1)!(n-k+1)!} + \frac{n!}{k!(n-k)!} \\ &= \frac{n!k}{k!(n-k+1)!} + \frac{n!(n-k+1)}{k!(n-k+1)!} \\ &= \frac{n!k+n!(n-k+1)}{k!(n-k+1)!} \\ &= \frac{n!(n+1)}{k!(n-k+1)!} \\ &= \frac{(n+1)!}{k!(n+1-k)!} \\ &= \binom{n+1}{k}. \tag*{$\blacksquare$} \end{align*} $$

随后证明二项式定理

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

证：使用归纳法证明. 首先证明$P_0$，显然，

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

故$P_0$得证. 接下来，假设$P_n$成立，验证$P_{n+1}$是否成立：

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

注意到这里，我们给$\sum_{k=0}^{n-1} \binom{n}{k} a^{n-k}b^{k+1}$更换索引为$\sum_{k=1}^{n} \binom{n}{k-1} a^{n-(k-1)}b^{(k-1)+1}$，观察易得这两个式子是相等的（坦诚地说，我第一次学的时候并没有观察出来）. 继续进行变换：

$$ \begin{aligned} & a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k}b^k + b^{n+1} + \sum_{k=1}^{n} \binom{n}{k-1} a^{n-(k-1)}b^{(k-1)+1}. \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k}b^k + b^{n+1} + \sum_{k=1}^{n} \binom{n}{k-1} a^{n+1-k}b^{k}. \\ &= a^{n+1} + b^{n+1} + \sum_{k=1}^{n} \left[ \binom{n}{k} + \binom{n}{k-1} \right] a^{n+1-k}b^{k} . \end{aligned} $$

利用一开始证得的引理，即有

$$ \begin{aligned} & a^{n+1} + b^{n+1} + \sum_{k=1}^{n} \left[ \binom{n}{k} + \binom{n}{k-1} \right] a^{n+1-k}b^{k} \\ &= a^{n+1} + b^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k} a^{n+1-k}b^{k} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k}b^{k}. \end{aligned} $$

所以，

$$ \begin{align} (a+b)^{n+1} = \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k}b^{k}. \tag*{$\blacksquare$} \end{align} $$

虽然在这里写得洋洋洒洒，但是说实话，在下天资愚钝，第一次见到这个证明，还是没那么容易理解的. 而且很有可能，现在证得出来，将来某天就会忘掉. 所以数学的学习是一个不断积累的过程，现在吃下的每一口，将来都会成长为构成身体的肌肉和骨骼.