Binary string block recurrence

Question

Let $a_n$ be the total number of blocks for all $2^n$ binary strings with length $n$. Prove the following recurrence:

\begin{equation*} a_n = 2a_{n-1} + \frac{2^{n}}{2} \end{equation*}

For example $a_2$ = 6 since 00 and 11 have 1 block each and 01, 10 have 2 blocks.

Using the equation, $a_3$ = $2(6) + \frac{2^3}{2}$ = 16 and this is shown as follows:

000 (1), 001 (2), 010 (3), 011 (2), 100 (2), 101 (3), 110 (2), 111 (1) for a total of (16) blocks.

I can see how $2a_{n-1}$ is part of the equation since there's twice as many binary strings in $a_n$ than $a_{n-1}$ but I'm not sure about $\frac{2^n}{2}$ part.

Answer 1

Hint. Consider all strings $w$ of length $n-1$. The total number of blocks is $a_{n-1}$. Now create all strings of length $n$ by appending an extra $0$ and an extra $1$ to each string. Consider two cases.

• The digit appended is the same as the last digit of $w$. How many blocks, total, are there in these words?
• The digit appended is the opposite of the last digit of $w$. How many words have we created, and how many blocks do they contain?

Good luck!