Prove that the $c_{n}$ in $\frac{1}{1-z-z^{2}}=\displaystyle\sum_{n=0}^{\infty}c_{n}z^{z}$ satisfy a Fibonacci-like recurrence relation I need to prove that the coefficients $c_{n}$ of the expansion $\frac{1}{1-z-z^{2}}\sum_{n=0}^{\infty}c_{n}z^{n}$ satisfy the recurrence relation $c_{0}=c_{1}=1$, $c_{n}=c_{n-1}+c_{n-2}$, by multiplying $(1-z-z^{2})\sum_{n=0}^{\infty}c_{n}z^{n}$.
I'll admit that the coefficients look rather Fibonacci-like, but I'm not very experienced with recurrence relations, and I'm not entirely sure what this problem is asking me to do. 
Am I supposed to just multiply the series $\sum_{n=0}^{\infty}c_{n}z^{n}$ through by $1$, $-z$, and $-z^{2}$, respectively, add them up, and set them equal to $\sum_{n=0}^{\infty}c_{n}z^{n}$?
Then after that, what? It looks like I'm going to have to solve a rather daunting system of equations...
Is there a better way to do this, or is this it? If this is not how I'm supposed to approach this problem, how should I instead do so? Hints, suggestions, even full-answers welcome. I'm incredibly confused.
 A: Note upon multiplying $1-z-z^2$ with the series $\sum_{n=0}^\infty c_nz^n$ and setting the result equal to $1$ we obtain
$$\begin{align}
1&=\sum_{n=0}^\infty c_n(z^n+z^{n+1}-z^{n+2})\\\\
&=\sum_{n=0}^\infty c_nz^n-\sum_{n=0}^\infty c_nz^{n+1}-\sum_{n=0}^\infty c_nz^{n+2}\\\\
&=\sum_{n=0}^\infty c_nz^n-\sum_{n=1}^\infty c_{n-1}z^n-\sum_{n=2}^\infty c_{n-2}z^n\\\\
&=c_0+(c_1-c_0)z+\sum_{n=2}^\infty(c_n-c_{n-1}-c_{n-2})z^n
\end{align}$$
Therefore, we find $c_0=1$, $c_1=c_0$, and $c_n=c_{n-1}+c_{n-2}$ for $n\ge 2$ as was to be shown!
A: Well, you  know that
$$
\begin{split}
1 &= (1-z-z^2)\sum_{k=0}^\infty c_k z^k \\
  &= \sum_{k=0}^\infty c_k z^k 
   - \sum_{k=0}^\infty c_k z^{k+1}
   - \sum_{k=0}^\infty c_k z^{k+2} \\
  &= \sum_{k=0}^\infty c_k z^k 
   - \sum_{k=1}^\infty c_{k-1} z^k
   - \sum_{k=2}^\infty c_{k-2} z^k \\
  &= c_0 + c_1 z + \sum_{k=2}^\infty c_k z^k 
   - c_0 z - \sum_{k=2}^\infty c_{k-1} z^k
   - \sum_{k=2}^\infty c_{k-2} z^k \\
  &= c_0 + z(c_1 - c_0)
   + \sum_{k=2}^\infty \left[c_k - c_{k-1} - c_{k-2}\right] z^k
\end{split}
$$
Since that sum is a power series, the only way it can be 1 for all values of $z$ is if $c_0=1$, $c_0-c_1=0$ and $c_k-c_{k-1}-c_{k-2}=0$ for all $k$. Can you take it from here?
A: Let's start with a finite number of terms.
$$(1-z-z^2)(c_0+c_1z+c_2z^2+c_3z^3+c_4z^4)\\
=c_0+c_1z+c_2z^2+c_3z^3+c_4z^4\\
-c_0z-c_1z^2-c_2z^3-c_3z^4-c_4z^5\\
-c_0z^2-c_1z^3-c_2z^4-c_3z^5-c_4z^6.$$
Then regrouping by equal powers,
$$=c_0+(c_1-c_0)z+(c_2-c_1-c_0)z^2+(c_3-c_2-c_1)z^3+(c_4-c_3-c_2)z^4\\
-c_4z^5-c_3z^5-c_4z^6.$$
Now, what happens when you replace the constants by their values ? And what happens when you add more terms ? Can you generalize ?
