Power series of $1/(1-x-x^2)$ I have a difficulty in finding the power series of: $$\frac{1}{1-x-x^2}$$ At first I did a polynomial division and I found out that: $$\frac{1}{1-x-x^2}=1+x+2x+3x^2+5x^3+8x^4+13x^5+...$$ where the coefficients of this Taylor Series are the numbers of the Fibonacci Sequence.
However, this is not a proof, so when I tried to prove it, I reached the following point:$$\frac{1}{1-x-x^2}=\sum_{n=0}^{\infty}(x+x^2)^n=\sum_{n=0}^{\infty}x^n(1+x)^n\\ =\sum_{n=0}^{\infty}x^n\sum_{k=0}^{n}\binom{n}{k}x^{n-k}=\sum_{n=0}^{\infty}\sum_{k=0}^{n}\binom{n}{k}x^{2n-k}$$
How can I proceed from this point, or I have to take another path?
 A: It is possible to continue from your approach. Let's fix a natural number $N$ and compute its coefficient. Given $n$, the inner sum can only contribute terms with powers $n, n+1, \ldots, 2n$. So to compute the coefficient of $x^{N}$, we should consider those terms with $n = N/2, N/2 + 1, \ldots N$. It now makes a difference whether $N$ is even or odd - let's assume it's even for simplicity.
The coefficient of $x^{N}$ is
$$\binom{N/2}{0} + \binom{N/2+1}{2} + \ldots + \binom{N}{N} = \sum_{i=0}^{N/2} \binom{N/2+i}{2i}$$
A similar argument for $N$ odd gives
$$\binom{(N+1)/2}{1} + \binom{(N+3)/2}{3} + \ldots \binom{N}{N}$$
Let's call these sums $S_{N}$. Sorry for the overloaded notation - assuming again that $N$ is even, so $N+1$ is odd, We can write $S_{N}+S_{N+1}$ as:
\begin{align*}
\binom{N/2}{0} + \binom{N/2+1}{2} + \ldots + \binom{N}{N} + \\
\binom{N/2 + 1}{1} + \binom{N/2+2}{3} + \ldots + \binom{N + 1}{N} \\
= \binom{N/2}{0} + \binom{N/2+2}{2} + \binom{N/2+3}{4} + \ldots \binom{N+1}{N+1}
\end{align*}
(applying Pascal's identity), and luckily $\binom{N/2}{0} = 1 = \binom{N/2 + 1}{0}$, so this final sum is indeed $S_{N+2}$. It remains to check the case $N$ odd, and that $S_{0} = S_{1} = 1$, but those checks are easy.
There is a more compelling approach: Assume we can write $\frac{1}{1-x-x^2} = \sum_{n=0}^{\infty} a_{n} x^{n}$.
Then, multiplying by $1-x-x^2$,
\begin{align*}
1 &= \sum_{n=0}^{\infty} a_{n} (1-x-x^2)x^{n}\\
&= a_{0} + a_{1} x - a_{0}x + \sum_{n=2}^{\infty} (a_{n} - a_{n-1} - a_{n-2}) x^n \\
\end{align*}
and we deduce, by equating coefficients, that
\begin{align*}
a_0 &= 1 \\
a_1 &= a_0 \\
a_n &= a_{n-1} + a_{n-2} \,\,\text{for $n \ge 2$}
\end{align*}
and hence, that $(a_n)$ are the Fibonacci numbers.
