组合数学第五章练习题（部分）
11.
\[\binom{n}{k} - \binom{n - 3}{k} = \binom{n - 1}{k - 1} + \binom{n - 2}{k - 1} + \binom{n - 3}{k - 1} \]理树要在神北私立高级中学的 \(n\) 位女同学中挑选 \(k\) 位后宫，但是他必须走沙耶，佳奈多和撒撒撒撒撒米中的至少一条线，因为这是 LBEX。
12.
\[\begin{aligned} \sum\limits_{k = 0}^{n}(-1)^k\binom{n}{k}^2 = \begin{cases} 0, & \text{若 } n \text{ 是奇数} \\ (-1)^m\binom{2m}{m}, & \text{若 } n = 2m \end{cases} \end{aligned} \]\[\begin{aligned} (1 - x^2)^n &= (1 + x)^n(1 - x)^n \\ \sum\limits_{i = 0}^{n}\binom{n}{i}(-x^2)^{i} &= \left( \sum\limits_{i = 0}^{n}\binom{n}{i}x^i \right)\left( \sum\limits_{i = 0}^{n}\binom{n}{i}(-x)^i \right) \\ \sum\limits_{i = 0}^{n}\binom{n}{i}(-1)^ix^{2i} &= \sum\limits_{i = 0}^{2n}\sum\limits_{k = 0}^{i}(-1)^k\binom{i}{k}\binom{i}{i - k}x^i \\ \end{aligned} \]原式显然。这道卷积应该是前后几道题中最有意思的一道。
13.
\[\begin{aligned} ans = &\binom{n}{k} + 3\binom{n}{k - 1} + 3\binom{n}{k - 2} + \binom{n}{k - 3} \\ &= \sum\limits_{i = 0}^{3}\binom{3}{i}\binom{n}{k - i} = \binom{n + 3}{k} \end{aligned} \]14.
\[\begin{aligned} \frac{r}{r - k}\binom{r - 1}{k} = \frac{r}{r - k}\times \frac{(r - 1)!}{(r - k - 1)!k!} = \frac{r!}{(r - k)!k!} = \binom{r}{k} \end{aligned} \]15.
\[\sum\limits_{i = 1}^{n}(-1)^{i + 1}i\binom{n}{i} = \sum\limits_{i = 1}^{n}(-1)^{i + 1}n\frac{(n - 1)!}{(i - 1)!(n - i)!} = n\sum\limits_{i = 0}^{n - 1}(-1)^i\binom{n - 1}{i}\times 1^{n - i} = 0 \]16.
\[\begin{aligned} (1 + x)^n &= \sum\limits_{i = 0}^{n}\binom{n}{i}x^i \\ \int\limits(1 + x)^ndx &= \sum\limits_{i = 0}^{n}\binom{n}{i}\int\limits{x^idx} \\ \frac{(x + 1)^{n + 1}}{n + 1} + C_1 &= \sum\limits_{i = 0}^{n}\frac{1}{i + 1}\binom{n}{i} x^{i + 1} + C_2 \\ \frac{1}{n + 1}\sum\limits_{i = 1}^{n + 1}\binom{n + 1}{i}x^i &= \sum\limits_{i = 0}^{n}\frac{1}{i + 1}\binom{n}{i} x^{i + 1} \\ &\xrightarrow{x = 1} \\ \sum\limits_{i = 0}^{n}\frac{1}{i + 1}\binom{n}{i} &= \frac{2^{n + 1} - 1}{n + 1} \end{aligned} \]注意积分之后要把左边的常数项舍弃，否则最后推出来会少个 \(-1\)。
17.
16 的另解。
\[\sum\limits_{i = 0}^{n}\frac{1}{i + 1}\binom{n}{i} = \frac{1}{n + 1}\sum\limits_{i = 0}^{n}\binom{n + 1}{i + 1} = \frac{2^{n + 1} - 1}{n + 1} \]18.
\[\begin{aligned} \sum\limits_{i = 0}^{n}(-1)^i\frac{1}{i + 1}\binom{n}{i} &= \frac{1}{n + 1}\sum\limits_{i = 0}^{n}(-1)^i\binom{n + 1}{i + 1} \\ &= \frac{1}{n + 1}\sum\limits_{i = 1}^{n + 1}(-1)^i\binom{n + 1}{i} \\ &= \frac{1}{n + 1}\left(\sum\limits_{i = 0}^{n + 1}(-1)^i\binom{n + 1}{i} - 1 \right) \\ &= -\frac{1}{n + 1} \end{aligned} \]19.
\[2\binom{m}{2} + \binom{m}{1} = 2\left( \binom{m}{2} + \binom{m}{1} \right) - \binom{m}{1} = 2\binom{m + 1}{2} - m = m(m + 1) - m = m^2 \]\[\sum\limits_{i = 1}^{n}i^2 = \sum\limits_{i = 1}^{n}2\binom{i}{2} + \binom{i}{1} = 2\sum\limits_{i = 1}^{n}\binom{i}{2} + \sum\limits_{i = 1}^{n}\binom{i}{1} = 2\binom{n + 1}{3} + \binom{n + 1}{2} \]20.
\[m^3 = \frac{am(m - 1)(m - 2)}{6} + \frac{bm(m - 1)}{2} + cm = \frac{a}{6}m^3 + \frac{b - a}{2}m^2 + \left( \frac{a}{3} - \frac{b}{2} + c \right)m \]\[\begin{aligned} \begin{cases} \frac{a}{6} = 1 \\ \frac{b - a}{2} = 0 \\ \frac{a}{3} - \frac{b}{2} + c = 0 \end{cases} \end{aligned} \]解得 \(a = 6, b = 6, c = 1\)，\(\therefore m^3 = 6\binom{m}{3} + 6\binom{m}{2} + \binom{m}{1}\)。
\[\sum\limits_{i = 1}^{n}i^3 = 6\sum\limits_{i = 1}^{n}\binom{i}{3} + 6\sum\limits_{i = 1}^{n}\binom{i}{2} + \sum\limits_{i = 1}^{n}\binom{i}{1} = 6\binom{n + 1}{4} + 6\binom{n + 1}{3} + \binom{n + 1}{2} \]