Show that $\lim_{n\rightarrow\infty}{\sum_{i=1}^{n}{\frac{F_n}{2^n}}}=2$

Question

I need help to show that $\lim_{n\rightarrow\infty}{\displaystyle\sum_{i=1}^{n}{\frac{F_n}{2^n}}}=2$, where $F_n$ is the n-th number in the Fibonacci sequence.

I know how to prove this by putting that $A_n={\displaystyle\sum_{i=1}^{n}{\frac{F_n}{2^n}}}$ and than finding a closed form for $A_n$ (I can't remember how the closed form looks like bcs I did this problem 2 years ago). Now that I started to learn limits at school I wanted to know if it is possible to solve this problem in another way using some tricks with limits or something similar.

Answer 1

The series is convergent by the ratio test. Given: $$ S = \sum_{n=1}^{+\infty}\frac{F_n}{2^n}$$ we have: $$ S = \frac{1}{2}+\sum_{n=1}^{+\infty}\frac{F_{n+1}}{2^{n+1}}=\frac{1}{2}+\frac{S}{2}+\sum_{n=1}^{+\infty}\frac{F_{n-1}}{2^{n+1}}=\frac{1+S}{2}+\sum_{n=1}^{+\infty}\frac{F_n}{2^{n+2}}=\frac{1+S}{2}+\frac{S}{4}$$ from which $S=2$ follows.

Answer 2

Here's a way that actually uses the Fibonacci relation as a step of the proof.

Define

$S = \displaystyle\sum_{n=1}^\infty \frac{F_n}{2^n}$

Then let's take advantage of the Fibonacci properties by adding $F_n$ and $F_{n-1}$. To set that up:

$\frac{S}{2} = \displaystyle\sum_{n=1}^\infty \frac{F_n}{2^{n+1}} = \sum_{n=2}^\infty \frac{F_{n-1}}{2^n}$

So

$S+\frac{S}{2} = \displaystyle\frac{F_1}{2} + \sum_{n=2}^\infty \frac{F_n + F_{n-1}}{2^n} = \frac{F_1}{2} + \sum_{n=2}^\infty \frac{F_{n+1}}{2^n} = \frac{F_1}{2}+2 \sum_{n=2}^\infty \frac{F_{n+1}}{2^{n+1}} = \frac{F_1}{2} + 2\sum_{n=3}^\infty \frac{F_n}{2^n}$

Note $F_1/2 + 2F_2/2^2 = 1$. Adding this to both sides gives

$\displaystyle\frac{3S}{2} + 1 = 2 \frac{F_1}{2} + 2 \frac{F_2}{2^2} + 2\sum_{n=3}^\infty \frac{F_n}{2^n} = 2 \sum_{n=1}^\infty \frac{F_n}{2^n} = 2S$

Solving $\frac{3S}{2} + 1 = 2S$ gives S=2.

(an alternate already suggested by others is to notice that $\sum F_n x^n$ is the "generating function" of the Fibonacci numbers. This function is known (or easily calculated). Then just set $x=1/2$)

Answer 3

I will show how I managed to solve it not using limits. Let define $A_n=\displaystyle\sum_{i=1}^n{\frac{F_n}{2^n}}$; $A_1=\frac{1}{2},A_2=\frac{3}{4},A_3=1$

With that we now have

$A_{n+1}-A_n=\frac{F_{n+1}}{2^{n+1}} \Rightarrow F_{n+1}=2^{n+1}(A_{n+1}-A_n)$

$A_n-A_{n-1}=\frac{F_n}{2^n} \Rightarrow F_n=2^n(A_n-A_{n-1})$

$A_{n-1}-A_{n-2}=\frac{F_{n-1}}{2^{n-1}} \Rightarrow F_{n-1}=2^{n-1}(A_{n-1}-A{n-2})$

Now using that $F_{n+1}=F_n+F_{n-1}$ we will get $4\cdot A_{n+1}-6\cdot A_{n}+A_{n-1}+A{n-1}=0$, and from that we will have $4A_{n+1}-2A_n-A_{n-1}=4A_n-2A_{n-1}-A_{n-2}$ andfrom that we get that $4A_{n+1}-2A_n-A_{n-1}$ has a constant value which we can calculate putting n=2. $4A_3-2A_2-A_1=2$, so we have that $4A_{n+1}=2A_n+A_{n-1}+2$. Putting $A_n=B_n+2$, where $B_n$ is a sequence so that $4B_{n+1}=2B_{n}+B_{n-1}$. Giving the starting values we can calculate that $B_1=-\frac{3}{2},B_2=-\frac{5}{4},B_3=-1$, and so we can get that every $B_i$ is a negative number, and besides that it gets always closer to $0$. So we have that $A_n<2$ for all n and bcs $B_n$ gets always closer to $0$ we have that $\lim_{n\rightarrow\infty}{A_n}=2$.