Infinite Series: Fibonacci/ $2^n$

Question

I presented the following problem to some of my students recently (from Senior Mathematical Challenge- edited by Gardiner)

In the Fibonacci sequence $1, 1, 2, 3, 5, 8, 13, 21, 34, 55,\ldots$ each term after the first two is the sum of the two previous terms. What is the sum to infinity of the series:

$$\frac{1}{2} + \frac{1}{4}+ \frac{2}{8} + \frac{3}{16} + \frac{5}{32} +\frac{8}{64} + \frac{13}{128} +\frac{21}{256} +\frac{34}{512}+ \frac{55}{1024} + \cdots$$

Now, I solved this using an infinite geometric matrix series (incorporating the matrix version of the relation $a_n= \frac{a_{n-1}}{2}+ \frac{a_{n-2}}{4}$), and my students, after much hinting on my part, googled the necessary string to stumble across Binet's formula (which allows one to split the series into two simple, if rather messy, geometrics).

Both of these are good methods, but neither really seems plausible for a challenge set for 15-18 year olds under exam conditions. So how is one supposed to do it?

Answer 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.

Answer 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.