[hayd]

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