# How to simplify $F(x)=\sum_{n}^{\infty}\sum_{k}^{\infty}{n-k-1\choose k}x^n$?

This generating function is equivalent to $$\sum_{n}^{\infty}F_n x^n=\dfrac{x}{1-x-x^2}$$

where $F_n$ is a fibonacci number. To show this, I need to simplify the above generating function with binomial coefficients using $$(1-z)^{-\alpha+1}=\sum_{k}^{\infty}{\alpha+k\choose k}z^k$$

I'm familiar with using this conversion, but I can't do it successfully in this case. Please give me a hint for conversion.

EDIT: So, as achille hui suggested, I converted as the following: $$\sum_{s}\sum_{k}{k+s\choose k}x^{s+2k+1}=\sum_{s}x^{s+1}(1-x^2)^{1-s}=x(1-x^2)\dfrac{1}{1-\dfrac{x}{1-x^2}}=\dfrac{x(1-x^2)^2}{1-x-x^2}$$

But the last formula clearly doesn't match with what I expected, which is: $$\sum_{n}^{\infty}F_n x^n=\dfrac{x}{1-x-x^2}$$

Where did I make a mistake?

-
Rewrite $n$ as $2k+1+s$, the coefficient $\binom{n-k-1}{k}$ is non-zero only for $s \ge 0$. If you convert your sum to one over $k$ and $s$, everything should be obvious. – achille hui Jun 6 '14 at 23:09
That makes sense! – Math.StackExchange Jun 6 '14 at 23:19