Let $(F_n)_{n\in{N^*}}$ be the Fibonacci sequence defined by $F_1=1$, $F_2=1$, $F_{n+1}=F_n+F_{n-1}$ for every $n\geq{2}$. Find the limit: \[ \lim_{n \to \infty}(\sum_{i=1}^n{\frac{F_i}{2^i}}) \]
Problem
Source: Moldovan MO 2003
Tags: limit, function, calculus, calculus computations
21.02.2006 15:26
Write $F_n$ in the canonical form :$F_n=a x^n+by^n$ for some $a,b,x,y$. The limit becomes: $\lim a \sum \left(\frac{y}{2}\right)^n+b\left(\frac{x}{2}\right)^n= a\frac{1}{1-\frac{x}{2}} + b\frac{1}{1-\frac y 2}$. First prove that $x,y<2$.
21.02.2006 16:49
Using generating function we have $\sum_{i=1}^{\infty} F_n x^n = \frac{x}{1-x-x^2}$. for $-\frac{\sqrt{5}+1}{2} < x < \frac{\sqrt{5}-1}{2}$.
21.02.2006 17:11
what is the generating function?
21.02.2006 17:27
It some kind of method to find the closed formula of reccurence relation. Using power series $\sum_{k=1}^{\infty} a_kx^k$. Where $a_k$ is the sequence of reccurence.
22.02.2006 09:53
i solved it using the general form of fibonacci like xirti said( forgive me if i mispelled your name)...
23.02.2006 11:56
Letting $S=\sum_{i=1}^n\frac{F_i}{2^i}$.....(i) then $\frac{1}{2}S=\sum^{i=1}^n\frac{F_i}{2^{i+1}}$....(ii) (i) - (ii) : $\frac{1}{2}S=\frac{F_1}{2}+(\frac{1}{4}\sum^{n-2}_{i=1}\frac{F_i}{2^i})-\frac{F_n}{2^{n+1}}\\=\frac{1}{2}+\frac{1}{4}(S-\frac{F_{n-1}}{2^{n-1}}-\frac{F_n}{2^n})-\frac{F_n}{2^{n+1}}\\=\frac{1}{2}+\frac{1}{4}S-\frac{F_{n-1}}{2^{n+1}}-\frac{3F_n}{2^{n+2}}\\=\frac{1}{2}+\frac{1}{4}S-\frac{F_{n+3}}{2^{n+2}}\longleftrightarrow \\\frac{1}{4}S=\frac{1}{2}-\frac{F_{n+3}}{2^{n+2}}$ And the rest is to prove $\frac{F_{n+3}}{2^{n+2}}\rightarrow 0$ as $n\rightarrow \infty$