Explicit formula for recurrence relation (coin flipping problem) 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?
 A: As I mentioned in my comment, I had made a simple error in simplifying the recurrence relationship.
$$C(f-1, h) = 2C(f-2, h) + 2^f - C(f-(h+3), h)$$
Should have been:
$$C(f-1, h) = 2C(f-2, h) + 2^{f-(h+3)} - C(f-(h+3), h)$$
and so on...
From this it's possible to simplify the relationship as follows (third line is obtained by subtracting $2 C(f-1, h)$ from both sides and simplifying):
$$\begin{split}
C(f, h) &= 2C(f-1, h) + 2^{f-(h+2)} - C(f-(h+2), h) \\
C(f-1, h) &= 2C(f-2, h) + 2^{f-(h+3)} - C(f-(h+3), h) \\
C(f, h) &= 4C(f-1, h) - 4C(f-2, h) - C(f-(h+2), h) + 2 C(f-(h+3),h) \\
\end{split}$$
From here, the derivation is straightforward, I let a symbolic computation program crunch on it for a while and it gave the explicit formula for $C(n, 2)$ to be (n = f-h):
$$-\frac{i}{4 \sqrt{11}}\left(\text{Root}\left[\text{$\#$1}^6+42340 \text{$\#$1}^4-10128 \text{$\#$1}^2+704\&,3\right] \text{Root}\left[\text{$\#$1}^3-\text{$\#$1}^2-\text{$\#$1}-1\&,1\right]^n+\text{Root}\left[\text{$\#$1}^6+42340 \text{$\#$1}^4-10128 \text{$\#$1}^2+704\&,2\right] \text{Root}\left[\text{$\#$1}^3-\text{$\#$1}^2-\text{$\#$1}-1\&,2\right]^n+\text{Root}\left[\text{$\#$1}^6+42340 \text{$\#$1}^4-10128 \text{$\#$1}^2+704\&,6\right] \text{Root}\left[\text{$\#$1}^3-\text{$\#$1}^2-\text{$\#$1}-1\&,3\right]^n+2 i \sqrt{11} \left(2^{n+5}+1\right)\right)$$
I didn't bother to compute the explict formula for h=15.
A: 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. 
