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

From ProofWiki
Jump to navigation Jump to search


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$