Given n raffles, what is the chance of winning k in a row? I was reading this interesting article about the probability of of tossing heads k times in a row out of n tosses. The final result was
$$P = 1-\frac{\operatorname{fib}_k(n+2)}{2^n}\;,$$
where $\operatorname{fib}_k(n)$ is the $n$-th $k$-step Fibonacci number.
However, I could not figure out how to adapt it to cases where the probability is not half but just some generic $p$. How do I approach that, and is there a generic solution for all $p$?
To be clear, $n$ is the number of raffles, $p$ is the probability of winning a single one, and $k$ is the number of consecutive successes required. $P$ is the desired value.
 A: We can proceed as follows.  Let $p$ be the probability that we flip a head, and $q=1-p$ the probability that we flip tails.  Let us search for the probability that we do NOT have at least $k$ heads in a row at some point after $n$ flips, which we will denote $P(n,k)$.
Given a sequence of coin tosses (of length at least $k)$ which does not have $k$ heads in a row, the end of sequence must be a tail followed by $i$ heads, where $0\leq i<k$.  We will let $P(n,k,i)$ denote the probability that a string of length $n$ has less than $k$ heads AND ends with $i$ heads.  Clearly $P(n,k)=\sum P(n,k,i)$.  (Also note that we can still work with $n<k$ by treating a string of just $i$ heads as being in the class $(n,k,i)$).
Suppose we have a series of $n$ coin flips, with no more than $k$ heads, and we are in the class $(n,k,i)$.  What can happen if we flip the coin once more?  If we get tails, we end up in class $(n+1,k,0)$, which happens with probability $q$, and if we get heads, we end up in the class $(n,k,i+1)$ which happens with probability $p$. The only caveat is that if $i=k-1$, our string will have $k$ heads in a row if the next run is a head.
From this, and using the fact that the $(n+1)$st flip is independent of the flips that came before, we can calculate:
$$P(n+1,k,i+1)=pP(n,k,i) \qquad 0\leq i<k, $$
and so 
$$P(n,k,i)=p^iP(n-i,k,0) \qquad 0\leq i<k.$$
This could have been seen more directly by noting that the only way to be in the class $(n,k,i)$ is to have a string in class $(n-i,k,0)$ and to then have $i$ heads in a row, which happens with probability $p^i$.  This means that we only need to use things of the form $P(n,k)$ and $P(n,k,0)$ in our calculations.  
By similar reasoning about how strings come about, we have
$$P(n+1,k,0)=qP(n,k)=q\sum_{i=0}^{k-1} P(n,k,i)=q\sum_{i=0}^{k-1} p^iP(n-i,k,0).$$
This gives us a nice linear recurrence relation for $P(n,k,0)$ very similar to the one for the $k$-Fibonacci numbers, and dividing by $q$, we see that $P(n,k)$ satisfies the same recurrence.  Adding the initial condition $P(n,k)=1$ if $n<k$ allows us to easily generate the values we need.
Moreover, if we multiply our recurrence by $p^{-(n+1)}$, we get a slightly simpler recurrence for $Q(n+1,k,0)=p^{-(n+1)}P(n+1,k,0)$, namely
$$Q(n+1,k,0)=\frac{q}{p} \sum_{i=0}^{k-1} Q(n-i,k,0).$$
When $p=q$, this becomes the recurrence for the $k$-Fibonacci numbers.
