ProofWiki is an online compendium of mathematical proofs
source link: https://proofwiki.org/wiki/Main_Page
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Welcome to Pr∞fWiki
|
Pr∞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
Featured Proof
Theorem
∞∑n=0Fn2n=2
where Fn is the nth 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 Xn be the event of some outcome from flipping n fair coins in a row, then Pr(Xn)=12n.
In the sample space defined above, we now demonstrate that for a given number of flips n, there are exactly Fn−1 outcomes contained in the sample space.
Illustration
nf(n)Sample Space:Ω10impossible21HH31THH42(HTHH),(TTHH)53(THTHH),(HTTHH),(TTTHH)65(HTHTHH),(TTHTHH),(THTTHH),(HTTTHH),(TTTTHH)⋯⋯⋯nFn−1⋯
Reviewing the illustration above, for any given value of n:
For ALL combinations displayed in row n (that is f(n)) , we can place a T in front and that new combination would exist in the sample space for (n+1).
For example:
(HTHH),(TTHH)→(THTHH),(TTTHH)
However, we also see that for only those combinations starting with a T (that is f(n−1)), can we place an H in front and that new combination will also exist in the sample space for (n+1).
For example:
(TTHH)→(HTTHH)
Therefore, we have:
| f(n) | = | Fn−1 | ||||||||||||
| f(n+1) | = | f(n)+f(n−1) | f(n) is adding a T in front and f(n−1) is adding an H in front | |||||||||||
| = | Fn−1+Fn−2 | |||||||||||||
| = | Fn |
The sum of the probabilities of outcomes in a sample space is one by the second Kolmogorov Axiom.
| (II) | : | Pr(Ω) | = | 1 |
Hence:
| ∞∑n=1Fn−12n | = | 1 | 2nd Kolmogorov Axiom | |||||||||||
| ⇝ | ∞∑n=0Fn2n+1 | = | 1 | reindexing the sum | ||||||||||
| ⇝ | ∞∑n=0Fn2n | = | 2 | multiplying both sides by 2 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK