# Sum of nth Fibonacci Number over nth Power of 2

## Theorem

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

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

## Proof 1

Let us define a sample space which satisfies the Kolmogorov Axioms such that it is the set of all combinations of flipping a fair coin until you receive two heads in a row.

Let $X_n$ be the event of some outcome from flipping $n$ fair coins in a row, then $\Pr(X_n) = \dfrac 1 {2^n}$.

In the sample space defined above, we now demonstrate that for a given number of flips $n$, there are exactly $F_{n - 1}$ outcomes contained in the sample space.

### Illustration

$\begin{array}{c|c|cc} n & \map f n & \text {Sample Space}: \Omega \\ \hline 1 & 0 & \text {impossible} \\ 2 & 1 & HH \\ 3 & 1 & THH \\ 4 & 2 & (HTHH), (TTHH) \\ 5 & 3 & (THTHH), (HTTHH), (TTTHH) \\ 6 & 5 & (HTHTHH), (TTHTHH), (THTTHH), (HTTTHH), (TTTTHH) \\ \hline \cdots & \cdots & \cdots \\ \hline n & F_{n - 1} & \cdots \\ \hline \end{array}$

Reviewing the illustration above, for any given value of $n$:

For ALL combinations displayed in row $n$ (that is $\map f n$) , we can place a $T$ in front and that new combination would exist in the sample space for $\paren {n + 1}$.

For example:

$\paren {HTHH}, \paren {TTHH} \to \paren {THTHH}, \paren {TTTHH}$

However, we also see that for only those combinations starting with a $T$ (that is $\map f {n - 1}$), can we place an $H$ in front and that new combination will also exist in the sample space for $\paren {n + 1}$.

For example:

$\paren {TTHH} \to \paren {HTTHH}$

Therefore, we have:

 $\ds \map f n$ $=$ $\ds F_{n - 1}$ $\ds \map f {n + 1}$ $=$ $\ds \map f n + \map f {n - 1}$ $\map f n$ is adding a $T$ in front and $\map f {n - 1}$ is adding an $H$ in front $\ds$ $=$ $\ds F_{n - 1} + F_{n - 2}$ $\ds$ $=$ $\ds F_n$

The sum of the probabilities of outcomes in a sample space is one by the second Kolmogorov Axiom.

 $(\text {II})$ $:$ $\ds \map \Pr \Omega$ $\ds =$ $\ds 1$

Hence:

 $\ds \sum_{n \mathop = 1}^\infty \frac {F_{n - 1} } {2^n}$ $=$ $\ds 1$ $2$nd Kolmogorov Axiom $\ds \leadsto \ \$ $\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^{n + 1} }$ $=$ $\ds 1$ reindexing the sum $\ds \leadsto \ \$ $\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n}$ $=$ $\ds 2$ multiplying both sides by $2$

$\blacksquare$

## Proof 2

From the Euler-Binet Formula, we have:

$F_n = \dfrac {\phi^n - \paren {1 - \phi}^n} {\sqrt 5}$

Therefore:

 $\ds \sum_{n \mathop = 0}^\infty \frac{F_n} {2^n}$ $=$ $\ds \sum_{n \mathop = 0}^\infty \dfrac {\phi^n - \paren {1 - \phi}^n} {\sqrt 5 \times 2^n}$ Euler-Binet Formula $\ds$ $=$ $\ds \sum_{n \mathop = 0}^\infty \dfrac {\paren {\dfrac {1 + \sqrt 5} 2}^n - \paren {1 - \paren {\dfrac {1 + \sqrt 5} 2 } }^n} {\sqrt 5 \times 2^n}$ Definition of Golden Mean $\ds$ $=$ $\ds \sum_{n \mathop = 0}^\infty \dfrac {\paren {\dfrac {1 + \sqrt 5} 2}^n - \paren {\dfrac {1 - \sqrt 5} 2 }^n} {\sqrt 5 \times 2^n}$ $\ds$ $=$ $\ds \dfrac 1 {\sqrt 5} \sum_{n \mathop = 0}^\infty \paren {\dfrac {1 + \sqrt 5} 4}^n - \dfrac 1 {\sqrt 5} \sum_{n \mathop = 0}^\infty \paren {\dfrac {1 - \sqrt 5} 4}^n$ Product of Powers and $2^2 = 4$ $\ds$ $=$ $\ds \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 + \sqrt 5 } 4} } - \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 - \sqrt 5} 4} }$ Sum of Infinite Geometric Sequence $\ds$ $=$ $\ds \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 + \sqrt 5} 4} } \times \dfrac 4 4 - \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 - \sqrt 5} 4} } \times \dfrac 4 4$ multiplying top and bottom by $4$ $\ds$ $=$ $\ds \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 - \sqrt 5} } - \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 + \sqrt 5} }$ $\ds$ $=$ $\ds \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 - \sqrt 5} } \times \paren {\dfrac {3 + \sqrt 5} {3 + \sqrt 5} } - \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 + \sqrt 5} } \times \paren {\dfrac {3 - \sqrt 5} {3 - \sqrt 5} }$ multiplying top and bottom by $\paren {3 + \sqrt 5}$ and by $\paren {3 - \sqrt 5}$ $\ds$ $=$ $\ds \dfrac 4 {\sqrt 5} \paren {\dfrac {3 + \sqrt 5} 4} - \dfrac 4 {\sqrt 5} \paren {\dfrac {3 - \sqrt 5} 4}$ $\ds$ $=$ $\ds \paren {\dfrac {3 + \sqrt 5} {\sqrt 5} } - \paren {\dfrac {3 - \sqrt 5} {\sqrt 5} }$ $\ds$ $=$ $\ds 2$

$\blacksquare$

## Proof 3

 $\ds \sum_{k \mathop = 0}^{\infty} F_k z^k$ $=$ $\ds \dfrac z {1 - z - z^2}$ Generating Function for Fibonacci Numbers $\ds \leadsto \ \$ $\ds \sum_{k \mathop = 0}^{\infty} \frac {F_k} {2^k}$ $=$ $\ds \dfrac {\dfrac 1 2} {1 - \dfrac 1 2 - \paren {\dfrac 1 2}^2}$ substituting $z = \dfrac 1 2$ $\ds$ $=$ $\ds \dfrac {1 / 2} {1 / 4}$ $\ds$ $=$ $\ds 2$

$\blacksquare$

## Proof 4

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$