34 Using the digits $0,1,2,3$ and 4, find the number of 13 -digit sequences that can be written so that the difference between any two consecutive digits is 1 .
Examples of such 13-digit sequences are 0123432123432,2323432321234 and 3210101234323.
34 Answer: (3402)
We call a sequence that satisfy the condition a "good" sequence.
Let $A_{n}$ denote the number of "good" sequence that end in either 0 or 4 , $B_{n}$ denote the number of "good" sequence that end in either 1 or 3 , $C_{n}$ denote the number of "good" sequence that end in 2 .
We have
(1) $A_{n+1}=B_{n}$ because each sequence in $A_{n+1}$ can be converted to a sequence in $B_{n}$ by deleting its last digit.
(2) $B_{n+1}=A_{n}+2 C_{n}$ because each sequence in $A_{n}$ can be converted into a sequence in $B_{n+1}$ by adding a 1 (if it ends with a 0 ) or a 3 (if it ends with a 4) to its end, and each sequence in $C_{n}$ can be converted into a sequence in $B_{n}$ by adding a 1 or a 3 to it.
(3) $C_{n+1}=B_{n}$ because each sequence in $C_{n+1}$ can be converted to a sequence in $B_{n}$ by deleting the 2 at its end.

Hence we can show that $B_{n+1}=3 B_{n-1}$ for $n \geq 2$.
Check that $B_{1}=2$ and $B_{2}=4$, so $B_{2 n+1}=2 \times 3^{n}$ and $B_{2 n}=4 \times 3^{n-1}$.
So $A_{13}+B_{13}+C_{13}=2 B_{12}+B_{13}=2 \times 4 \times 3^{5}+2 \times 3^{6}=3402$.