The original question:
If I toss a coin 15000 times, what is the probability that I'll get at least 15 consecutive heads at least once.
The workup:
Consider a toy example, 2 consecutive heads in 5 flips, we have the following cases (where X is don't cares):
Toss | Result
------|-------
HHXXX | True
THHXX | True
?THHX | True
??THH | True
Other | False
The ?s are because in order to avoid double counting cases we require that the ?s not result in our goal. Let $C(f, h)$ represent the number of successful cases out of all the $2^f$ cases, and let $\neg C(f, h) = 2^f - C(f, h)$ representing the number of unsuccessful cases. In this case our toy example is:
$$C(5, 2) = 2^3 \text{(from the Xs on line one)} + \neg C(0, 2) \cdot 2^2 \text{(line two)} + \neg C(1, 2) \cdot 2 \text{(line three)} + \neg C(2, 2) \text{(line four)}$$
This gives 19.
Let's consider what happens when we go up by one:
Toss | Result
---------|-------
HHXXX(X) | True
THHXX(X) | True
?THHX(X) | True
??THH(X) | True
(???THH) | True
Other | False
So we have an extra X for each of the lines that were in C(5,2) and one more line.
$$C(6,2) = 2 C(5,2) + \neg C(3,2)$$
From this we can deduce a method of increasing the number of flips by one:
$$C(f+1, h) = 2 C(f, h) + \neg C(f-(h+1), h)$$
And then we can set some initial conditions:
$$\begin{split} C(f=h, h) &= 1 \\ C(f<h, h) &= 0 \\ \end{split}$$
Finally the probability of any $f, h$ pair is simply:
$$P(f,h) = \frac{C(f,h)}{2^f}$$
My question:
From here it's possible to simply let a computer crunch on this to get a solution. However, just for the sake of curiosity, I wanted to come up with an explicit formula. What I would normally do is come up with a matrix form of this formula then perform an eigendecomposition on it.
$$\begin{pmatrix} 2 & 0 & 0 & \dots & ? \\ 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 0 \\ \end{pmatrix} \begin{pmatrix} C(f,h) \\ C(f-1,h) \\ C(f-2,h) \\ \vdots \\ C(f-(h+1),h) \\ \end{pmatrix} = \begin{pmatrix} C(f+1,h) \\ C(f,h) \\ C(f-1,h) \\ \vdots \\ C(f-h,h) \\ \end{pmatrix} $$
But I don't think it's possible to cleanly represent $\neg C$ in this fashion, and that's what needs to go into the spot with the ?.
So next I tried to get rid of the $2^f$ in the formula.
$$\begin{split} C(f, h) &= 2C(f-1, h) + 2^f - C(f-(h+2), h) \\ C(f-1, h) &= 2C(f-2, h) + 2^f - C(f-(h+3), h) \\ C(f, h) &= 3C(f-1, h) - 2C(f-2, h) - C(f-(h+2), h) + C(f-(h+3),h) \\ \end{split}$$
And this works. However, when I put all of this together, and take the eigenvectors, one eigenvector is {0, 0, 0, ..., 0}. So the matrix of eigenvectors is singular, so I can't use the $S\Lambda^nS^{-1}$ formula.
Is there an approach that will work in this case?
Let $p_n$ be the probability that you get $15$ consecutive heads when you flip a coin $n$ times. A recurrence relation is $$ p_n = \frac12p_{n-1} + \frac14 p_{n-2}+\frac18p_{n-3} + \dots + \frac{1}{2^{14}}p_{n-14}+\frac{1}{2^{15}}p_{n-15} + \frac1{2^{15}}\tag{$n\ge 15$} $$ The first term accounts for the cases where you flip $T$ first, and you now need to get $15$ heads in a row in the remaining $n-1$ flips. The next term is for when your first two flips are $HT$, the third when they are $HHT$, etc. The last term account for when the first 15 flips are all heads.
The trick you tried works to get rid of the $\frac1{2^{15}}:$
$$ p_n-p_{n-1}=\frac12p_{n-1}-\frac14p_{n-2}-\frac18p_{n-3}-\dots-\frac{1}{2^{15}}p_{n-15}-\frac1{2^{15}}p_{n-16} $$ You can now put this in matrix form and find the eigenvalues, etc.
Letting $C_n$ be the number of sequences of flips with a run of 15 heads, which is $C(n,15)$ in your notation, then $$ C_n = C_{n-1}+C_{n-2} + \dots + C_{n-15} + 2^{n-15}. \tag{1} $$ To get rid of the $2^{n-15}$, you should instead subtract two times the previous eqaution: $$ 2C_{n-1} = 2C_{n-2}+\dots +2C_{n-15}+2\cdot 2^{n-16} $$ The result is $$ C_n = 3C_{n-1}-C_{n-2}-\ldots-C_{n-15}-2C_{n-16} $$
If you apply the usual subtraction trick to $(1)$, you get $$ C_n = 2C_{n-1} - C_{n-16} + 2^{n-16} $$ which is exactly the recurrence you had before.