Do you mean Prob(at least 1 observation of 2 consecutive heads appears) ?? Then since the subsets can be: 1. all tails 2. 1 head 1 tail 1 head 1 tail .... 3. at least 2 heads consecutively appear once So Pr(3) = 1- Pr(1) - Pr(2) = 1- (1/2)^N - (1/2)^N = 1 - power(1/2,N-1)

I think the answer should be this: Since the probability of getting two heads in a row and getting two tails in a row is the same, we only need to figure out the probability of the total. The remaining event is: 1 head 1 tail......due to different order, events should be 2 Therefore the probability=0.5(1-2(1/2)^N)=0.5(1-(1/2)^(N-1))

Only solution I could think of, which took quite some time, was to actually start by drawing a tree of possible outcomes. From there, I could see only three different states at each node. Either I am in a state similar to my initial state (when I toss a tail), I can also be in tilt state (I have just flipped heads after flipping a tail) or I am in the done state (I have just flipped heads after having flipped heads before). I consider that someone would only continue flipping if he/she has not flipped two heads in a row. That is, is not in the done state. That is, for any toss level N, it wrong to assume that number of nodes is equal to 2^N. It will be strictly smaller as of level N = 3. Anyway, after 3-4 levels drawn, one should see a pattern, that is, the number of tails, or initial state nodes (is), at a level N is equal to the number of is's I had at level N-1 + the number of is's I had at level N-2. We can thus write: is(N) = is(N-1) + is(N-2). we then realize that at every level N, the number of tilt nodes (t) is equal to the number of initial states from the previous level. That is: t(N) = is(N-1) That makes sense, because on the level N-1, all initial states output one tail (becoming a new initial state at level N) and a heads (becoming a tilt state at level N). the other states of level N-1 are either done (so no continuation) or tilt. The possible outcomes of a tilt state are either done or initial state (if I flip heads again, I am done, so I can't go from tilt to tilt.) One then realize that following the same logic, the number of done (d) nodes for a level N is given by: d(N) = t(N-1) = is(N-2) that is, at every level (as of the second level, or two tosses), I will have a number of done outcomes equal to the number of initial states to levels (or tosses) ago. So the general recursive formula to get the number of done nodes for a certain level really is: d(N) = is(N-2) = is(N-3) + is(N-4) We note, by definition: is(N) = 0, is N<0 is(N) = 1, if N = 0, or 1 is(N) = is(N-1) + is(N-2) otherwise. Furthermore, the probability of being at any node of a level N is simply (1/2)^N. So if I want to find the probability that I observed at least one occurrence of 2 heads in a row. I simply add the number of done nodes from level 1 to N multiplying them by the probability of them occurring at each level. That is: P(hh after N tosses) = sum(from i = 1 to N) (d(i).(1/2)^i). E.g. for N = 2, I get: d(1).1/2 + d(2).(1/4) = s(-1).1/2 + s(0).(1/4) = 0 + 1/4. We know that this is true. you can test it for a larger number of tosses and see it is true. as N goes to infinity, the sum will converge to 1, as I have theoretically no chance of never tossing 2 heads in a row if I throw a coin an infinity number of times. I haven't found a solution that didn't use recursions. There probably is one, I'd be interested in seeing one.

sorry for all the typos, the solution should be understandable in spite of that.

This can be solved by considering the number of sequences of heads/tails that do NOT have consecutive heads. If N coins are tossed, you can have 0 heads in 1 way. You can have 1 head in N ways--choose 1 from any of the N positions in the sequence. You can have 2 heads as long as they are not consecutive. Imagine you have N-2 tails and you need to decide where to place the 2 heads. You can insert them before any of the tails, or after the last tail--so you need to choose 2 out of a possible N-1 positions. Similarly, for any H less than or equal to N/2, you can have H heads by selecting H positions from a possible (N-H)+1 positions. So the number of sequences which do NOT have two consecutive heads can be found by the sum: 1 + nCr(N,1) + nCr(N-1,2) + nCr(N-2,3) + ... Evaluating this starting with N = 2 gives the values 3, 5, 8, 13, 21, 34, ... These are Fibonacci numbers. The number of sequences of length N without 2 consecutive heads is given by F_{N+2}, where F_1 = 1, F_2 = 1, and F_N = F_{N-1} + F_{N-2}. It follows that the probability for obtaining two consecutive heads in N flips of a fair coin is given by 1 - ( F_{N+2}/ 2^N). Note: j-dw has a correct solution. The solution given by Charles ignores the fact that many sequences will have BOTH two consecutive tails AND consecutive heads. He treats these as non-overlapping sets. Delusion ignores all cases such as HTTHTTHTT in which there is more than one T separating the heads.