Binary string block recurrence 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.

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!
