「 学习笔记 」二项式定理与组合恒等式
二项式定理与组合恒等式
前置知识
\]
二项式定理
二项式定理：设 \(n\) 是正整数，对于一切 \(x\) 和 \(y\)
\]
常用形式
\]
等价形式
{(x + y)} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k} \\
& = \sum \limits _ {k = 0} ^ n \dbinom {n} {n – k} x ^ k y ^{n – k} \\
& = \sum \limits _ {k = 0} ^ n \dbinom {n} {n – k} x ^ {n – k} y ^k \\
& = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ {n – k} y ^k \\
\end{aligned}
\]
证明 1 ( 组合意义 / 组合分析 / 算二次 )
\]
对于每一项 \(x ^ k y ^ {n – k}\)，其含义就是在 \(n\) 个 \((x + y)\) 中选择 \(k\) 个 \(x\)、\(n – k\) 个 \(y\)，故有 \(\dbinom {n} {k}\) 中选法，即有 \(\dbinom {n} {k}\) 个 \(x ^ k y ^ {n – k}\)
证毕
证明 2 ( 数学归纳法 )
当 \(n = 1\) 时，公式显然成立
假设公式对于正整数 \(n\) 成立，即证明公式对于 \(n + 1\) 也成立
即证
\]
- 因为公式对于 \(n\) 成立，故有
{(x + y)} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k} \\
{(x + y)} ^ {n + 1} & = (x + y) \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k} \\
& = x \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k} + y \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k} \\
& = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ {k + 1} y ^{n – k} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 – k} \\
& = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ {k + 1} y ^{(n + 1) – (k + 1)} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 – k} \\
& = \sum \limits _ {k + 1 = 1} ^ {n + 1} \dbinom {n} {(k + 1) – 1} x ^ {k + 1} y ^{(n + 1) – (k + 1)} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 – k} \\
& = \sum \limits _ {k = 1} ^ {n + 1} \dbinom {n} {k – 1} x ^ k y ^{n + 1 – k} + \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 – k} \\
& = \sum \limits _ {k = 1} ^ {n} \dbinom {n} {k – 1} x ^ k y ^{n + 1 – k} + x ^ {n + 1} + \sum \limits _ {k = 1} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 – k} + y ^ {n + 1} \\
& = \dbinom {n + 1} {0} x ^ {n + 1} + \sum \limits _ {k = 1} ^ {n} \dbinom {n} {k – 1} x ^ k y ^{n + 1 – k} + \sum \limits _ {k = 1} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 – k} + \dbinom {n + 1} {n + 1} y ^ {n + 1} \\
\end{aligned}
\]
由 \(\mathrm{Pascal}\) 公式 \(\dbinom {n + 1} {k} = \dbinom {n} {k – 1} + \dbinom {n} {k}\)（后面会证明），就可以把 \(k\) 相等的项合并了
{(x + y)} ^ {n + 1} & = \dbinom {n + 1} {0} x ^ {n + 1} + \sum \limits _ {k = 1} ^ {n} \dbinom {n} {k – 1} x ^ k y ^{n + 1 – k} + \sum \limits _ {k = 1} ^ n \dbinom {n} {k} x ^ k y ^{n + 1 – k} + \dbinom {n + 1} {n + 1} y ^ {n + 1} \\
& = \dbinom {n + 1} {0} x ^ {n + 1} y ^ 0 + \sum \limits _ {k = 1} ^ {n} \dbinom {n + 1} {k} x ^ k y ^{n + 1 – k} + \dbinom {n + 1} {n + 1} x ^ 0 y ^ {n + 1} \\
& = \sum \limits _ {k = 0} ^ {n + 1} \dbinom {n + 1} {k} x ^ k y ^{n + 1 – k} \\
\end{aligned}
\]
证毕
组合恒等式
公式 1
\]
证明 ( 组合意义 )
\(n\) 个小球选择 \(k\) 个留下，等价于选择 \(n – k\) 个不留下
证毕
公式 2
\]
证明 ( 公式法 )
\dbinom {n} {k} & = \dfrac {n!} {(n – k)! \times k!} \\
& = \dfrac {n} {k} \times \dfrac {(n – 1)!} {(n – k)! \times k!} \\
& = \dfrac {n} {k} \times \dfrac {(n – 1)!} {[(n – 1) – (k – 1)]! \times k!} \\
& = \dfrac {n} {k} \dbinom {n – 1} {k – 1} \\
\end{aligned}
\]
证毕
公式 3 ( Pascal 公式 )
\]
证明 ( 组合意义 )
\(n\) 个小球中选择 \(k\) 个，等价于 ( 不选最后一个，前 \(n – 1\) 个中选择 \(k\) 个 ) 和 ( 选最后一个，前 \(n – 1\) 个中选择 \(k – 1\) 个 ) 的并集
公式 4
\]
证明 ( 公式法 )
由二项式定理得 \({(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k}\)，令 \(x = y = 1\)，则等式变为
{(1 + 1)} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} \times 1 ^ k \times 1 ^{n – k} \\
2 ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} \\
\sum \limits _ {k = 0} ^ n \dbinom {n} {k} & = 2 ^ n \\
\end{aligned}
\]
证毕
公式 5
\]
证明 ( 公式法 )
由二项式定理得 \({(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k}\)，令 \(x = -1\)、\(y = 1\)，则等式变为
{[(-1) + 1]} ^ n & = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} \times {(-1)} ^ k \times 1 ^{n – k} \\
0 ^ n & = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \dbinom {n} {k} \\
\sum \limits _ {k = 0} ^ n {(-1)} ^ k \dbinom {n} {k} & = 0 \\
\end{aligned}
\]
证毕
公式 6 ( 变下项求和 )
\]
证明 1 ( 组合意义 )
- 公式含义：选择 \(n\) 个小球的所有选法中每个小球出现的次数和
- 右式含义：\(n\) 个小球，每个小球被选择的次数是 \(2 ^ {n – 1}\)
- 左式含义：对于所有选法中选择 \(k\) 个小球情况，其对答案的贡献是 \(k\)，共有 \(\dbinom {n} {k}\) 种选法
显然，三种含义等价
证毕
证明 2 ( 公式法 )
由 公式 2 \(\dbinom {n} {k} = \dfrac {n} {k} \dbinom {n – 1} {k – 1}\) 得：
\sum \limits _ {k = 0} ^ {n} k \dbinom {n} {k} & = 0 \dbinom {n} {k} + \sum \limits _ {k = 1} ^ {n} k \times \dbinom {n} {k} \\
& = 0 + \sum \limits _ {k = 1} ^ {n} k \times \dfrac {n} {k} \dbinom {n – 1} {k – 1} \\
& = \sum \limits _ {k = 1} ^ {n} n \dbinom {n – 1} {k – 1} \\
& = n \sum \limits _ {k = 1} ^ {n} \dbinom {n – 1} {k – 1} \\
& = n \sum \limits _ {k = 0} ^ {n – 1} \dbinom {n – 1} {k} \\
\end{aligned}
\]
由 公式 4 \(\sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} = 2 ^ n\) 得 \(\sum \limits _ {k = 0} ^ {n – 1} \dbinom {n – 1} {k} = 2 ^ {n – 1}\)，故
\sum \limits _ {k = 0} ^ {n} k \dbinom {n} {k} & = n \sum \limits _ {k = 0} ^ {n – 1} \dbinom {n – 1} {k} \\
& = n 2 ^ {n – 1} \\
\end{aligned}
\]
证毕
公式 7
\]
证明 1 ( 组合意义 )
n (n + 1) 2 ^ {n – 2} & = n (n – 1) 2 ^ {n – 2} + n \times 2 \times 2 ^ {n – 2} \\
& = n (n – 1) 2 ^ {n – 2} + n \times 2 ^ {n – 1}
\end {aligned}
\]
- 左式含义：有 \(n\) 个不同的数，对于选择 \(k\) 个不同的数的情况，可以组成 \(k ^ 2\) 种有序数对，每种有序数对 \((a, b)\) 对答案的贡献为 \(1\)，一起对答案的贡献就是 \(k ^ 2\)，选择 \(k\) 个不同的数有 \(\dbinom {n} {k}\) 种选法
- 右式含义：考虑每种有序数对 \((a, b)\) 对答案的贡献；若 \(a \neq b\)，对于其它 \(n – 2\) 个数的每种选法中，有 \(1\) 的贡献，有 \(2 ^ {n – 2}\) 种选法；若 \(a = b\)，对于其它 \(n – 2\) 个数的每种选法中，有 \(1\) 的贡献，有 \(2 ^ {n – 1}\) 种选法
右式含义中的两种情况的并集等于左式含义中的情况，故两种含义等价
证毕
证明 2 ( 公式法 )
由 公式 2 \(\dbinom {n} {k} = \dfrac {n} {k} \dbinom {n – 1} {k – 1}\) 得：
\sum \limits _ {k = 0} ^ {n} k ^ 2 \dbinom {n} {k} & = 0 + \sum \limits _ {k = 1} ^ {n} k ^ 2 \times \dfrac {n} {k} \dbinom {n – 1} {k – 1} \\
& = \sum \limits _ {k = 1} ^ {n} k ^ 2 \times \dfrac {n} {k} \dbinom {n – 1} {k – 1} \\
& = \sum \limits _ {k = 1} ^ {n} k \times n \dbinom {n – 1} {k – 1} \\
& = n \sum \limits _ {k = 1} ^ {n} k \dbinom {n – 1} {k – 1} \\
& = n \sum \limits _ {k = 0} ^ {n – 1} (k + 1) \dbinom {n – 1} {k} \\
& = n \sum \limits _ {k = 0} ^ {n – 1} k \dbinom {n – 1} {k} + n \sum \limits _ {k = 0} ^ {n – 1} \dbinom {n – 1} {k} \\
\end{aligned}
\]
由 公式 6 \(\sum \limits _ {k = 0} ^ {n} k \dbinom {n} {k} = n 2 ^ {n – 1}\) 得：\(\sum \limits _ {k = 0} ^ {n – 1} k \dbinom {n – 1} {k} = (n – 1) 2 ^ {n – 2}\)
由 公式 4 \(\sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} = 2 ^ n\) 得：\(\sum \limits _ {k = 0} ^ {n – 1} \dbinom {n – 1} {k} = 2 ^ {n – 1}\)
故原式可化为：
\sum \limits _ {k = 0} ^ {n} k ^ 2 \dbinom {n} {k} & = n \sum \limits _ {k = 0} ^ {n – 1} k \dbinom {n – 1} {k} + n \sum \limits _ {k = 0} ^ {n – 1} \dbinom {n – 1} {k} \\
& = n (n – 1) 2 ^ {n – 2} + n 2 ^ {n – 1} \\
& = n (n – 1) 2 ^ {n – 2} + n \times 2 \times 2 ^ {n – 2} \\
& = n (n + 1) 2 ^ {n – 2} \\
\end{aligned}
\]
证毕
公式 8 ( 变上项求和 )
\]
证明 ( 组合意义 )
在 \(n + 1\) 个小球中选择 \(k + 1\) 个
对于所有选法中，考虑选择的最后一个小球的位置为 \(l + 1(0 \leq l \leq n)\) 时对答案的贡献，就是在前 \(l\) 个小球中选择 \(k\) 的方案数
因此，对于所有的 \(l\) 属于的集合的并集，就等于在 \(n + 1\) 个小球中选择 \(k + 1\) 个的集合
证毕
公式 9
\]
证明 ( 组合意义 )
把 \(n\) 个球分成 \(3\) 堆，使得第 \(1\) 堆有 \(k\) 个球、第 \(2\) 堆有 \(r – k\) 个球、第 \(3\) 堆有 \(n – r\) 个球 的方案数
- 左式含义：先从这 \(n\) 个球中选出 \(r\) 个球，把剩下的 \(n – r\) 个分到第 \(3\) 堆；再从这 \(r\) 个中选择 \(k\) 个分到第 \(1\) 堆，剩下的 \(r – k\) 给分到第 \(2\) 堆
- 右式含义：先从这 \(n\) 个球中选出 \(k\) 个球分到第 \(1\) 堆；再从剩下的 \(n – k\) 个中选择 \(r – k\) 个分到第 \(2\) 堆，剩下的 \(n – r\) 给分到第 \(3\) 堆
显然，两种含义不会重复，并且两种含义等价
证毕
公式 10
\]
证明 ( 组合意义 )
- 右式含义：从 \(m + n\) 个球中选出 \(r\) 个球
- 左式含义：从前 \(m\) 个球中选出 \(k\) 个球和从后 \(n\) 个球中选出 \(r – k\) 个球的并集的并集（第一个并集对于每个 \(k\) 的方案数，第二个并集对于 \(\sum\)）
显然，两种含义等价
证毕
公式 11
\]
证明 ( 公式法 )
\sum \limits _ {k = 0} ^ {m} \dbinom {m} {k} \dbinom {n} {k} & = \sum \limits _ {k = 0} ^ {m} \dbinom {m} {m – k} \dbinom {n} {k} \\
\end{aligned}
\]
由 公式 10 \(\sum \limits _ {k = 0} ^ {r} \dbinom {m} {k} \dbinom {n} {r – k} = \dbinom {m + n} {r}\) 得 \(\sum \limits _ {k = 0} ^ {r} \dbinom {m} {r – k} \dbinom {n} {k} = \dbinom {n + m} {r}\)，令 \(r = m\) 得：\(\sum \limits _ {k = 0} ^ {m} \dbinom {m} {m – k} \dbinom {n} {k} = \dbinom {m + n} {m}\)，故
\sum \limits _ {k = 0} ^ {m} \dbinom {m} {k} \dbinom {n} {k} & = \sum \limits _ {k = 0} ^ {m} \dbinom {m} {m – k} \dbinom {n} {k} \\
& = \dbinom {m + n} {m} \\
\end{aligned}
\]
证毕
课后习题
习题 1
\({(3x – 2y)} ^ {18}\) 的展开式中，\(x ^ 5 y ^ {13}\) 的系数是多少？\(x ^ 8 y ^ 9\) 的系数是多少？
答案
解：
\(x ^ 5 y ^ {13}\) 的系数为 \(\dbinom {18} {5} (3 ^ 5 + 2 ^ {13})\)，\(x ^ 8 y ^ 9\) 的系数为 \(0\)
习题 2
- 用二项式定理证明：\(3 ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} 2 ^ k\)
- 对于任意实数 \(r\) 求 $ \sum \limits _ {k = 0} ^ n \dbinom {n} {k} r ^ k$
答案
-
证：
由 二项式定理常用形式 得：\({(x + 1)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k\)
令 \(x = 2\)，则等式变为 \({(2 + 1)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} 2 ^ k\)，即 \(3 ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} 2 ^ k\)
证毕 -
解：
由 二项式定理常用形式 得：$ \sum \limits _ {k = 0} ^ n \dbinom {n} {k} r ^ k = {(r + 1)} ^ n$
习题 3
用 二项式定理 证明：\(2 ^ n = \sum \limits _ {k = 0} ^ {n} {(- 1)} ^ k \dbinom {n} {k} 3 ^ {n – k}\)
答案
证：
由 二项式定理 得：\({(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n – k}\)
令 \(x = -1, y = 3\)，则等式变为 \({[(-1) + 3]} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-1)} ^ k 3 ^{n – k}\)
即 \(2 ^ n = \sum \limits _ {k = 0} ^ {n} {(- 1)} ^ k \dbinom {n} {k} 3 ^ {n – k}\)
证毕
习题 4
求 $ \sum \limits _ {k = 1} ^ n {(-1)} ^ k \dbinom {n} {k} {10} ^ k$
答案
解：
$ \sum \limits _ {k = 0} ^ n {(-1)} ^ k \dbinom {n} {k} {10} ^ k = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-10)} ^ k$
由 二项式定理常用形式 得：\({(x + 1)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k\)
令 \(x = -10\)，则等式变为 \({[(-10) + 1]} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-10)} ^ k\)
故 $ \sum \limits _ {k = 0} ^ n \dbinom {n} {k} {(-10)} ^ k = {(-9)} ^ n$
习题 5
用组合意义证明 \(\dbinom {n} {k} – \dbinom {n – 3} {k} = \dbinom {n – 1} {k – 1} + \dbinom {n – 2} {k – 1} + \dbinom {n – 3} {k – 1}\)
答案
证：
选择 \(n\) 个小球中的 \(k\) 个
- 左式含义：( 总方案数 ) \(-\) ( 前 \(3\) 个小球都不选的方案数 )，即表示至少选择前 \(3\) 个小球中的一个的方案数
- 右式含义：( 选择第 \(1\) 个小球的方案数 ) \(+\) ( 不选择第 \(1\) 个小球，选择第 \(2\) 个小球的方案数 ) \(+\) ( 不选择第 \(1\) 个小球和第 \(2\) 个小球，选择第 \(3\) 个小球的方案数 )
显然，这两个含义是等价的
证毕
习题 6
设 \(n\) 是正整数，请证明：
\begin{cases}
0, n = 2m + 1, m \in N_+ \\
{(-1)} ^ m \dbinom {2m} {m}, n = 2m, m \in N_+ \\
\end{cases}
\]
答案
证：
如果 \(n\) 是奇数，则 \(k\) 和 \(n – k\) 是不同奇偶的
\(\therefore\) \({(-1)} ^ k\) 和 \({(-1)} ^ {n – k}\) 是一正一负的
\sum \limits _ {k = 0} ^ n {(-1)} ^ k {\dbinom {n} {k}} ^ 2 & = \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} {k} + \sum \limits _ {k = m + 1} ^ {n} {(-1)} ^ k \dbinom {n} {k} \\
& = \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} {k} – \sum \limits _ {k = m + 1} ^ {n} {(-1)} ^ {n – k} \dbinom {n} {n – k} \\
& = \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} {k} – \sum \limits _ {k = 0} ^ {m} {(-1)} ^ k \dbinom {n} k \\
& = 0 \\
\end{aligned}
\]
如果 \(n\) 是偶数，则 \(k\) 和 \(n – k\) 是同奇偶的
\(\therefore\) \({(-1)} ^ k = {(-1)} ^ {n – k}\)
由 二项式定理 得：
{(x + 1)} ^ n & = \sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} x ^ k \\
{(x – 1)} ^ n & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ {n – k} \dbinom {n} {k} x ^ k \\
& =\sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ k \\
{(x ^ 2 – 1)} ^ n & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ {n – k} \dbinom {n} {k} {(x ^ 2)} ^ k \\
& = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} {(x ^ 2)} ^ k \\
& = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ {2k} \\
\end{aligned}
\]
故可列等式 \({(x + 1)} ^ n {(x – 1)} ^ n = {(x ^ 2 – 1) ^ n}\)
{(x + 1)} ^ n {(x – 1)} ^ n & = {(x ^ 2 – 1) ^ n} \\
\sum \limits _ {k = 0} ^ {n} \dbinom {n} {k} x ^ k \times \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ k & = \sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ {2k} \\
\end{aligned}
\]
\(\because\) 左右两边多项式相等
\(\therefore \forall i\)，\(x ^ i\) 的系数相等
令 \(i = n = 2m\)，即考虑 \(x ^ n\) 的系数
\sum \limits _ {k = 0} ^ {n} \dbinom {n} {n – k} x ^ {n – k} \times {(-1)} ^ k \dbinom {n} {k} x ^ k & = {(-1)} ^ m \dbinom {n} {m} x ^ n \\
\sum \limits _ {k = 0} ^ {n} {(-1)} ^ k \dbinom {n} {k} x ^ {n – k} \times \dbinom {n} {k} x ^ k & = {(-1)} ^ m \dbinom {n} {m} x ^ n \\
\sum \limits _ {k = 0} ^ {n} {(-1)} ^ k {\dbinom {n} {k}} ^ 2 x ^ n & = {(-1)} ^ m \dbinom {n} {m} x ^ n \\
\sum \limits _ {k = 0} ^ {n} {(-1)} ^ k {\dbinom {n} {k}} ^ 2 x ^ n & = {(-1)} ^ m \dbinom {2m} {m} x ^ n \\
\end{aligned}
\]
同时约去 \(x ^ n\)，得
\sum \limits _ {k = 0} ^ {n} {(-1)} ^ k {\dbinom {n} {k}} ^ 2 & = {(-1)} ^ m \dbinom {2m} {m} \\
\end{aligned}
\]
证毕
习题 7
化简 \(\dbinom {n} {k} + 3 \dbinom {n} {k – 1} + 3 \dbinom {n} {k – 2} + \dbinom {n} {k – 3}\)
答案
证：
$\dbinom {n} {k} + 3 \dbinom {n} {k – 1} + 3 \dbinom {n} {k – 2} + \dbinom {n} {k – 3} = \dbinom {3} {0} \dbinom {n} {k} + \dbinom {3} {1} \dbinom {n} {k – 1} + \dbinom {3} {2} \dbinom {n} {k – 2} + \dbinom {3} {3} \dbinom {n} {k – 3} = $
有 \(2\) 堆小球，第 \(1\) 堆有 \(3\) 个，第 \(2\) 堆有 \(n\) 个
在 \(n + 3\) 个小球中选择 \(k\) 个，等价于 ( 在第 \(1\) 堆选择 \(0\) 个，第 \(2\) 堆选择 \(k\) 个 ) + ( 在第 \(1\) 堆选择 \(1\) 个，第 \(2\) 堆选择 \(k – 1\) 个 ) + ( 在第 \(1\) 堆选择 \(2\) 个，第 \(2\) 堆选择 \(k – 2\) 个 ) + ( 在第 \(1\) 堆选择 \(3\) 个，第 \(2\) 堆选择 \(k – 3\) 个)
证毕
习题 8
证明 \(\dbinom {r} {k} = \dfrac {r} {r – k} \dbinom {r – 1} {k}\)，其中 \(r \in R\)，\(k \in Z\)，\(r \neq k\)
答案
本题需要使用牛顿二项式，不符合本博客的讨论范围
习题 9
求：\(1 – \dfrac {1} {2} \dbinom {n} {1} + \dfrac {1} {3} \dbinom {n} {2} – \dfrac {1} {4} \dbinom {n} {3} + \cdots + {(-1)} ^ n \dfrac {1} {n + 1} \dbinom {n} {n}\)
答案
解：
1 – \dfrac {1} {2} \dbinom {n} {1} + \dfrac {1} {3} \dbinom {n} {2} – \dfrac {1} {4} \dbinom {n} {3} + \cdots + {(-1)} ^ n \dfrac {1} {n + 1} \dbinom {n} {n} & = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {k + 1} \dbinom {n} {k} \\
\end{aligned}
\]
由 公式 2 \(\dbinom {n + 1} {k + 1} = \dfrac {n + 1} {k + 1} \dbinom {n} {k}\) 得：\(\dbinom {n} {k} = \dfrac {k + 1} {n + 1} \dbinom {n + 1} {k + 1}\)
\sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {k + 1} \dbinom {n} {k} & = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {k + 1} \times \dfrac {k + 1} {n + 1} \dbinom {n + 1} {k + 1} \\
& = \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dfrac {1} {n + 1} \dbinom {n + 1} {k + 1} \\
& = \dfrac { \sum \limits _ {k = 0} ^ n {(-1)} ^ k \times \dbinom {n + 1} {k + 1}} {n + 1} \\
& = -\dfrac { \sum \limits _ {k = 0} ^ n {(-1)} ^ {k + 1} \times \dbinom {n + 1} {k + 1}} {n + 1} \\
& = -\dfrac { \sum \limits _ {k = 1} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k}} {n + 1} \\
& = -\dfrac { \sum \limits _ {k = 0} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k} – {(-1)} ^ 0 \times \dbinom {n + 1} {0}} {n + 1} \\
& = -\dfrac { \sum \limits _ {k = 0} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k} – 1} {n + 1} \\
\end{aligned}
\]
由 公式 5 $ \sum \limits _ {k = 0} ^ n {(-1)}^k \dbinom {n} {k} = 0$ 得：$ \sum \limits _ {k = 0} ^ {n + 1} {(-1)}^k \dbinom {n + 1} {k} = 0$
-\dfrac { \sum \limits _ {k = 0} ^ {n + 1} {(-1)} ^ k \times \dbinom {n + 1} {k} – 1} {n + 1} & = – \dfrac {0 – 1} {n + 1} \\
& = – \dfrac {-1} {n + 1} \\
& = \dfrac {1} {n + 1} \\
\end{aligned}
\]
\(\therefore 1 – \dfrac {1} {2} \dbinom {n} {1} + \dfrac {1} {3} \dbinom {n} {2} – \dfrac {1} {4} \dbinom {n} {3} + \cdots + {(-1)} ^ n \dfrac {1} {n + 1} \dbinom {n} {n} = \dfrac {1} {n + 1}\)
习题 10
- 证明：\(\dbinom {n + 1} {k + 1} = \dbinom {0} {k} + \dbinom {1} {k} + \cdots + \dbinom {n – 1} {k} + \dbinom {n} {k}\)
- 证明：\(m ^ 2 = 2 \dbinom {m} {2} + \dbinom {m} {1}\)
答案
- 证：
\(\dbinom {n + 1} {k + 1} = \dbinom {0} {k} + \dbinom {1} {k} + \cdots + \dbinom {n – 1} {k} + \dbinom {n} {k} = \sum \limits _ {i = 0} ^ {n} \dbinom {i} {k}\)
在 \(n + 1\) 个小球中选择 \(k + 1\) 个的方案数，等价于 ( 枚举选择的最后一个小球的位置，在这个小球前选择 \(k\) 个小球 ) 的方案数之和
证毕 - 证：
( 在 \(m\) 个不同的数中先后选择 \(2\) 个可以相同的数的方案数，组成一个有序数对 )，等价于 ( 选择不同的 \(2\) 个数组成 \(2\) 个有序数对 ) 和 ( 选择 \(1\) 个数组成 \(1\) 个有序数对 ) 的方案数之和
证毕
习题 11
求整数 \(a, b, c\)，使得对于所有的 \(m\)，满足：\(m ^ 3 = a \dbinom {m} {3} + b \dbinom {m} {2} + c \dbinom {m} {1}\)
答案
解：
( 在 \(m\) 个不同的数中先后选择 \(3\) 个可以相同的数的方案数，组成一个有序数对 )，等价于 ( 选择不同的 \(3\) 个数组成 \(6\) 个有序数对 )、( 选择不同的 \(2\) 个数组成 \(6\) 个有序数对 )、( 选择 \(1\) 个数组成 \(1\) 个有序数对 ) 的方案数之和
\(\therefore m ^ 3 = 6 \times \dbinom {m} {3} + 6 \times \dbinom {m} {2} + 1 \times \dbinom {m} {1}\)
\(\therefore a = 6, b = 6, c = 1\)
习题 12
设 \(n\) 是整数，请证明 \(\sum \limits _ {k = 1} ^ {n} \dbinom {n} {k} \dbinom {n} {k – 1} = \dfrac {1} {2} \dbinom {2n + 2} {n + 1} – \dbinom {2n} {n}\)
答案
证：
\sum \limits _ {k = 1} ^ {n} \dbinom {n} {k} \dbinom {n} {k – 1} & = \sum \limits _ {k = 1} ^ {n} \dbinom {n} {n – k} \dbinom {n} {k – 1} \\
\dfrac {1} {2} \dbinom {2n + 2} {n + 1} – \dbinom {2n} {n} & = \dfrac {1} {2} \times \dfrac {2n + 2} {n + 1} \dbinom {2n + 1} {n} – \dbinom {2n} {n} \\
& = \dfrac {1} {2} \times 2 \dbinom {2n + 1} {n} – \dbinom {2n} {n} \\
& = \dbinom {2n + 1} {n} – \dbinom {2n} {n} \\
& = \dbinom {2n} {n – 1} \\
\end{aligned}
\]
即证 \(\sum \limits _ {k = 1} ^ {n} \dbinom {n} {n – k} \dbinom {n} {k – 1} = \dbinom {2n} {n – 1}\)
- 右式含义：在 \(2n\) 个小球中选择 \(n – 1\) 个的方案数
- 左式含义：( 在前 \(n\) 个小球中选择 \(n – k\) 个 ) 和 ( 在后 \(n\) 个小球中选择 \(k – 1\) 个 ) 的方案数之和；\(\because 1 \leq k \leq n\)，\(\therefore n – k, k – 1 \geq 0\)，故此含义成立
显然，左右两式等价
证毕
习题 13
设 \(n\) 是整数，请用组合意义证明 \(\sum \limits _ {k = 1} ^ {n} k {\dbinom {n} {k}} ^ 2 = n \dbinom {2n – 1} {n – 1}\)
答案
证：
\sum \limits _ {k = 1} ^ {n} k {\dbinom {n} {k}} ^ 2 & = \sum \limits _ {k = 1} ^ {n} k \dbinom {n} {k} \dbinom {n} {n – k} \\
& = \sum \limits _ {k = 1} ^ {n} k \times \dfrac {n} {k} \dbinom {n – 1} {k – 1} \dbinom {n} {n – k} \\
& = \sum \limits _ {k = 1} ^ {n} n \dbinom {n – 1} {k – 1} \dbinom {n} {n – k} \\
& = n \sum \limits _ {k = 1} ^ {n} \dbinom {n – 1} {k – 1} \dbinom {n} {n – k} \\
& = n \sum \limits _ {k = 1} ^ {n} \dbinom {n} {n – k} \dbinom {n – 1} {k – 1} \\
\end{aligned}
\]
即证 \(n \sum \limits _ {k = 1} ^ {n} \dbinom {n} {n – k} \dbinom {n – 1} {k – 1} = n \dbinom {2n – 1} {n – 1}\)
即证 \(\sum \limits _ {k = 1} ^ {n} \dbinom {n} {n – k} \dbinom {n – 1} {k – 1} = \dbinom {2n – 1} {n – 1}\)
- 右式含义：在 \(2n – 1\) 个小球中选择 \(n – 1\) 个的方案数
- 左式含义：( 在前 \(n\) 个小球中选择 \(n – k\) 个 ) 和 ( 在后 \(n – 1\) 个小球中选择 \(k – 1\) 个 ) 的方案数之和；\(\because 1 \leq k \leq n\)，\(\therefore n – k, k – 1 \geq 0\)，故此含义成立
显然，左右两式等价
证毕
