# ${a_n}$ series of Fibonacci numbers. $f(x)=\sum_{0}^{\infty}a_nx^n$, show that in the convergence radius: $f(x)= \frac{1}{1-x-x^2}$

I'd really like your help with this following problem: Let ${a_n}$ be a Fibonacci series $a_1=a_0=1$ and $a_{n+2}=a_n+a_{n+1}$ for every $n \geq 0$.

Let $f(x)=\sum_{0}^{\infty}a_nx^n$, I need to find the radius of convergence and to prove that in the range of this radius $f(x)= \frac{1}{1-x-x^2}$.

we know that the convergence radius $R=\lim_{n\to \infty} |\frac {a_n}{a_{n+1}}|$, How can I apply it in this case? Any direction to prove that $f(x)$ is as requested?

Thanks alot!

-
The question is essentially about the generating function of the recurrence, if I understand things right! –  user21436 Feb 6 '12 at 17:05
The "author" didn't direct to generating functions for sure :), but I'll look it up in this way. –  Jozef Feb 6 '12 at 17:07
@JavaMan: that sounds like an answer... –  Pete L. Clark Feb 6 '12 at 17:14
@PeteL.Clark I have written answer, which I will like if you go through it to leave comments about the rigour. Please consider this request of mine! –  user21436 Feb 6 '12 at 17:17

As $\dfrac{a_{n+1}}{a_n} \to \phi$, where $\phi=\dfrac{1+\sqrt 5}{2}$, we see that the limit superior coincides with the limit.

$$\limsup \dfrac{a_{n+1}}{a_n}=\lim \dfrac{a_{n+1}}{a_n}=\phi$$ which gives you the radius of convergence.

Loosely, this is how generating functions work:

Note that we have, $a_n=a_{n-1}+a_{n-2},~~ n\ge2$

\begin{align*} f(x) & = \sum _{n=0}^ \infty {a_n x^n} \&=1+a_1x+\sum_{n=2}^\infty(a_{n-1}+a_{n-2})x^n\\&=1+a_1x+\sum_{n=2}^\infty{a_{n-1}x^n+\sum_{n=2}^\infty}a_{n-2}x^n\\&=1+a_1x+x\sum_{n-1=1}^\infty{a_{n-1}x^{n-1}}+x^2\sum_{n-2=0}^\infty{a_{n-2}x^{n-2}}\\&=1+x+x(f(x)-1)+x^2f(x) ~~~\text{as a_1=1}\\&=1+xf(x)+x^2f(x)\end{align*}

But, as for rigour, I am looking forward to enlightening comments!

-
$@$Kannappan: this is certainly a valid derivation of the closed form of the generating function. (And this does not need any convergence considerations whatsoever.) But the OP also asked explicitly for the radius of convergence, right? –  Pete L. Clark Feb 6 '12 at 17:22
@Kannappan Sampath: Thank you. We get that $f(x)=xf(x)+x^2f(x)$, I didn't understand how do we get $f(x)$ as requested, or: why does this equal 1? –  Jozef Feb 6 '12 at 17:27
I am editing the answer @Jozef. A little care is necessary. I was too loose! –  user21436 Feb 6 '12 at 17:36
@Jozef Does this look fine to you? –  user21436 Feb 6 '12 at 17:45
In the convergence ratio yes :) –  Jozef Feb 6 '12 at 18:08

You can find the radius of convergence by noting the well-known identity:

$$\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = \varphi,$$ where $\varphi = \frac{\sqrt{5}+1}{2}$ is the golden ratio.

Once you know the radius of convergence, to find the partial sum $S_N$, just write:

\begin{align} S_N := \sum_{n=0}^N a_n x^n &= 1 +x + \sum_{n =2}^N a_n x^n \\ &= 1+x + \sum_{n=2}^N(a_{n-2} + a_{n-1})x^n \\ &= 1+ x + x^2\sum_{n=2}^N a_{n-2}x^{n-2} + x\sum_{n=2}^Na_{n-1} x^{n-1} \\ &= 1 + x + x^2 \sum_{n=0}^{N-2} a_n x^n + x \cdot \sum_{n=1}^{N-1} a_n x^n \\ &= 1 + x + x^2 S_{N-2} + x\sum_{n=0}^{N-1} a_n x^n - x \\ &= 1 + x^2 S_{N-2} + x S_{N-1}. \end{align} Since $S_N = a_Nx^N + S_{N-1} = a_Nx^N + a_{N-1}x^{N-1} + S_{N-2}$, we arrive at $$S_N = 1 + x^2 (S_N - a_N x^N - a_{N-1}x^{N-1}) + x(S_N - a_Nx^N)$$ Solving for $S_N$ gives $$S_N = \frac{1 - a_Nx^{N+2} - a_{N-1}x^{N+1} - a_Nx^{N+1}}{1 - x - x^2}.$$ Finally, taking the limit $\lim_{N \to \infty} S_N$ gives the answer as the terms with powers of $x$ in the numerator go to zero (since the original sum under question converges).

-
Thank you @JavaMan! –  Jozef Feb 6 '12 at 18:44