Infinite Series: Fibonacci/ $2^n$

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.

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.

This is how I solve it:

---

let $S$ equal the sequence of fractions:

$$S=\frac12+\frac14+\frac28+\frac3{16}+\frac5{32}+\frac8{64}+\cdots$$

Divide by $2$ and get:

$$\frac{S}2=\frac14+\frac18+\frac2{16}+\frac3{32}+\frac5{64}+\cdots$$

Subtract the first from the second to get:

$$S-\frac{S}2 = \frac12 + \frac04 + \frac18 + \frac1{16} + \frac2{32} + \frac3{64} + \cdots$$

Simplify:

$$\frac{S}2=\frac12+\frac18+\frac1{16}+\frac2{32}+\frac3{64}+\cdots$$

Multiply both sides by two:

$$S=1+\frac14+\frac18+\frac2{16}+\frac3{32}+\cdots$$

$$2S=2+\frac12+\frac14+\frac28+\frac3{16}+\cdots$$

Recognize $S$ from above:

$$2S=2+S$$

Subtract $S$ from both sides:

$$S=2$$