Main Page

From ProofWiki
Jump to navigation Jump to search

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

Logo.png

$\mathsf{Pr} \infty \mathsf{fWiki}$ is an online compendium of mathematical proofs! Our goal is the collection, collaboration and classification of mathematical proofs. If you are interested in helping create an online resource for math proofs feel free to register for an account. Thanks and enjoy!

If you have any questions, comments, or suggestions please post on the discussion page, or contact one of the administrators. Also, feel free to take a look at the frequently asked questions because you may not be the first with your idea.

To see what's currently happening in the community, visit the community portal.

26,829 Proofs 25,580 Definitions Help

Featured Proof

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$