Here is an iterative method of finding the probability. Let k and N be the quantities you described. Then perform this matlab code:
p = zeros(N,1);
p(k) = 1/2^k;
if N > k, p(k+1) = p(k) + 1/2^(k+1); end
for n = k+2:N
p(n) = p(n-1) + (1-p(n-k-1))/2^(k+1);
end
Then p(n) is the probability for k consecutive heads out of n tosses for each of the values of n in 1<=n<=N. Note: This is not a Monte Carlo method; it is an exact computation.
This is based on the notion that if p is already evaluated from p(1) to p(n-1), then the probability p(n) event occurs in two mutually exclusive ways. Either the first n-1 of the n tosses contains such a contiguous sequence of k heads or else the last k of the n tosses are all heads, the toss immediately prior to them is a tails, and the remaining initial n-k-1 of them contains no such sequence of k consecutive heads. There is no other way this event can occur with the n tosses. The first of these ways clearly has probability p(n-1) and the second has probability equal to the product
and hence p(n) is their sum.
I ran this for two cases and arrived at the following results:
k = 3;
p(10) = 0.5078125 = 520/1024
k = 5;
p(50) = 0.5518753229536166 = 621356374702220/1125899906842624
