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

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, 2012 at 13:09
• BTW this question provides a more general identity: math.stackexchange.com/questions/88529/… Feb 29, 2012 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. Feb 29, 2012 at 13:16
• @TMM I've made some edits, I think it is correct now. Feb 29, 2012 at 13:19
• This is exactly what I have in mind. Feb 29, 2012 at 13:19
• @ThomasAndrews I have addressed the issue of convergence, see my above edit. Feb 29, 2012 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}.$$ Feb 29, 2012 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 Feb 29, 2012 at 13:49
• I just wanted to add it for completeness. @ThomasAndrews Feb 29, 2012 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... Mar 1, 2012 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$$