A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s. A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s. (A binary sequence only uses the numbers 0 and 1 for those who don't know) 
B) Repeat for n-digit ternary sequences. (only uses numbers 0, 1, and 2) 
C) Repeat for n-digit ternary sequences with no consecutive 1s or consecutive 2s.
 A: for the binary case the recurrence relation as follows:
$a_{n}=a_{n-1}+a_{n-2}$. 
why?
because any n-digit binary sequence has to start with $0$ or $1$ since it is
binary.
If it starts with $0$ the rest will be same with the $a_{n-1}$, if it starts
with $1$ then next number has to be $0$ meaning that it will start exactly
with $10$ so the rest now will be same with $a_{n-2}$.
......................
by using similar idea, for the ternary case we have the following:
$a_{n}=2a_{n-1}+2a_{n-2}$
the sequence can start with $0,1$ or $2$.
if the sequence starts with $0$ or $2$ then the rest will be same with $%
a_{n-1}$, if the sequence starts with $1$, next one can be $0$ or
$2$, so it can be start with $10$ or $12,$ the rest will be same
with $a_{n-2}$.
As a result, since we have two choices for both cases we have recurrence
with coefficient $2.$
.......
for part C i refer to Recurrence relation for the number of $n$-digit ternary sequences with no consecutive $1$s or $2$s
the solution also can be obtained by same argument with part A and B.
A: Let $b_n$ be the number of ways we can produce a ternary sequence of length $n$ with no two consecutive $1$'s.  Call such $n$-sequences good. 
There are two types of good sequence of length $n$, (i) the ones that don't end in $1$  and (ii) the ones that do end in $1$. 
Any Type (i) good sequence of length $n$ can be obtained in $2$ ways from a uniquely determined good sequence of length $n-1$ by appending a $0$ or a $2$. So there are $2b_{n-1}$ of them.
Any Type (ii) good $n$-sequence can be obtained from an arbitrary good sequence of length $n-2$ by appending $01$ or $21$. So there are $2b_{n-2}$ of them.
That yields the recurrence $b_n=2b_{n-1}+2b_{n-2}$.
Though we were not asked, one should add that $b_0=1$ and $b_1=3$. 
Problem a) is somewhat easier, and problem c) somewhat harder.
