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!

  • $\begingroup$ Awesome, adding the same bit gives the same number of blocks, adding a different bit gives you the same number of blocks + 1, hence twice as many blocks and half of the strings have an extra block. Thanks! $\endgroup$
    – user151948
    Jun 16 '14 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.