Power series of $1/(1-x-x^2)$

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.