3 ms·

The featured proof about the sum of Fibonacci numbers divided by 2^n is beautiful. When I started reading the proof I thought it was a mistake, a mismatch betw

The featured proof about the sum of Fibonacci numbers divided by 2^n is beautiful. When I started reading the proof I thought it was a mistake, a mismatch between the theorem to proof and the linked proof. I didn't expect using Kolmogorov axioms to prove this kind of sums. I really enjoyed reading it. I just learned something new today, thanks!

krackers 3y ago
I found a more detailed explanation of that proof at https://www.youtube.com/watch?v=4ApWBYBsc9k https://www.youtube.com/watch?v=4ApWBYBsc9k It also wasn't immediately clear to me that this _is_ a valid sample space, the explanation in https://old.reddit.com/r/math/comments/18szn6y/anyone_use_proof_wiki/kfciwa8/ https://old.reddit.com/r/math/comments/18szn6y/anyone_use_pr... provides a more formal but still readable construction I especially like the "finite" variant/version of the proof which reframes this as a counting/combinatorial proof instead of a probability-based one.
md224 3y ago
> However, we also see that for only those combinations starting with a T (that is f(n - 1))... Why is that f(n - 1)?
- ihm 3y ago
  The set of sequences of length n ending in HH (and with no earlier HH) and beginning with a T are in bijection with the set of sequences of length n-1 ending in HH (and with no earlier HH) by the bijection def f(s): assert(s[0] == 'T') return s[1:] whose inverse is def f_inverse(s): return 'T' + s
  - hayd 3y ago
    Also the bijection between sequence of length n ending in HH (and no earlier HH) and beginning with an H are a bijection with the set of sequences of length n-2 ending in HH (with no earlier HH) by the bijection: def f(s): assert(s[0] == 'H') assert(s[1] == 'T') # can't be another H! def f_inverse(s): return 'HT' + s Therefore, since sequences either begin with a T or an H, for n>=2 we see f(n) = f(n-1) + f(n-2).

krackers 3y ago

I found a more detailed explanation of that proof at https://www.youtube.com/watch?v=4ApWBYBsc9k https://www.youtube.com/watch?v=4ApWBYBsc9k It also wasn't immediately clear to me that this _is_ a valid sample space, the explanation in https://old.reddit.com/r/math/comments/18szn6y/anyone_use_proof_wiki/kfciwa8/ https://old.reddit.com/r/math/comments/18szn6y/anyone_use_pr... provides a more formal but still readable construction I especially like the "finite" variant/version of the proof which reframes this as a counting/combinatorial proof instead of a probability-based one.

md224 3y ago

> However, we also see that for only those combinations starting with a T (that is f(n - 1))... Why is that f(n - 1)?

ihm 3y ago
The set of sequences of length n ending in HH (and with no earlier HH) and beginning with a T are in bijection with the set of sequences of length n-1 ending in HH (and with no earlier HH) by the bijection def f(s): assert(s[0] == 'T') return s[1:] whose inverse is def f_inverse(s): return 'T' + s
- hayd 3y ago
  Also the bijection between sequence of length n ending in HH (and no earlier HH) and beginning with an H are a bijection with the set of sequences of length n-2 ending in HH (with no earlier HH) by the bijection: def f(s): assert(s[0] == 'H') assert(s[1] == 'T') # can't be another H! def f_inverse(s): return 'HT' + s Therefore, since sequences either begin with a T or an H, for n>=2 we see f(n) = f(n-1) + f(n-2).