This answer has a "motivational" stage, and afterwards a "calculations" stage. Even if the deduction of the formulas is not as pleasant as the formulas provided by the OP and leonbloy, I think that my answer qualifies as "nice", at least because I obtain a decreasing recurrence and because of its "constructive" flavor. Please prepare yourself to see a lot of summation symbols, but do not get impatient, just don't forget the moral of the reasoning, and feel free to skip the easy steps.
STAGE 1: MOTIVATION
I always try to solve problems concerning random binary strings in a constructive manner. Then we can ask: how to "construct" an "admissible" string?
This is how I proceed: let us say that you want that the desired condition be fulfilled at the $r$-th run of $1$s (shortly, $1$-run) and not before. Then you construct the previous $1$-runs with prescribed lengths $k_1,k_2,\dots,k_{r-1}\geq1$. Now we must interleave $0$-runs between our $1$-runs. The first $0$-run, which we will be put before the first $1$-run, can have any length $i_1$ including zero (because your sequence may or not start with $1$). On the other hand, the other dividing $0$-runs must have positive length (because they must separate our $1$-runs).
Therefore the lengths $i_1,\dots,i_r$ of the $0$-runs satisfy $i_1\geq0$ and $i_2,\dots,i_r\geq1$. Finally, the $r$-th $1$-run must have length greater or equal than $n+k_1+\cdots+k_{r-1}$. Actually, we can suppose that this length is exactly equal to $n+k_1+\cdots+k_{r-1}$, because in this case it does not matter how the rest of the sequence is.
Of course, the desired condition is not fulfilled before the $r$-th step if and only if $k_j\leq s_{j-1}$ for $j=1,\dots,r-1$, being $s_j=n-1+k_1+\cdots+k_j$ ($s_0=n-1$).
The set of sequences constructed in the way described above, with the values $k_i$ and $i_j\ $ fixed has probability
$\underbrace{2^{-(i_1+\cdots+i_r)}}_{0\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{2^{-(k_1+\cdots+k_{r-1})}}_{\style{font-family:inherit;}{\text{faulty}}\ 1\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{2^{-(n+k_1+\cdots+k_{r-1})}}_{\style{font-family:inherit;}{\text{successful}}\ 1\text{-}\style{font-family:inherit;}{\text{run}}}\,.$
It remains to sum this value over all admissible values of $r,i_1,\dots,i_r,k_1,\dots,k_{r-1}$. In other words, the desired probability is equal to
$\sum_{r=1}^\infty\Biggl[\,\sum_{i_1=0}^\infty\sum_{i_2=1}^\infty\cdots\sum_{i_r=1}^\infty\Biggr]\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}2^{-(i_1+\cdots+i_r)}\,2^{- (k_1+\cdots+k_{r-1})}\,2^{-(n+k_1+\cdots+k_{r-1})}\,.$
The part of the sum involving the $i_j$ can be easily solved: recall that $\sum_{i=0}^\infty 2^{-i}=2$ and $ \sum_{i=1}^\infty2^{-i}=1$, so our sum simplifies to
$2^{1-n}\sum_{r=1}^\infty\ \sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}4^{-(k_1+\cdots+k_{r-1})}\,.$
Now we concentrate on the inner sum, that is, with $r$ fixed. We have
$\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}4^{-(k_1+\cdots+k_{r-1})}=\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}\sum_{k_{r-1}=1}^{s_{r-2}}4^{-k_{r-1}}\,.$
Since $\sum_{k=1}^s4^{-k}=\frac13(1-4^{-s})$, our sum becomes
$\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}(1-4^{-s_{r-2}})$
$=\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}-\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}4^{-s_{r-2}}$
$=\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}-\frac13\,4^{-(n-1)}\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-2(k_1+\cdots+k_{r-2})}$
Now I will try to convince you that this is indeed a decreasing recurrence, unlike OP and leonbloy's approach (which of course are very clever and illuminating). This is a good time to make a generalization of the problem and introduce some convenient notation:
STAGE 2: CALCULATIONS
Let $p\in(0,1)$ and let $q=1-p$. Now we suppose that the probability of $1$ in each place of a binary string is equal to $p$ (so the probability of $0$ is $q$). In the case of interest we have $p=q=1/2$, but the general case is not harder than this particular case.
Reasoning as in the previous stage, the probability of the set of desired sequences with the numbers $r,i_1,\dots,i_r,k_1,\dots,k_{r-1}$ fixed is equal to
$\underbrace{q^{i_1+\cdots+i_r}}_{0\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{p^{k_1+\cdots+k_{r-1}}}_{\style{font-family:inherit;}{\text{faulty}}\ 1\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{p^{n+k_1+\cdots+k_{r-1}}}_{\style{font-family:inherit;}{\text{successful}}\ 1\text{-}\style{font-family:inherit;}{\text{run}}}\,,$
It is important to distinguish the case $r=1$ of the probability above: in this case there is no choice of numbers $k_1,\dots,k_{r-1}$, we only choose $i_1\geq0$, so in this case the probability is equal to $p^nq^{i_1}$. Thus, the total probability is equal to
$\sum_{i_1=0}^\infty p^nq^{i_1}+\sum_{r=2}^\infty\Biggl[\,\sum_{i_1=0}^\infty\sum_{i_2=1}^\infty\cdots\sum_{i_r=1}^\infty\Biggr]\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}q^{i_1+\cdots+i_r}\,p^{k_1+\cdots+k_{r-1}}\,p^{n+k_1+\cdots+k_{r-1}}\,.$
$=\frac{p^n}{1-q}+\frac{p^n}{1-q}\sum_{r=2}^\infty\biggl(\frac{q}{1-q}\biggr)^{r-1}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}\bigl(p^2\bigr)^{k_1+\cdots+k_{r-1}}\,.$
Define
$S(\alpha,1)=1;\ S(\alpha,r)=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}\alpha^{k_1+\cdots+k_{r-1}}\,,\ \style{font-family:inherit;}{\text{for}}\ r\geq2\,.$
Then our probability can be written as
$\frac{p^n}{1-q}\sum_{r=1}^\infty\biggl(\frac{q}{1-q}\biggr)^{r-1}S(p^2,r)\,.$
We have $S(\alpha,1)=1$, and for $r\geq2$:
$S(\alpha,r)=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}\sum_{k_{r-1}=1}^{s_{r-2}}\alpha^{k_{r-1}}$
$=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}\biggl[\frac{\alpha}{1-\alpha}\,(1-\alpha^{s_{r-2}})\biggr]$
$=\frac{\alpha}{1-\alpha}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}-\frac{\alpha}{1-\alpha}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}+s_{r-2}}$
$=\frac{\alpha}{1-\alpha}S(\alpha,r-1)-\frac{\alpha}{1-\alpha}\,\alpha^{n-1}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{2(k_1+\cdots+k_{r-2})}$
$=\frac{\alpha}{1-\alpha}\,S(\alpha,r-1)-\frac{\alpha^n}{1-\alpha}\,S(\alpha^2,r-1)\,.$
Changing $\alpha$ by $\alpha^j$, we obtain, for $r\geq2$:
$S(\alpha^j,r)=\frac{\alpha^j}{1-\alpha^j}\,S(\alpha^j,r-1)-\frac{\alpha^{jn}}{1-\alpha^j}\,S(\alpha^{2j},r-1)\,.$
Why the hell I did this? because defining
$b_j=\frac{\alpha^j}{1-\alpha^j},\ c_j=-\,\frac{\alpha^{jn}}{1-\alpha^j}\quad \style{font-family:inherit;}{\text{and}}\quad T(j,r)=S(\alpha^j,r)$
the recurrence becomes
$T(j,1)=1;\quad T(j,r)=b_j\,T(j,r-1)+c_j\,T(2j,r-1),\ \style{font-family:inherit;}{\text{for}}\ r\geq2\,.$
OK, I agree that this is not a genuine decreasing recurrence, as index $j$ is increasing; fortunately, the index $r$ decreases. In general, these recurrences can be explicitly solved, either by bare hands or using computer algebra systems. Later I will try to solve it step by step, for the benefit of those who believed (or disbelieved?) me and endured up this point.