2
$\begingroup$

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!

  • 0
    The question is essentially about the generating function of the recurrence, if I understand things right!2012-02-06
  • 0
    The "author" didn't direct to generating functions for sure :), but I'll look it up in this way.2012-02-06
  • 0
    @JavaMan: that sounds like an answer...2012-02-06
  • 0
    @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!2012-02-06

2 Answers 2

5

As for the question about radius of convergence, I'll write the comments by Javaman:

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!

  • 0
    $@$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?2012-02-06
  • 0
    @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?2012-02-06
  • 0
    I am editing the answer @Jozef. A little care is necessary. I was too loose!2012-02-06
  • 0
    @Jozef Does this look fine to you?2012-02-06
  • 0
    In the convergence ratio yes :)2012-02-06
  • 0
    The rest is not still fine then? @Jozef2012-02-06
  • 0
    It is! Thanks a lot! :)2012-02-06
1

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).