今日在 oi-wiki 上看到斐波那契的生成函数，为：

$\sum\limits_{n\ge 0}x^n\sum\limits_{i=0}^n\dbinom{n-i}{i}$。

但是他能用待定系数解出另一个解：

$\dfrac{1}{\sqrt 5}((\dfrac{1+\sqrt 5}{2})^n-(\dfrac{1-\sqrt 5}{2})^n)$。

那么，请问有没有非组合意义的代数方法可以从左式推到右式。请注意，一定是非斐波那契的组合意义。

275307894b 数学很菜，如有答复，不胜感激。

简而意之，求证：

$\sum\limits_{i=0}^n\dbinom{n-i}{i}=\dfrac{1}{\sqrt 5}((\dfrac{1+\sqrt 5}{2})^n-(\dfrac{1-\sqrt 5}{2})^n)$