# Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?

-
Do you mean $\sum_k \binom{n-k}{k}$ for the sum? – Mike Spivey Oct 19 '11 at 5:26
@Mike: Those coincide for suitable ranges of $k$. – joriki Oct 19 '11 at 5:38
In fact in a sense the version in the question is nicer in that you can let $k$ run from $0$ to infinity. – joriki Oct 19 '11 at 5:44
@anon, joriki: Yes, you both are right. – Mike Spivey Oct 19 '11 at 6:24

Expanding as a geometric series and then using the Binomial Theorem, we obtain $$\sum_{k=0}^\infty (x^2+x)^k=\sum_{k=0}^\infty \sum_{l=0}^k{k\choose l}x^{2l+(k-l)}=\sum_{n=0}^\infty\left(\sum_{k+l=n}{k\choose l}\right)x^n$$ Rewrite the inner sum's index $l=n-k$ so that equating coefficients with $\sum F_n x^n$ gives $$F_n=\sum_{k} {k\choose n-k}.$$