what is the coefficient of $x^n$ in the expansion of the function $\frac{x}{1-x-x^2}$?

Question

But, just to get across the idea of a generating function, here is how a generatingfunctionologist might answer the question: the nth Fibonacci number, $F_{n}$, is the coefficient of $x^{n}$ in the expansion of the function $\frac{x}{(1 − x − x^2)}$ as a power series about the origin.

I am reading a book about generating function, however, I got a little rusted about power series. could anyone give me a quick review about what the statement above is saying?

namely,

$F_{n}$, is the coefficient of $x_{n}$ in the expansion of the function $\frac{x}{(1 − x − x^2)}$ as a power series about the origin

Answer 1

If you consider the power series $$f(x) = F_0 + F_1 x + F_2 x^2 + \cdots$$ then the relation $F_{n+2} = F_n + F_{n+1}$ implies $$x^2 f(x) + x f(x) - F_0 x = f(x) - F_0 - F_1 x.$$ (Write out each term as a power series, and combine terms.) Rearranging and plugging in $F_0=0$ and $F_1=1$ gives $$(1-x-x^2) f(x) = x.$$

---

More detail:

\begin{align} x^2 f(x) + x f(x) &= (F_0 x^2 + F_1 x^3 + F_2 x^4 + \cdots) + (F_0 x + F_1 x^2 + F_2 x^3 + \cdots) \\ &=F_0 x + (F_0+F_1)x^2 + (F_1+F_2)x^3 + (F_2+F_3)x^4+\cdots\\ &= F_0 x + F_2 x^2 + F_3 x^3 + F_4 x^4 + \cdots \\ &= F_0 x - F_0 - F_1 x + (F_0 + F_1x + F_2x^2 + F_3 x^3 + \cdots) \\ &= F_0 x - F_0 - F_1 x + f(x). \end{align}

Answer 2

$$(1-ax)^{-1}-(1-bx)^{-1}=\dfrac{x(a-b)}{1-(a+b)x+abx^2}$$

Now the $r$th term of $(1-ax)^{-1}$ is $$(ax)^r$$

So, the coefficient of $x^n$ will be $$a^n-b^n$$

Here $a+b=1, ab=-1$

Answer 3

Your comments on angryavian's answer suggest that it would be worth showing some more intermediate steps. Given $f(x) = F_0 + F_1 x + F_2 x^2 + F_3 x^3 + \ldots$ we have $$\begin{eqnarray} f(x) = & F_0 + & F_1 x + & F_2 x^2 + F_3 x^3 + F_4 x^4 + F_5 x^5 + \ldots \\ xf(x) = & & F_0 x + & F_1 x^2 + F_2 x^3 + F_3 x^4 + F_4 x^5 + \ldots \\ x^2f(x) = & & & F_0 x^2 + F_1 x^3 + F_2 x^4 + F_3 x^5 + \ldots \\ \end{eqnarray}$$

whence

$$f(x) - xf(x) - x^2f(x) = F_0 + (F_1 - F_0) x + (F_2 - F_1 - F_0) x^2 + (F_3 - F_2 - F_1) x^3 + \ldots$$

But since $F_{i+2} = F_{i+1} + F_i$ that simplifies to $$f(x) - xf(x) - x^2f(x) = F_0 + (F_1 - F_0) x$$ which is easily rearranged to $$f(x) = \frac{F_0 + (F_1-F_0)x}{1-x-x^2}$$