二项式定理与组合恒等式的部分证明
\(\mathcal{No.}1\)
证明以下组合恒等式
-
\[\dbinom{n}{k}=\dbinom{n}{n-k}
\] -
\[\dbinom{n}{k}=\dfrac{n}{k}\cdot\dbinom{n-1}{k-1}
\]
\(\large{\mathcal{Proof}}\) (组合分析 + 计算)：
-
\(\dbinom{n}{k}\) 的组合意义相当于 \(n\) 个物体中取出 \(k\) 个物体的方案数，而在 \(n\) 个物体中取出 \(k\) 个物体后，就还剩下 \(n-k\) 个物体
废话，则 \(n\) 个物体中取出 \(k\) 个物体的方案数与 \(n\) 个物体中取出 \(n-k\) 个物体的方案数相同，即 \(\dbinom{n}{k}=\dbinom{n}{n-k}\)原公式成立，证毕。
-
\(\because\) 左边 \(=\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}=\dfrac{n}{k}\cdot\dfrac{(n-1)!}{(k-1)!(n-k)!}=\dfrac{n}{k}\cdot\dbinom{n-1}{k-1}=\) 右边
原公式成立，证毕。
\(\mathcal{No.}2\)
证明 \(Pascal\) 公式
\[\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}
\]
\(\large{\mathcal{Proof}}\) (组合分析)：
\(\dbinom{n}{k}\) 的组合意义相当于 \(n\) 个物体中取出 \(k\) 个物体的方案数，而我们可以指定第 \(n\) 个物体的取否，也可以得到方案数。
-
当取第 \(n\) 个物体时，还剩下 \(n-1\) 个物体，还可以选择 \(k-1\) 个物体，方案数为 \(\dbinom{n-1}{k-1}\)
-
当不取第 \(n\) 个物体时，还剩下 \(n-1\) 个物体，还可以选择 \(k\) 个物体，方案数为 \(\dbinom{n-1}{k}\)
\(\large{\therefore}\) 方案数也可以表示为 \(\dbinom{n-1}{k-1}+\dbinom{n-1}{k}\)
\(\therefore\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\)
原公式成立，证毕。
\(\mathcal{No.}3\)
证明二项式定理：
\[(x+y)^n=\displaystyle\sum^{n}_{k=0}\dbinom{n}{k}x^{n-k}y^{k}
\]
\(\large{\mathcal{Proof}}\) (数学归纳法)：
-
当 \(n=1\) 时，\((x+y)^n=x+y\)，显然成立。
-
假设 \(n=k\) 时公式成立, 即证 \(n=k+1\) 时公式也成立
\(\because (x+y)^{k+1}=(x+y)(x+y)^k\)
\(\therefore(x+y)^{k+1}=(x+y)(\displaystyle\sum^{k}_{i=0}\dbinom{k}{i}x^{k-i}y^{i})\)
\(\therefore(x+y)^{k+1}=\displaystyle\sum^{k}_{i=0}\dbinom{k}{i}x^{k-i+1}y^{i}+\displaystyle\sum^{k}_{i=0}\dbinom{k}{i}x^{k-i}y^{i+1}\)
\(\therefore(x+y)^{k+1}=\dbinom{k}{0}x^{k+1}+\displaystyle\sum^{k}_{i=1}\dbinom{k}{i}x^{k-i+1}y^{i}+\dbinom{k}{k}y^{k+1}+\displaystyle\sum^{k-1}_{i=0}\dbinom{k}{i}x^{k-i}y^{i+1}\)
变限合并得:
\(\therefore(x+y)^{k+1}=\dbinom{k}{0}x^{k+1}+\displaystyle\sum^{k}_{i=1}\big[\dbinom{k}{i}+\dbinom{k}{i-1}\big]x^{k-i+1}y^{i}+\dbinom{k}{k}y^{k+1}\)
由 \(Pascal\) 公式得:
\(\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\)
\(\therefore(x+y)^{k+1}=\dbinom{k}{0}x^{k+1}+\displaystyle\sum^{k}_{i=1}\dbinom{k+1}{i}x^{k-i+1}y^{i}+\dbinom{k}{k}y^{k+1}\)
\(\therefore(x+y)^{k+1}=\displaystyle\sum^{k}_{i=0}\dbinom{k+1}{i}x^{k-i+1}y^{i}\)
即得:当 \(n=k\) 公式成立时, \(n=k+1\) 时公式也成立
综上，原公式成立，证毕。
由此，我们也可以通过改变 \(x\) 和 \(y\) 的取值，得到以下公式：
-
当 \(x=y=1\) 时，\((x+y)^n=(1+1)^n=2^n=\displaystyle\sum^{n}_{k=0}\dbinom{n}{k}\)
\(\therefore\displaystyle\sum^{n}_{k=0}\dbinom{n}{k}=2^n\)
-
当 \(x=1\)，\(y=-1\) 时，\((x+y)^n=(1+(-1))^n=0=\displaystyle\sum^{n}_{k=0}(-1)^k\dbinom{n}{k}\)
\(\therefore\displaystyle\sum^{n}_{k=0}(-1)^k\dbinom{n}{k}=0\)
\(\mathcal{No.}4\)
证明
\[\displaystyle\sum^n_{k=0}k\dbinom{n}{k}=n\cdot2^{n-1}
\]
\(\large{\mathcal{Proof}}\) (二项式定理 + 求导)：
-
如果不了解求导的朋友可以看一下这一篇文章 链接
\(\because (1+x)^{n}=\displaystyle\sum^{n}_{k=0}\dbinom{n}{k}x^{k}=\displaystyle\sum^{n}_{k=1}\dbinom{n}{k}x^{k}+1\)
求导得:
\(n(1+x)^{n-1}=\displaystyle\sum^{n}_{k=1}k\cdot \dbinom{n}{k}x^{k-1}\)
又因为 \(\displaystyle\sum^{n}_{k=0}\dbinom{n}{k}=2^n\)
\(\therefore\)当 \(x=1\) 时，\(n\cdot2^{n-1}=\displaystyle\sum^{n}_{k=1}k\dbinom{n}{k}\)
通过变限得：
\(\displaystyle\sum^n_{k=0}k\dbinom{n}{k}=n\cdot2^{n-1}\)
原公式成立，证毕。
\(\mathcal{No.}5\)
证明
\[\displaystyle\sum^n_{k=0}k^2\dbinom{n}{k}=n(n+1)\cdot2^{n-2}
\]
\(\large{\mathcal{Proof}}\) (二项式定理)：
由 \(\dbinom{n}{k}=\dfrac{n}{k}\dbinom{n-1}{k-1}\) 得：
\(\displaystyle\sum^n_{k=0}k^2\dbinom{n}{k}=\displaystyle\sum^n_{k=1}k^2\cdot \dfrac{n}{k}\dbinom{n-1}{k-1}=\displaystyle\sum^n_{k=1}k\cdot n\dbinom{n-1}{k-1}\)
将 \(n\) 提出，并配凑 \(k-1\) 后,式子变为 \(n\displaystyle\sum^n_{k=1}[(k-1)+1]\dbinom{n-1}{k-1}\)
\(\therefore\) 原式 \(=n\displaystyle\sum^n_{k=1}[(k-1)+1]\dbinom{n-1}{k-1}=n\displaystyle\sum^n_{k=1}(k-1)\dbinom{n-1}{k-1}+n\displaystyle\sum^n_{k=1}\dbinom{n-1}{k-1}\)
\(\because\displaystyle\sum^{n}_{k=0}\dbinom{n}{k}=2^n\)
\(\therefore\) 原式 \(=n\displaystyle\sum^n_{k=1}(k-1)\dbinom{n-1}{k-1}+n\cdot 2^{n-1}\)
通过变限得:
原式 \(=n\displaystyle\sum^n_{k=0}k\dbinom{n-1}{k}+n\cdot 2^{n-1}=n(n-1)\cdot 2^{n-2}+n\cdot 2^{n-1}=n(n+1)\cdot2^{n-2}\)
\(\mathcal{No.}6\)
证明
\[\displaystyle\sum^n_{l=0}\dbinom{l}{k}=\dbinom{n+1}{k+1}\ n,k \in N
\]
\(\large{\mathcal{Proof}}\) (组合分析)：
\(\dbinom{n+1}{k+1}\) 的组合意义相当于集合 \(S=\{a_1,a_2,a_3\cdots a_n,a_{n+1}\}\) 中集合大小为 \(k+1\) 子集数。
而子集数也可以通过指定某些集合元素的取否来算出。
当 \(a_1\) 在子集中，此时有一共 \(\dbinom{n}{k}\) 个集合大小为 \(k+1\) 的子集。
当 \(a_2\) 在子集中，且 \(a_1\) 不在子集中，此时有一共 \(\dbinom{n-1}{k}\) 个集合大小为 \(k+1\) 的子集。
\(\large{\cdots\cdots}\)
当 \(a_n\) 在子集中，且 \(a_1,a_2\cdots a_{n-1}\) 不在子集中，此时有一共 \(\dbinom{1}{k}\) 个集合大小为 \(k+1\) 的子集。
当 \(a_{n+1}\) 在子集中，且 \(a_1,a_2\cdots a_{n}\) 不在子集中，此时有一共 \(\dbinom{0}{k}\) 个集合大小为 \(k+1\) 的子集。
综上，共有 \(\dbinom{n}{k}+\dbinom{n-1}{k}+\cdots+\dbinom{1}{k}+\dbinom{0}{k}=\displaystyle\sum^n_{l=0}\dbinom{l}{k}\) 个集合大小为 \(k+1\) 的子集。
由此可得：\(\displaystyle\sum^n_{l=0}\dbinom{l}{k}=\dbinom{n+1}{k+1}\)
原公式成立，证毕。
\(\mathcal{No.}7\)
证明
\[\dbinom{n}{r}\dbinom{r}{k}=\dbinom{n}{k}\dbinom{n-k}{r-k}
\]
\(\large{\mathcal{Proof}}\) (组合分析)：
\(\dbinom{n}{r}\dbinom{r}{k}\) 的组合意义相当于一个大小为 \(n\) 的集合中先取出 \(r\) 个元素，再从这 \(r\) 个元素中取出 \(k\) 个元素的方案数。
而我们是否能直接以这些 \(k\) 元子集的数目 \(\dbinom{n}{k}\) 代替之前所提的方案数呢?
答案是不能废话不，因为不同的 \(r\) 元子集可能会取出相同的 \(k\) 元子集(如图)
所以,我们还要算上这些这些能选出相同 \(k\) 元子集的 \(r\) 元子集,即乘上 \(\dbinom{n-k}{r-k}\)
综上,集合中先取出 \(r\) 个元素，再从这 \(r\) 个元素中取出 \(k\) 个元素的方案数也等于 \(\dbinom{n}{k}\dbinom{n-k}{r-k}\)
所以，\(\dbinom{n}{r}\dbinom{r}{k}=\dbinom{n}{k}\dbinom{n-k}{r-k}\)
原公式成立，证毕。
\(\mathcal{No.}8\)
证明
\[\displaystyle\sum^{r}_{k=0}\dbinom{m}{k}\dbinom{n}{r-k}=\dbinom{n+m}{r}
\]
\(\large{\mathcal{Proof}}\) (组合分析)：
\(\displaystyle\sum^{r}_{k=0}\dbinom{m}{k}\dbinom{n}{r-k}\) 的组合意义相当于先在一个大小为 \(n\) 的集合中取出 \(k\) 个元素，再在一个大小为 \(m\) 的集合中取出 \(r-k\) 个元素的方案数。
由于在 \(n\) 元集合中取值与在 \(m\) 元集合中取值互不干扰显然，所以我们可以将两个集合合并，并在合并后的集合中取出 \(r\) 个元素，这样操作后方案数并不会发生改变，此时方案数为 \(\dbinom{n+m}{r}\)
综上，\(\displaystyle\sum^{r}_{k=0}\dbinom{m}{k}\dbinom{n}{r-k}=\dbinom{n+m}{r}\)
原公式成立，证毕。
通过改变 \(r\) 的取值，我们还可以得到下面这个式子：
当 \(r=m\) 时，\(\displaystyle\sum^{r}_{k=0}\dbinom{m}{k}\dbinom{n}{r-k}=\displaystyle\sum^{m}_{k=0}\dbinom{m}{k}\dbinom{n}{m-k}=\dbinom{n+m}{m}\)
整理得：
\(\displaystyle\sum^{m}_{k=0}\dbinom{n}{k}\dbinom{m}{k}=\dbinom{n+m}{m}\)
完结撒花