Sum of nth Fibonacci Number over nth Power of 2/Proof 4

Theorem

$\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n} = 2$

where $F_n$ is the $n$th Fibonacci number.

Proof

First, let:

$S = \ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n}$

Some sundry results:

\(\ds \sum_{k \mathop = 0}^n F_k\)

\(=\)

\(\ds F_{n + 2} - 1\)

Sum of Sequence of Fibonacci Numbers

\(\text {(1)}: \quad\)

\(\ds \leadsto \ \ \)

\(\ds F_{n + 2}\)

\(=\)

\(\ds \paren {\sum_{k \mathop = 0}^n F_k} + 1\)

and:

\(\ds \sum_{n \mathop = 0}^\infty \frac 1 {2^n}\)

\(=\)

\(\ds \frac 1 {1 - \frac 1 2}\)

Sum of Infinite Geometric Sequence

\(\ds \)

\(=\)

\(\ds \frac 1 {1 / 2}\)

\(\text {(2)}: \quad\)

\(\ds \)

\(=\)

\(\ds 2\)

We have:

\(\ds S\)

\(=\)

\(\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n}\)

\(\ds \)

\(=\)

\(\ds \frac {F_0} {2^0} + \frac {F_1} {2^1} + \sum_{n \mathop = 2}^\infty \frac {F_n} {2^n}\)

\(\ds \)

\(=\)

\(\ds \frac 0 1 + \frac 1 2 + \sum_{n \mathop = 2}^\infty \frac {F_n} {2^n}\)

Definition of Fibonacci Numbers: $F_0 = 0$ and $F_1 = 1$

\(\ds \)

\(=\)

\(\ds \frac 1 2 + \sum_{n \mathop = 2}^\infty \frac {F_n} {2^n}\)

\(\ds \)

\(=\)

\(\ds \frac 1 2 + \sum_{n \mathop = 0}^\infty \frac{F_{n + 2} } {2^{n + 2} }\)

Translation of Index Variable of Summation

\(\ds \)

\(=\)

\(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \frac {F_{n + 2} } {2^n} }\)

as $2^{n + 2} = 2^2 \times 2^n = 4 \times 2^n$

\(\ds \)

\(=\)

\(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \frac 1 {2^n} \paren {\paren {\sum_{k \mathop = 0}^n F_k} + 1} }\)

from $(1)$

\(\ds \)

\(=\)

\(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} } + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \frac 1 {2^n} }\)

\(\ds \)

\(=\)

\(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} } + \frac 2 4\)

from $(2)$

\(\text {(3)}: \quad\)

\(\ds \)

\(=\)

\(\ds 1 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} }\)

We have:

\(\ds 1 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} }\)

\(=\)

\(\ds S\)

\(\ds \leadsto \ \ \)

\(\ds \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac{F_k} {2^n} }\)

\(<\)

\(\ds S\)

Hence we can show that $S$ is absolutely convergent by the Ratio Test:

For $S$ we get $a_n = \dfrac {F_n} {2^n}$ therefore

\(\ds \lim_{n \mathop \to \infty} \size {\frac {a_{n + 1} } {a_n } }\)

\(=\)

\(\ds \lim_{n \mathop \to \infty} \size {\frac {\frac {F_{n + 1 } } {2^{n + 1 } } } {\frac {F_n } {2^n } } }\)

substituting $a_n$ and $a_{n + 1}$ from above

\(\ds \)

\(=\)

\(\ds \lim_{n \mathop \to \infty} \size {\frac {2^n F_{n + 1 } } {2^{n + 1 } F_n} }\)

reformatting division of fractions

\(\ds \)

\(=\)

\(\ds \lim_{n \mathop \to \infty} \size {\frac {F_{n + 1} } {2F_n} }\)

cancelling $2^n$ from top and bottom

\(\ds \)

\(=\)

\(\ds \lim_{n \rightarrow \infty} \size {\frac {F_n + F_{n - 1} } {F_n + F_n} }\)

Definition of Fibonacci Numbers: $F_{n + 1} = F_n + F_{n - 1}$ and $2F_n = F_n + F_n$

\(\ds \)

\(<\)

\(\ds 1\)

$F_n > F_{n - 1}$ so $F_n + F_n > F_n + F_{n - 1}$

Therefore the double summation is absolutely convergent and we can exchange the order of the sums.

We note that:

$0 \le k \le n < \infty$

Therefore by Fubini's Theorem for Infinite Sums:

$\ds \sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} = \sum_{k \mathop = 0}^\infty \sum_{n \mathop = k}^\infty \frac{F_k} {2^n}$

and it follows that:

\(\ds S\)

\(=\)

\(\ds 1 + \frac 1 4 \paren {\sum_{k \mathop = 0}^\infty \sum_{n \mathop = k}^\infty \frac {F_k} {2^n} }\)

continuing from $(3)$

\(\ds \)

\(=\)

\(\ds 1 + \frac 1 4 \paren {\sum_{k \mathop = 0}^\infty \paren {F_k \sum_{n \mathop = 0}^\infty \paren {\frac 1 {2^k} } \frac 1 {2^n} } }\)

reindexing the sum

\(\ds \)

\(=\)

\(\ds 1 + \frac 1 4 \paren {\sum_{k \mathop = 0}^\infty \paren {\frac 1 {2^k} F_k \sum_{n \mathop = 0}^\infty \paren {\frac 1 {2^n} } } }\)

\(\ds \)

\(=\)

\(\ds 1 + \frac 1 4 \paren {2 \sum_{k \mathop = 0}^\infty \frac {F_k} {2^k} }\)

from $(2)$

\(\ds \)

\(=\)

\(\ds 1 + \frac S 2\)

as $S = \ds \sum_{k \mathop = 0}^\infty \frac {F_k} {2^k}$ by hypothesis

\(\ds \leadsto \ \ \)

\(\ds \dfrac S 2\)

\(=\)

\(\ds 1\)

\(\ds \leadsto \ \ \)

\(\ds S\)

\(=\)

\(\ds 2\)

Hence the result.

$\blacksquare$