What is the probability in n flips of a fair coin that there will be two heads in a row?

Well, the question is then how many strings of n h's and t's contain
hh?  I would guess right off hand that its going to be easier to
calculate the number of strings that _don't_ contain hh and then
subtract that from the total number of strings.

So we want to count the strings of n h's and t's with no hh in them.
How many h's and t's can there be? It is fairly clear that there must
be from 0 to n/2 h's, inclusive. (If there were (n/2+1) then there
would have to be two touching.)

How many strings are there with 0 h's? 1

How many strings are there with 1 h? Well, there are (n-1) t's, so
there are a total of n places to put the one h. So the are nC1 such
strings.  How many strings are there with 2 h's? Well, there are (n-1)
places to put the two h's, so there are (n-1)C2 such strings.

Finally, with n/2 h's there are (n/2+1) places to put them, so there
are (n/2+1)C(n/2) such strings.

Therefore the total number of strings is
Sum (from i=0 to n/2) of (n-i+1)C(i)

Now, here's where it get's interesting. If we play around with Pascal's
triangle for a while, we see that this sum equals none other than the
(n+2)th Fibonacci number.

So the probability that n coin tosses will give a hh is:

2^n-f(n+2) 
----------
2^n

(where f(x) is the xth Fibonacci number (so that f(1) and f(2) are both 1))