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$