Infinite Series: Fibonacci/ $2^n$ [duplicate]

Solution 1:

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

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

$$ = \frac{3}{4} + \frac{1}{2} \sum_{n=3}^{\infty} \frac{ F_{n-1} }{2^{n-1} } + \frac{1}{4} \sum_{n=3}^{\infty} \frac{F_{n-2} }{2^{n-2} } $$

$$ = \frac{3}{4} + \frac{1}{2} \left( S - \frac{1}{2} \right) + \frac{1}{4} S.$$

Thus we have $ S = 2.$

To prove the series converges, we prove by induction that $ F_n \leq \phi^n$ where $ \phi = \frac{1+ \sqrt{5} }{2} \approx 1.618.$

The base cases are simple to check. Now assume there exists some integers $n-2$ and $n-1$ such that $ F_{n-2}\leq \phi^{n-2} $ and $ F_{n-1} \leq \phi^{n-1}.$ Then $$ F_n = F_{n-1}+ F_{n-2} \leq \phi^{n-1} + \phi ^{n-2} $$

$$= \phi^{n-2} ( \phi + 1) = \phi^{n-2} \phi^2 = \phi^n$$

which proves the claim. Note we used the fact that $\phi + 1 = \phi^2 $, the defining property of the golden ratio.

Solution 2:

Let $F(z)=\sum_{n=0}^\infty F_n z^n$. (Note, I'm adding the $F_0=0$ term, which does not affect the calculation.)

Then $$F(z) = z + \sum_{n=0}^\infty F_{n+2} z^{n+2}$$

Replacing $F_{n+2} = F_{n+1} + F_n$, you get:

$$F(z) = z + zF(z) + z^2F(z)$$

So $F(z) = \frac{z}{1-z-z^2}$. Now compute $F(\frac{1}{2})$.

Note that this only proves that, if the sum converges, it is equal to $\frac{z}{1-z-z^2}$. Showing that it converges is as easy (or hard) as showing that $\frac{1}{2}$ is in the radius of convergence.