求和式中含组合项的表达式化简问询

嘿，这个问题我之前也碰到过类似的，咱们一步步拆解就清晰啦！

首先，先把求和式里和i无关的常数拎出来——你看，$2^k$跟i一点关系都没有，完全可以提到求和符号的外面，这样原式就变成：
$$2^k \times \sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} \binom{k-i}{i}$$
现在问题就简化成了处理后面这个求和项$\sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} \binom{k-i}{i}$，咱们把它记为$S(k)$。

接下来重点看$S(k)$，其实它和斐波那契数列直接相关！咱们先算几个小的k值验证下：

• 当k=0时，$\lfloor 0/2 \rfloor=0$，$S(0)=\binom{0-0}{0}=1$
• 当k=1时，$\lfloor 1/2 \rfloor=0$，$S(1)=\binom{1-0}{0}=1$
• 当k=2时，i可以取0和1，$S(2)=\binom{2}{0}+\binom{1}{1}=1+1=2$
• 当k=3时，i可以取0和1，$S(3)=\binom{3}{0}+\binom{2}{1}=1+2=3$
• 当k=4时，i可以取0、1、2，$S(4)=\binom{4}{0}+\binom{3}{1}+\binom{2}{2}=1+3+1=5$

是不是看着眼熟？这就是标准的斐波那契数列呀！如果咱们定义斐波那契数列$F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5,...$，那$S(k)=F(k+1)$。

那怎么证明这个递推关系呢？咱们可以用组合恒等式推导：
对于k≥2，$S(k)=\sum_{i=0}^{\lfloor k/2 \rfloor} \binom{k-i}{i}$，拆成第一项$\binom{k}{0}=1$加上后面的求和项。后面的$\binom{k-i}{i}$可以用组合恒等式$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$，这里n=k-i，m=i，所以$\binom{k-i}{i}=\binom{(k-1)-i}{i}+\binom{(k-1)-i}{i-1}$。把这个代入求和后，拆分得到两个求和：

• 第一个求和加上前面的$\binom{k-1}{0}$，正好就是$S(k-1)$
• 第二个求和换元后，就变成$\sum_{j=0}^{\lfloor (k-2)/2 \rfloor} \binom{(k-2)-j}{j}=S(k-2)$

所以得到递推式$S(k)=S(k-1)+S(k-2)$，结合初始条件$S(0)=1=F(1)$，$S(1)=1=F(2)$，就完全对应上斐波那契数列的$F(k+1)$啦！

现在把斐波那契数列的通项公式（比内公式）代入，$F(n)=\frac{\phi^n - \psi^{n}{\sqrt{5}}$，其中$\phi=\frac{1+\sqrt{5}}{2}$（黄金分割比），$\psi=\frac{1-\sqrt{5}}{2}$。那$S(k)=F(k+1)=\frac{\phi}{k+1}-\psi^{k+1}}{\sqrt{5}}$。

最后把这个代回原来的表达式，就得到化简结果：
$$2^k \times \frac{\phi^{k+1}-\psi{k+1}}{\sqrt{5}} = \frac{(1+\sqrt{5})^{k+1} - (1-\sqrt{5})^{k+1}}{2\sqrt{5}}$$
（这里把$\phi$和$\psi$代入后，$2^{k$和分母的$2}{k+1}$约掉了1/2，整理后就得到这个更简洁的形式）

如果你更喜欢用递推形式表达，那原式也可以写成$2^k \times F(k+1)$，其中F是斐波那契数列，两种形式都可以，看你需求~

备注：内容来源于stack exchange，提问作者Laura