Help me!
For each non-negative integer n let c(n), denote the number of lists of n numbers each chosen from {0, 1, 2} but with no two consecutive 1s and no two consecutive 2s. So, for example, c(3) = 17, the seventeen lists being
000, 001, 002, 010, 012, 020, 021, 100, 101, 102, 120, 121, 200, 201, 202, 210, 212.
Show that the c(n)s satisfy the recurrence relation c(0) = 1, c(1) = 3 and c(n) = 2c(n-1 )+ c(n-2) (n > 1).
Hint: Let $d(n), e(n), f(n)$ refer to the number of such strings that end with 0, 1, 2.
Clearly, we have
$c(n) = d(n) + e(n) + f(n) $
$ e(n) = f(n)$
$d(n) = d(n-1) + e(n-1) + f(n-1)$
$e(n) = d(n-1) + f(n-1)$
$f(n) = d(n-1) + e(n-1)$
Can you take it from here?