4 ms·

> 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).