计算小练习 4+i

· · 个人记录

试给出

\sum_{k=0}^n\binom{2n-k}{k}(-1)^k2^{2n-2k}

的封闭形式。

先计算下式：

F_n(x)=\sum_{k= 0}^n\binom{2n-k}{k}x^k

可以考虑从二项式系数的递推入手：

f_{n,k}=\binom{2(n-1)-(k-1)}{k-1}+\binom{2n-k-1}{k} =f_{n-1,k-1}+\binom{2(n-1)-k}{k}+\binom{2n-k-2}{k-1} =f_{n-1,k-1}+f_{n-1,k}+\binom{2(n-1)-(k-1)}{k-1}-\binom{2(n-2)-(k-2)}{k-2} =2f_{n-1,k-1}+f_{n-1,k}-f_{n-2,k-2}

也就有迭代式

F_n(x)=(1+2x)F_{n-1}(x)-x^2F_{n-2}(x)

直接得到

G(x,y)=\sum_{n\geq 0}F_n(x)y^n=\frac{1-xy}{1-(1+2x)y+x^2y^2}

我们要求的答案也就是

4^n[y^n]G(-1/4,y)=[y^n]\frac{4(4+4y)}{(4-4y)^2}=[y^n]\frac{1+y}{(1-y)^2}=2n+1