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

Question

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.

Answer 1

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!

Answer 2

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?

Answer 3

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 ?