记录一些遇到的推式子的技巧

$$ \begin{aligned} \sum_{k}\frac{n!}{\left(n-2k\right)!k!k!}2^{n-2k}&=\sum_k\left[x^{n-2k}y^kz^k\right]\left(2x+y+z\right)^n\\ &=\sum_k\left[y^kz^k\right]\left(2+y+z\right)^n\\ &=\left[y^0\right]\left(2+y+\frac{1}{y}\right)^n\\ &=\left[y^n\right]\left(y^2+2y+1\right)^n\\ &=\left[y^n\right]\left(y+1\right)^{2n}=\binom{2n}{n} \end{aligned} $$

而根据《具体数学》，有

$$ \begin{aligned} \sum_{k}\frac{n!}{\left(n-2k\right)!k!k!}2^{n-2k}&=2^n\sum_k\binom{n/2}{k}\binom{\left(n-1\right)/2}{k}\\ &=2^n\binom{n-1/2}{\left\lfloor n/2\right\rfloor}\\ &=\binom{2n}{n} \end{aligned} $$