https://proofwiki.org/wiki/Main_Page

Main Page

From ProofWiki
Jump to navigation Jump to search
[INS::INS]

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,727 Proofs -- 25,226 Definitions -- Help

Follow @ProofWiki

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 \ \     \(\ds F_{n -
      map f n (=    1}\)
           \) \)
      \(\ds \ \     \(\ds \map f    $\map f n$ is adding a $T$ in
     map f {n (=    n + \map f {n   front and $\map f {n - 1}$ is
       + 1}\) \)    - 1}\)          adding an $H$ in front
              \     \(\ds F_{n -
     \(\ds \) (=    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 \   \(\ds =  \(\ds 1 \)   
\)                                  Omega \)    \)        

Hence:

              \(\ds \sum_{n \mathop = 1}^ \     \(\    $2$nd
                \infty \frac {F_{n - 1} } (=    ds 1   Kolmogorov
                                  {2^n}\) \)    \)     Axiom
    \(\ds \   \(\ds \sum_{n \mathop = 0}^ \     \(\    reindexing
  leadsto \    \infty \frac {F_n} {2^{n + (=    ds 1   the sum
       \ \)                        1} }\) \)    \)
    \(\ds \   \(\ds \sum_{n \mathop = 0}^ \     \(\    multiplying
  leadsto \    \infty \frac {F_n} {2^n}\) (=    ds 2   both sides by
       \ \)                               \)    \)     $2$

$\blacksquare$


[INS::INS]
Retrieved from "https://proofwiki.org/w/index.php?title=Main_Page&
oldid=546458"
Categories:

  * Proven Results
  * Sum of nth Fibonacci Number over nth Power of 2

Navigation menu

Personal tools

  * Log in
  * Request account

Namespaces

  * Main Page
  * Discussion

[ ] English

Views

  * Read
  * View source
  * View history

[ ] More

Search

[                    ] [Search] [Go]
 

Navigation

  * Main Page
  * Community discussion
  * Community portal
  * Recent changes
  * Random proof
  * Help
  * FAQ
  * $\mathsf{Pr} \infty \mathsf{fWiki}$ $\LaTeX$ commands

ProofWiki.org

  * Proof Index
  * Definition Index
  * Symbol Index
  * Axiom Index
  * Mathematicians
  * Books
  * Sandbox
  * All Categories
  * Glossary
  * Jokes

To Do

  * Proofread Articles
  * Wanted Proofs
  * More Wanted Proofs
  * Help Needed
  * Research Required
  * Stub Articles
  * Tidy Articles
  * Improvements Invited
  * Refactoring
  * Missing Links
  * Maintenance

Tools

  * What links here
  * Related changes
  * Special pages
  * Printable version
  * Permanent link
  * Page information

  * This page was last modified on 12 November 2021, at 21:57 and is
    359 bytes
  * Content is available under Creative Commons
    Attribution-ShareAlike License unless otherwise noted.

  * Privacy policy
  * About ProofWiki
  * Disclaimers

  * Creative Commons Attribution-ShareAlike License
  * Powered by MediaWikiPowered by MathJax