The generating function of the Fibonacci sequence as a rational function

Question

Prove that if $$f(x)=\sum _1 ^{\infty} a_n \cdot x^n,$$ where $(a_n)$ is the Fibonacci Sequence, and if $|x|<1/2$, then $$(x^2 + x - 1) \cdot f(x) = -x.$$

So far, as an earlier part of this question, I've shown that $a_{k+1}/a_k \le 2$ and that $f(x)$ converges for all $|x|<1/2$.

Although I'm aware that this $f$ converges, I have no method for finding what it converges to!

This question implies that $f(x) = -x/(x^2 +x -1)$ which, for $-1/2 < x < 1/2$ is inside $(-4/10,2)$. I've also tried factoring the $(x^2 + x -1)$ into my series for $f$, but just don't know where to go from here.

Answer 1

Since the series converges, we are allowed to write $$(x^2+x-1)f(x)=\sum_{n=1} a_n x^{n+2}+\sum_{n=1}a_n x^{n+1}-\sum_{n=1} a_n x^n$$ Now for the last series $$\sum_{n=1} a_n x^n=a_1 x+a_2 x^2+\sum_{n=3}a_n x^n=a_1 x+a_2 x^2+\sum_{n=3}(a_{n-2}+a_{n-1})x^n$$ so putting all together you get $$(x^2+x-1)f(x)=a_1 x^2-a_1 x-a_2 x^2$$ Assuming you are defining the Fibonacci numbers starting with $a_1=a_2=1$, you have the result.

Answer 2

Hint: $a_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$ where $\psi = \frac{1}{2}(1-\sqrt{5})$ and $\phi = \frac{1}{2}(1+\sqrt{5})$ (the golden ratio).

Answer 3

(I'm leaving out the details on the ranges for $n$, leaving that for you to do)

Hint: $$x^2 f(x) = x^2 \sum{a_n}{x^n}$$ $$= \sum{a_n}{x^{n+2}}$$ $$= \sum{a_{n-2}}{x^{n}} + (some\space constant\space and\space x\space term) $$ where the last equality comes from "shifting the index" in the summation, replacing $n+2$ with $m$, and then $m$ with $n$.

Do something similar with $xf(x)$ and $-1f(x)$, and you should be able to combine the three summations into one and use a version of the recursion formula for the Fibonacci numbers that involves $a_{n}$, $a_{n-1}$, and $a_{n-2}$.