Starting with the digit 0, make a string of symbols by the substitution rule $$0 → 10, 1 → 100$$ (a) Write down the first four strings (including the initial string $0$) which results from the application of the substitution rule.
(b) Let an and $A_n$ denote the number of digits $0$ or $1$ in the string after $n$ applications of the substitution rule (the initial string $0$ is for $n = 1$). Let $B_n$ denote the total number of digits in the $n’th$ string. Show that
$B_n = 2B_{n-1} + B_{n−2}$, for $(n ≥ 3)$ with $B_1 = 1, B_2 = 2.$
For part (a) I have
$n = 1$, string is $0$
$n = 2$, string is $10$
$n = 3$, string is $10010$
$n = 4$, string is $100101010010$
From these 4 strings it is clear that the recurrence is correct but I don't know how to go about constructing it.
I was thinking every string $B_n$, will have the string $B_{n-1}$ at the head and the tail and the string $B_{n-2}$ in between. But I don't really know where to go from here. Any help/tips will be greatly appreciated.
Let $a_n$ be the number of $0$'s, $A_n$ be the number of $1$'s, $B_n$ be the total at the $n$'th round. Then
(1) $$ B_n = a_n + A_n. $$
Since each $0$ generates a $0$, each $1$ two $0$'s for the next round, we get
(2) $$ a_{n+1} = a_n + 2\, A_n, $$
Similarly, each $0$ generates a $1$, and each $1$ generates a $1$, we get
(3) $$ A_{n+1} = a_n + A_n = B_n, $$ where we used (1) in the last step.
Shift $n$ by one, we get
(4) $$ A_n = B_{n-1} $$
Adding (2) and (3), we get
(5) $$ B_{n+1} = 2 \, B_n + A_n = 2\, B_n +B_{n-1}. $$ where we have used (4) in the last step.
By the way, $B_n$'s are the Fibonacci numbers, and the solution of (5) is $$ B_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right]. $$