本文版权归Azazel与博客园共有，欢迎转载，但需保留此声明，并给出原文地址，谢谢合作。
原文地址：https://www.cnblogs.com/Azazel/p/15151448.html
二项式定理
表述
]
(~~~~) 其中 (n) 为正整数。
组合意义证明
(~~~~) 考虑暴力展开 ((x+y)^n) 为 (n) 个 ((x+y)) 的积，则凑出 (k) 个 (x) （即 (x^k) ）的方案数为 (egin{pmatrix} n\k end{pmatrix}) ，同时剩下的 (n-k) 个 (y) 自动凑成 (y^{n-k})，故 (x^k y^{n-k}) 的系数为 (egin{pmatrix} n\k end{pmatrix}) ，将所有项求和即为展开式。
数学归纳法
(~~~~) 当 (n=1) 时，二项式定理经带入成立。
(~~~~) 考虑当二项式定理对 (n) 成立时是否也对 (n+1) 成立。
\ large =(x+y)(x+y)^n
\ large =(x+y)sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k}
\ large =sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} x^{k+1}y^{n-k}+sum_{k=0}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k+1}
\ large =x^{n+1}+sum_{k=0}^{n-1} egin{pmatrix} n\k end{pmatrix} x^{k+1}y^{n-k}+y^{n+1}+sum_{k=1}^n egin{pmatrix} n\k end{pmatrix} x^ky^{n-k+1}
]
(~~~~) 将第一个 (sum) 里面的 (k) 用 (k-1) 来替换，以统一两个 (sum) 的上下限以及统一 (x) 和 (y) 的次数：
]
(~~~~) 代入：
\ large =x^{n+1}+y^{n+1}+sum_{k=1}^n (egin{pmatrix} n\k-1 end{pmatrix}+egin{pmatrix}n\k end{pmatrix})x^ky^{n-k+1}
]
(~~~~) 利用 ( ext{Pascal}) 公式（(egin{pmatrix} n\k end{pmatrix}=egin{pmatrix} n-1\k end{pmatrix}+egin{pmatrix} n-1\k-1 end{pmatrix})）：
\ large =x^{n+1}+y^{n+1}+sum_{k=1}^n egin{pmatrix} n+1\k end{pmatrix} x^ky^{n-k+1}
\ large =sum_{k=0}^{n+1} egin{pmatrix}n+1\kend{pmatrix}x^ky^{n-k+1}
]
(~~~~) 综上：
]
(~~~~) (mathcal{Q.E.D.})
组合恒等式 #1
表述
]
组合意义证明
(~~~~) 从 (n) 个物品当中选 (k) 个的方案数，即在 (n) 个物品中有 (n-k) 个不选的方案数。
公式证明
]
组合恒等式 #2
表述
]
公式证明
]
组合恒等式 #3
表述
]
组合意义证明
(~~~~) 从 (n) 个物品中取 (k) 个物品，方案数为 (egin{pmatrix} n\k end{pmatrix}) 。同时考虑其中某一个物品：
- 选择该物品，则还需从剩下 (n-1) 个物品中选择 (k) 个，方案数 (egin{pmatrix} n-1\k end{pmatrix})；
- 不选该物品，则还需从剩下 (n-1) 个物品中选择 (k-1) 个，方案数 (egin{pmatrix} n-1\k -1end{pmatrix})；
(~~~~) 以上两种情况相互独立，故 (egin{pmatrix} n\k end{pmatrix}=egin{pmatrix} n-1\k end{pmatrix}+egin{pmatrix} n-1\k -1end{pmatrix})
公式证明
\ large =dfrac{(n-1)!}{k!(n-1-k)!}+dfrac{(n-1)!}{(k-1)!(n-k)!}
\ large =dfrac{(n-1)! imes (n-k)}{k!(n-k)!}+dfrac{(n-1)! imes k}{k!(n-k)!}
\ large =dfrac{(n-1)! imes n}{k!(n-k)!}=dfrac{n!}{k!(n-k)!}=egin{pmatrix} n\k end{pmatrix}
]
组合恒等式 #4
表述
]
组合意义证明
(~~~~) 左边的意义即从 (n) 个物品中任意取若干个的方案数，则每个物品有取或不取两种选择，总方案数即为 (2^n)。
二项式定理证明
(~~~~) 逆用二项式定理：
]
组合恒等式 #5
表述
]
组合数性质证明
-
当 (n) 为奇数时，该级数共有偶数项，同时绝对值相同的数刚好正负一一对应抵消；
-
当 (n) 为偶数时，用 ( ext{Pascal}) 公式拆开每一项后亦可正负一一抵消。
二项式定理证明
]
组合恒等式 #6
表述
]
求导+二项式定理证明
(~~~~) 先写出一个二项式定理：
]
(~~~~) 为了凑出系数 (k) 我们对两边求导：
]
(~~~~) 令 (x=1)：
]
推式子证明
]
左右相加得：
]
则原式的值即为 (dfrac{n imes 2^n}{2}=n imes 2^{n-1}) 。
组合恒等式 #7
表述
]
推式子证明
(~~~~) 利用第二个组合恒等式：
large =sum_{k=0}^n k^2 dfrac{n}{k}egin{pmatrix} n-1\k-1 end{pmatrix}\
large =sum_{k=0}^n kn egin{pmatrix} n-1\k-1 end{pmatrix}\
]
(~~~~) 拆分 (k) ，方便利用第六个组合恒等式：
large =nsum_{k=0}^n (k-1)egin{pmatrix} n-1\k-1 end{pmatrix}+nsum_{k=0}^n egin{pmatrix} n-1\k-1 end{pmatrix}\
large =nsum_{k=1}^n (k-1)egin{pmatrix} n-1\k-1 end{pmatrix}+nsum_{k=1}^n egin{pmatrix} n-1\k-1 end{pmatrix}\
]
(~~~~) 变限使得其变为标准的组合恒等式：
large =n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}
]
组合恒等式 #8
表述
]
组合意义证明
(~~~~) 在 (n+1) 个物品里面选择 (k+1) 个，假设最后一个被选择的物品的位置为 (l+1) ，则剩下物品的选择方案为 (egin{pmatrix} l\k end{pmatrix}) ，枚举所有 (l) 并求和即为右式的意义。
组合恒等式 #9
]
组合意义证明
(~~~~) 左边为先在 (n) 个物品里选 (r) 个，再在选出的 (r) 个物品中选择 (k) 个的方案数。
(~~~~) 本质上为从 (n) 个物品里选 (k) 个，但是左边可能选出来的 (k) 个可能在不同的选 (r) 个物品的方案下相同，而相同的情况即为从剩下的 (n-k) 个物品中随便选 (r-k) 个得方案数。
组合恒等式 #10
表述
]
组合意义证明
(~~~~) 左式的意义为先从 (m) 个物品中选择 (k) 个，再从 (n) 个物品中选择 (r-k) 个。则相当于从 (m+n) 个物品中选择 (r) 个。由于 (kin[0,r]) ，故任何情况都可以视作上述情况中某一个 (k) 。
组合恒等式 #11
表述
]
组合恒等式证明
由第一个组合恒等式：
large =sum_{k=0}^n egin{pmatrix} m\m-k end{pmatrix} egin{pmatrix} n\k end{pmatrix}
]
再由第十个组合恒等式：
]