# Sum of nth Fibonacci Number over nth Power of 2/Proof 1

## Theorem

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

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

## Proof

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$