# Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is:

"Given an infinite length random binary string, what is the expected length between consecutive blocks of at least 20 $1$'s?"

I managed to come up with a recurrence relation for the number of strings of a certain length that ended with 20 $1$'s (with no internal blocks of 20+ $1$'s). With that, I could come up with an infinite series get the expected length. But I hit a roadblock as I didn't know how to simplify the recurrence (for a specific length) and then incorporate it into an infinite series (to calculate the expected length).

Anyway, having hit that roadblock, I took a different approach. I figured out the question for expected length between blocks of at least 1 $1$, 2 $1$'s, 3 $1$'s

For example, the expected size for between for at least 1 1's (1(1)*01, 1(1)*001, 1(1)*0001,...) is 2 (easy to prove $1 + 1/2 + 1/4...$)

I proved this expected length $E(k)$ for a few values of block size at least k

$E(1) = 2$ $E(2) = 5$ $E(3) = 12$ $E(4) = 27$ $E(5) = 58$

I want to know $E(20)$ which due to my proof method I am not able to do

However, I noticed a pattern for $E(k)$

$E(k) = 2E(k-1) + k - 1$ which I'm pretty confident is correct (per computer assisted evidence...not proof)

My question is, why is this recurrence true? It must be based on the way block's of $k$ $1$'s can be built from smaller blocks, but I cannot figure it out.

• – Shaun Jul 31 '14 at 19:13