Math Help - Combinatorial Proof

1. Combinatorial Proof

2. From the way you put the question, I assume that part (a) is no problem.
Any string in $a_n$ is a string in $a_{n-1}$ with one of 1,2, or 3 added. To avoid repetition we can use only two of three. Therefore $a_n = 2 a_n$, because $a_1 = 3$ the given result easily follows.

EDIT:
Clearly any string in $b_n$ with the last number removed is a string in $a_{n-1}$. Therefore, taking any string in $a_{n-1}$ that is not in $b_{n-1}$ and adding the same number as it begins with gives a string in $b_n$. Thus $b_n=a_{n-1}-b_{n-1}$.
.

3. Plato, how would I go about proving part a?
The basis would be when n=2, so their should be 6 A-sequences. How would I show that this is true? just list them?

Then what would I do for the inductive step?

Thanks!