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

127 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

The generating function of the Fibonacci numbers is as follows. \begin{align} \sum_{n=0}^{\infty} F_{n} t^{n} &= \sum_{n=0}^{\infty} \sum_{k=0}^{[(n-1)/2]} \binom{n-k-1}{k} \ t^{n} \\ &= \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \binom{n+k}{k} \ t^{n+2k+1} \\ &= \sum_{n=0}^{\infty} (1-t^{2})^{-n-1} \ t^{n+1} \\ &= \frac{t}{1-t^{2}} \ \sum_{n=0}^{\infty} \left( \frac{t}{1-t^{2}} \right)^{n} \\ &= \frac{t}{1-t-t^{2}}. \end{align}