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$