Now Reading
ProofWiki

ProofWiki

2024-02-04 11:51:58

Logo.png

$mathsf{Pr} infty mathsf{fWiki}$ is a web based compendium of mathematical proofs! Our purpose is the gathering, collaboration and classification of mathematical proofs. If you’re focused on serving to create a web based useful resource for math proofs be happy to register for an account. Thanks and luxuriate in!

In case you have any questions, feedback, or solutions please put up on the discussion web page, or contact one of many administrators. Additionally, be happy to check out the frequently asked questions since you might not be the primary together with your thought.

To see what’s at present occurring locally, go to the community portal.

26,727 Proofs 25,226 Definitions Help

Theorem

$ds sum_{n mathop = 0}^infty frac {F_n} {2^n} = 2$

the place $F_n$ is the $n$th Fibonacci number.

Proof

Allow us to outline a sample space which satisfies the Kolmogorov Axioms such that it’s the set of all mixtures of flipping a good coin till you obtain two heads in a row.

Let $X_n$ be the occasion of some final result from flipping $n$ honest coins in a row, then $Pr(X_n) = dfrac 1 {2^n}$.

Within the sample space outlined above, we now reveal that for a given variety of flips $n$, there are precisely $F_{n – 1}$ outcomes contained within the sample space.

Illustration

$start{array}cc
n & map f n & textual content {Pattern Area}: Omega
hline
1 & 0 & textual content {not possible}
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
finish{array}$

Reviewing the illustration above, for any given worth of $n$:

For ALL mixtures displayed in row $n$ (that’s $map f n$) , we are able to place a $T$ in entrance and that new mixture would exist within the sample space for $paren {n + 1}$.

For instance:

$paren {HTHH}, paren {TTHH} to paren {THTHH}, paren {TTTHH}$

Nevertheless, we additionally see that for under these mixtures beginning with a $T$ (that’s $map f {n – 1}$), can we place an $H$ in entrance and that new mixture will even exist within the sample space for $paren {n + 1}$.

See Also

For instance:

$paren {TTHH} to paren {HTTHH}$

Subsequently, we’ve:

(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 including a $T$ in entrance and $map f {n – 1}$ is including an $H$ in entrance
(ds ) (=) (ds F_{n – 1} + F_{n – 2})
(ds ) (=) (ds F_n)

The sum of the possibilities of outcomes in a pattern area is one by the second Kolmogorov Axiom.

((textual content {II}))   $:$      (ds map Pr Omega )   (ds = )   (ds 1 )      

Therefore:

(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 each side by $2$

$blacksquare$



Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top