对任何正整数 $n$，求证：$\displaystyle \sum\limits_{k=0}^{n} C_{n}^{k} 2^{k} C_{n-k}^{\left[\frac{n-k}{2}\right]}=C_{2 n+1}^{n}$
其中 $C_{0}^{0}=1,\left[\dfrac{n-k}{2}\right]$ 表示 $\dfrac{n-k}{2}$ 的整数部分．
其中 $C_{0}^{0}=1,\left[\dfrac{n-k}{2}\right]$ 表示 $\dfrac{n-k}{2}$ 的整数部分．
【难度】
【出处】
1994第9届CMO试题
【标注】
【答案】
略
【解析】
证法一
考虑多项式 $(x+1)^{2n}$，它的 $x^n$ 及 $x^{n-1}$ 的系数和为
$C_{2 n}^{n}+C_{2 n}^{n-1}=C_{2 n+1}^{n}$ ①
另一方面 $\displaystyle (x+1)^{2 n}=\left(x^{2}+2 x+1\right)^{n}=\sum\limits_{i+j+k=n} \dfrac{n !}{i ! j ! k !}\left(x^{2}\right)^{i}(2 x)^{j}=\sum_{0 \leqslant i+j \in n} \dfrac{n !}{i ! j !(n-i-j) !} 2^{j} x^{2 i+j}$ ②
这里 $i,j, k$ 均为非负整数．式 ② 右端 $x^n$ 及 $x^{n-1}$ 的系数之和是
$\displaystyle \sum\limits_{0 \leqslant i+j \leqslant n \atop 2 i+j=n} \dfrac{n !}{i ! j !(n-i-j) !} 2^{j}+\sum_{0 \leqslant i+j \in n \atop 2 i+j=n-1} \dfrac{n !}{i ! j !(n-i-j) !} 2^{j}=\sum_{0\leqslant i+(n-2 i)\leqslant n} \frac{n !}{i !(n-2 i) ! i !} 2^{n-2 i}\\+\sum\limits_{0 \leqslant i+(n-1-2 i) \leqslant n} \dfrac{n !}{i !(n-1-2 i) !(i+1) !} 2^{n-2 i-1}=\sum\limits_{i=0}^{[\frac{n}{2}]} C_{n}^{2 i} C_{2 i}^{i} 2^{n-2 i}+\sum\limits_{i=0}^{\left[\frac{n-1}{2}\right]} C_{n}^{2 i+1} C_{2 i+1}^{i} 2^{n-2 i-1}\\=\sum\limits_{k=0,k取偶数}^{n} C_{n}^{k} 2^{n-k} C_{k}^{\left(\frac{k}{2}\right]}+\sum\limits_{k=1,k取奇数}^{n} C_{n}^{k} 2^{n-k} C_{k}^{\left(\frac{k}{2}\right]}=\sum_\limits{k=0}^{n} C_{n}^{k} 2^{n-k} C_{k}^{\left[\frac{k}{2}\right]} ③ $
在上式右端，令 $n-k=s$，那么，有
$\displaystyle \sum\limits_{k=0}^{n} C_{n}^{k} 2^{n-k} C_{k}^{ [\frac{k}{2} ]}=\sum_{s=0}^{n} C_{n}^{n-s} 2^{s} C_{n-3}^{\left[\frac{n-s}{2}\right]}=\sum_{k=0}^{n} C_{n}^{k} 2^{k} C_{n-k}^{\left[\frac{n-k}{2}\right]}$ ④
由于 $C_{n}^{n-s}=C_{n}^{s}$，把 $ s $ 改写为 $ k$，可得上式最后一个等式．从而得到所要证明的恒等式．
证法二
有 $2 n + 1$ 个人，其中一位老师，$ n$ 位男同学，$n$ 位女同学．老师记为 $T$，$n$ 位男同学分别记为 $a_{1}, a_{2}, \cdots, a_{n}$，$n$ 位女同学分别记为 $b_{1}, b_{2}, \cdots, b_{n}$．$\left(a_{i}, b_{i}\right)$ 称为"一对"，$\dot{i}=1,2, \cdots, n$．现在有 $n$ 个人去参加植树劳动．有两种选人方法：
（1）$2 n + 1$ 个人中任选 $n$ 人，那么有 $C_{2 n+1}^{n}$ 种选人方法．
（2）固定 $k$，这里 $0\leqslant k\leqslant n$，在 $n$ 对学生中任选 $k$ 对，要求每对只去一人．对每个 $ k $，有 $ C_{n}^{k} 2^{k} $ 种选法．其余的 $ n- k $ 名同学是要一对一对地去植树的．由于一共只能去 $ n $ 人，所以只有 $ \left[\dfrac{n-k}{2}\right] $ 对同学去植树，有 $ C_{n-k}^{\left[\frac{n-k}{2}\right]}$ 种选对方案．
这时，去植树的同学总人数是 $k + 2[\dfrac{n-k}{2}]$ 当 $n-k$ 为奇数时 $k+2\left[\dfrac{n-k}{2}\right]=n-1$
由于一共要有 $n$ 个人去植树，老师 $T$ 必须去．当 $n-k$ 为偶数时 $k+2\left[\dfrac{n-k}{2}\right]=n$
受总人数限制，老师 $T$ 不去植树．那么当 $k$ 固定时，不同的选人方案数为 $\mathrm{C}_{\mathrm{n}}^{k} 2^{k} \mathrm{C}_{n-k}^{\left[\frac{n-k}{2}\right]}$，当 $k$ 取遍 $0,1,2, \cdots, n$ 时，所有的选人方案总数是应当等于 $C_{2 n+1}^{n}$．那么，有 $\displaystyle \sum\limits_{k=0}^{n} C_{n}^{k} 2^{k} C_{n-k}^{\left[\frac{n-k}{2}\right]}=C_{2 n+1}^{n}$
考虑多项式 $(x+1)^{2n}$，它的 $x^n$ 及 $x^{n-1}$ 的系数和为
$C_{2 n}^{n}+C_{2 n}^{n-1}=C_{2 n+1}^{n}$ ①
另一方面 $\displaystyle (x+1)^{2 n}=\left(x^{2}+2 x+1\right)^{n}=\sum\limits_{i+j+k=n} \dfrac{n !}{i ! j ! k !}\left(x^{2}\right)^{i}(2 x)^{j}=\sum_{0 \leqslant i+j \in n} \dfrac{n !}{i ! j !(n-i-j) !} 2^{j} x^{2 i+j}$ ②
这里 $i,j, k$ 均为非负整数．式 ② 右端 $x^n$ 及 $x^{n-1}$ 的系数之和是
$\displaystyle \sum\limits_{0 \leqslant i+j \leqslant n \atop 2 i+j=n} \dfrac{n !}{i ! j !(n-i-j) !} 2^{j}+\sum_{0 \leqslant i+j \in n \atop 2 i+j=n-1} \dfrac{n !}{i ! j !(n-i-j) !} 2^{j}=\sum_{0\leqslant i+(n-2 i)\leqslant n} \frac{n !}{i !(n-2 i) ! i !} 2^{n-2 i}\\+\sum\limits_{0 \leqslant i+(n-1-2 i) \leqslant n} \dfrac{n !}{i !(n-1-2 i) !(i+1) !} 2^{n-2 i-1}=\sum\limits_{i=0}^{[\frac{n}{2}]} C_{n}^{2 i} C_{2 i}^{i} 2^{n-2 i}+\sum\limits_{i=0}^{\left[\frac{n-1}{2}\right]} C_{n}^{2 i+1} C_{2 i+1}^{i} 2^{n-2 i-1}\\=\sum\limits_{k=0,k取偶数}^{n} C_{n}^{k} 2^{n-k} C_{k}^{\left(\frac{k}{2}\right]}+\sum\limits_{k=1,k取奇数}^{n} C_{n}^{k} 2^{n-k} C_{k}^{\left(\frac{k}{2}\right]}=\sum_\limits{k=0}^{n} C_{n}^{k} 2^{n-k} C_{k}^{\left[\frac{k}{2}\right]} ③ $
在上式右端，令 $n-k=s$，那么，有
$\displaystyle \sum\limits_{k=0}^{n} C_{n}^{k} 2^{n-k} C_{k}^{ [\frac{k}{2} ]}=\sum_{s=0}^{n} C_{n}^{n-s} 2^{s} C_{n-3}^{\left[\frac{n-s}{2}\right]}=\sum_{k=0}^{n} C_{n}^{k} 2^{k} C_{n-k}^{\left[\frac{n-k}{2}\right]}$ ④
由于 $C_{n}^{n-s}=C_{n}^{s}$，把 $ s $ 改写为 $ k$，可得上式最后一个等式．从而得到所要证明的恒等式．
证法二
有 $2 n + 1$ 个人，其中一位老师，$ n$ 位男同学，$n$ 位女同学．老师记为 $T$，$n$ 位男同学分别记为 $a_{1}, a_{2}, \cdots, a_{n}$，$n$ 位女同学分别记为 $b_{1}, b_{2}, \cdots, b_{n}$．$\left(a_{i}, b_{i}\right)$ 称为"一对"，$\dot{i}=1,2, \cdots, n$．现在有 $n$ 个人去参加植树劳动．有两种选人方法：
（1）$2 n + 1$ 个人中任选 $n$ 人，那么有 $C_{2 n+1}^{n}$ 种选人方法．
（2）固定 $k$，这里 $0\leqslant k\leqslant n$，在 $n$ 对学生中任选 $k$ 对，要求每对只去一人．对每个 $ k $，有 $ C_{n}^{k} 2^{k} $ 种选法．其余的 $ n- k $ 名同学是要一对一对地去植树的．由于一共只能去 $ n $ 人，所以只有 $ \left[\dfrac{n-k}{2}\right] $ 对同学去植树，有 $ C_{n-k}^{\left[\frac{n-k}{2}\right]}$ 种选对方案．
这时，去植树的同学总人数是 $k + 2[\dfrac{n-k}{2}]$ 当 $n-k$ 为奇数时 $k+2\left[\dfrac{n-k}{2}\right]=n-1$
由于一共要有 $n$ 个人去植树，老师 $T$ 必须去．当 $n-k$ 为偶数时 $k+2\left[\dfrac{n-k}{2}\right]=n$
受总人数限制，老师 $T$ 不去植树．那么当 $k$ 固定时，不同的选人方案数为 $\mathrm{C}_{\mathrm{n}}^{k} 2^{k} \mathrm{C}_{n-k}^{\left[\frac{n-k}{2}\right]}$，当 $k$ 取遍 $0,1,2, \cdots, n$ 时，所有的选人方案总数是应当等于 $C_{2 n+1}^{n}$．那么，有 $\displaystyle \sum\limits_{k=0}^{n} C_{n}^{k} 2^{k} C_{n-k}^{\left[\frac{n-k}{2}\right]}=C_{2 n+1}^{n}$
答案
解析
备注
