生成函数 证明恒等式

hbghlyj

$m, n ≥ 0$, 恒等式
$$\sum_{k}\binom mk\left(\begin{array}{c}n+k \\ m\end{array}\right)=\sum_{k}\binom mk\binom nk2^k$$
来源: Solution to problems in Mathematical Reflections第2页

hbghlyj

Multiply on the left by $x^n$, sum on $n \geq 0$ and interchange the summations, we find
\begin{aligned}
\sum_k\binom mkx^{-k} \sum_{n \geq 0}\left(\begin{array}{c}
n+k \\
m
\end{array}\right) x^{n+k} & =\sum_k\binom mkx^{-k} \frac{x^m}{(1-x)^{m+1}} \\
& =\frac{x^m}{(1-x)^{m+1}}\left(1+\frac{1}{x}\right)^m \\
& =\frac{(1+x)^m}{(1-x)^{m+1}} .
\end{aligned}Multiply on the right by $x^n$, sum on $n \geq 0$ and interchange the summations, we find
\begin{aligned}
\sum_k\binom mk2^k \sum_{n \geq 0}\binom nk x^n & =\frac{1}{1-x} \sum_k\binom mk\left(\frac{2 x}{1-x}\right)^k \\
& =\frac{1}{1-x}\left(1+\frac{2 x}{1-x}\right)^m \\
& =\frac{(1+x)^m}{(1-x)^{m+1}} .
\end{aligned}gfology