Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 4 down vote accepted

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!

share|improve this answer
    
$@$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).

share|improve this answer
    
Thank you @JavaMan! –  Jozef Feb 6 '12 at 18:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.