今天 jijidawang 找我问一个式子：
\[\sum\limits^n_{i=0}\binom{n}{i}f_i=f_{2n}
\]
其中 \(f_0=1\, ,\, f_1=1\, ,\, f_{n}=f_{n-1}+f_{n-2}\,(n\ge 2)\)
设 $$S(n,m)=\sum\limits^n_{i=0}\binom{n}{i}f_{i+m}$$
那么我们要求的就是 \(S(n,0)\)
观察到这个东西可以做出以下转换
\[\begin{aligned}
\sum\limits^n_{i=0}\binom{n}{i}f_{i+m} &= \sum\limits^n_{i=0}\left(\binom{n-1}{i-1}+\binom{n-1}{i}\right)f_{i+m}\\
&= \sum\limits^n_{i=0}\binom{n-1}{i}f_{i+m+1}+\binom{n-1}{i}f_{i+m}\\
&= \sum\limits^{n-1}_{i=0}\binom{n-1}{i}f_{i+m+2}\\
\end{aligned}
\]
所以对于 \(S\) 来说有如下递归式 \(S(n,m)=S(n-1,m+2)\)，然后存在终止状态 \(S(0,m)=f_m\)
那么这个递归式能导出如下结果 \(S(n,m)=S(0,m+2n)=f_{m+2n}\)，所以我们以加强版解出了这个式子