How would one go about solving a recurrence relation that has different cases?
The whole problem asks for
Derive a formula for the number of strings of length n over the alphabet $\{0, 1, 2\}$ which have no consecutive 0's.
So my recurrence relation will be $U(n)$ where $U(n)$ is the number of strings of length $n$ that contain no consecutive $0$'s. First I figure out the base cases.
$U(0) = 1$ because the only string of length $0$ is, $\Lambda$, the empty string.
$U(1) = 3$ because all strings of length $1$ in our alphabet will contain no consecutive $0$'s.
$U(2) = 8$ because $\{1,2,3\}^2$ has $9$ possible strings, and the only one with consecutive $0$'s would be "$00$"
Where I would like clarification: So now I need to figure out
How many length n strings have no occurrences of the substring "$00$" and end with each of the characters $0, 1,$ or $2$.
Case $0$: $U(n) = 2*U(n-2)$ because we can take any $U(n-2)$ string, and then add a $1$ or a $2$ then add a final $0$
Case $1$ & $2$: $U(n) = 2*U(n-1)$ because we can choose any $U(n-1)$ string, and simply add a $1$ or $2$ to the end.
I don't know if these are right at all. I also don't really know how to combine the cases. Any help would be appreciated!