(a) There are 2 sequences of length 1 that fit the bill: 0 and 1. So if [tex]b_n[/tex] is the number of permissible sequences, then [tex]b_1=2[/tex].
To the sequence 0, we can attach either 0 or 1 at the end, while the sequence 1 must be followed by 0. Then the permissible sequences of length 2 are 00, 01, and 10, so [tex]b_2=3[/tex].
Now consider a sequence of length n + 1, of which there are [tex]b_{n+1}[/tex].
• If the last digit is 0, then we got this sequence by simply joining 0 to one of [tex]b_n[/tex] sequences. In other words, there are [tex]b_n[/tex] permissible sequences of length n + 1 that end in 0.
• If the last digit is 1, then the previous digit must have been 0. Put another way, we join 01 to a permissible sequence of length n - 1 (there are [tex]b_{n-1}[/tex] of them). So there are [tex]b_{n-1}[/tex] permissible sequences of length n + 1 that end in 1.
These cases are mutually exclusive, so the number of (n + 1)-length permissible sequences is given by
[tex]\begin{cases}b_1 = 2 \\ b_2 = 3 \\ b_{n+1} = b_n + b_{n-2} & \text{for }n\ge2\end{cases}[/tex]
(b) The reasoning for a permissible ternary sequence is similar. Let [tex]t_n[/tex] be the number of sequences of length n not containing 11.
We first note that [tex]t_1 = 3[/tex], since we can have 0, 1, or 2; and [tex]t_2 = 8[/tex], since we can have 00, 01, 02, 10, 12, 20, 21, or 22.
Consider a sequence of length n + 1 ([tex]t_{n+1}[/tex] of these).
• If the last digit is 0, then we joined 0 to a permissible sequence of length n. So there are [tex]t_n[/tex] permissible sequences of length n + 1 ending in 0.
• If the last digit is 1, then the last two digits must be either 01 or 21. Since there are 2 choices for the n-th digit, there are [tex]2t_{n-1}[/tex] permissible sequences of length n + 1 ending in 1.
• If the last digit is 2, then we essentially have the same situation as if the sequence ended in 0, so there are [tex]t_n[/tex] sequences of length n + 1 ending in 2.
Then the recurrence for ternary permissible sequences is
[tex]\begin{cases}t_1 = 3 \\ t_2 = 8 \\ t_{n+1} = 2t_n + 2t_{n-1} & \text{for }n\ge2\end{cases}[/tex]
