[ihm]

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]

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