# Infinite Series: Fibonacci/ $2^n$

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?

-
My favorite ways of solving Fibonacci(-like) stuff are (i) using generating functions, and (ii) using the matrix/eigenvalues/eigenvectors approach. Would either of those work for your 15-18 year olds? – TMM Feb 29 '12 at 13:09
BTW this question provides a more general identity: math.stackexchange.com/questions/88529/… – Martin Sleziak Feb 29 '12 at 13:15

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.

-
Caveat: This only works if you know the series converges. – Thomas Andrews Feb 29 '12 at 13:16
@TMM I've made some edits, I think it is correct now. – Ragib Zaman Feb 29 '12 at 13:19
This is exactly what I have in mind. – Beni Bogosel Feb 29 '12 at 13:19
@ThomasAndrews I have addressed the issue of convergence, see my above edit. – Ragib Zaman Feb 29 '12 at 13:34

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.

-
For convergence it suffices to show, that $\frac{1}{2}$ is smaller than the minimum modulus of the solutions of $1-z-z^2 = 0$, that is the poles of $F$. Now $$\min_{1-z-z^2 = 0} |z| = \frac{\sqrt{5} - 1}{2} > \frac{1}{2}.$$ – Alexander Thumm Feb 29 '12 at 13:31
Sure, which is why I wrote "easy (or hard)" - it requires a certain kind of knowledge for it to be "easy." :) @AlexanderThumm – Thomas Andrews Feb 29 '12 at 13:49
I just wanted to add it for completeness. @ThomasAndrews – Alexander Thumm Feb 29 '12 at 14:11
I wish I could have picked this answer- really neat, and a straight generalisation of the other, but the odds of my students pulling a generating function out of the bag aren't high... – Tom Boardman Mar 1 '12 at 8:19

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$$

-

Let $f_n$ be the $n$th Fibonacci number, then we want to compute $$\sum_{n = 1}^{\infty} \frac {f_n} {2^n}.$$

Let $$S = \sum_{n = 1}^{\infty} \alpha_n$$ where $\alpha_n = f_n/2^n$. Since $f_n + f_{n + 1} = f_{n + 2}$, we have $\alpha_n + 2 \alpha_{n + 1} = 4 \alpha_{n + 2}$. Summing the last equality gives $$\sum_{n = 1}^{\infty} \alpha_n + 2 \sum_{n = 2}^{\infty} \alpha_n = 4 \sum_{n = 3}^{\infty} \alpha_n.$$ Hence, $S + 2 (S - \alpha_1) = 4 (S - \alpha_1 - \alpha_2)$. Since, $\alpha_1 = 1/2$ and $\alpha_2 = 1/4$, we have $3S - 1 = 4S - 3$, hence $S = 2$.

-