Just to clarify: are you picking a coin at random *before each flip* or are you making this choice once and repeat toss with same coin k times?

EDIT: here http://imgur.com/rBySo2g is my diagram solution with probabilities in case you make choice once. Excuse potato quality.

Then probability for having consecutive k Heads is in your case

0.5 * (1 + 0.5 ^ k),

so k + 1-th is just

0.5 * (1 + 0.5 ^ (k + 1))

So for k = 3 it's 0.5 * (1 + 1/8) = 9/16

For k = 4 it's 0.5 * (1 + 1/16) = 17/32

As you can see, it steadily goes down, for very high number of flips it will get very close to 0.5, but still marginally *above* 0.5. The limit for this formula in sense of k -> Infinity is of course 0.5, but you can't flip infinitely many times.

EDIT: I think that I have messed up, but I can't put my finger on it. If it's any excuse, I was never any good with probability. How does one differentiate consecutive case from consecutive and a next flip? This smells of Markov Chain to me, but that's just a hunch.

I thought of it the same way Devac thought about it but given the hint it comes down to something like this.

Edits for formatting

Turn Fake ------- Real Probability

1 1/2 ---- 1 / (.5 +1)

1 1/4 ------- 1/(.25+1 )

1 1/8 --------- 1/(.125+1 )

1 1/16 -------- 1/(.0625+1 ) -94%

1 1/2^N ---------- 1/(.5^N+1 )