# Main Page

# Welcome to $\mathsf{Pr} \infty \mathsf{fWiki}$

If you have any questions, comments, or suggestions please post on the To see what's currently happening in the community, visit the |

**—**25,580 Definitions

**—**Help

# Featured Proof

## 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$