For $n\ge 0$ let $a(n)$ be the number of strings of length n that only contain digits among $0\cdots\, 4,$ and do not contain the string $00$. Find a recurrence relation and give initial conditions for the sequence $a(0),\, a(1),\, \cdots$
Unsure of how to start this question.
If $a(n+1)$ is the number of such strings of length $n+1$, let $b(n+1)$, $c(n+1)$, $d(n+1)$, $e(n+1)$ and $f(n+1)$ denote the number of such strings ending in $0, 1, 2, 3$ and $4$ respectively so that $$a(n+1)=b(n+1)+c(n+1)+d(n+1)+e(n+1)+f(n+1)$$ It is easy to see that $c(n+1)=d(n+1)=e(n+1)=f(n+1)=a(n)$. Now if the $n+1$ length string ends in $0$, then it is clear that the number in the $n$th position cannot be $0$ and the previous $n-1$ length string cannot have two consecutive zeros. So $$b(n+1)=c(n)+d(n)+e(n)+f(n)=4a(n-1).$$ Thus, $$a(n+1)=4a(n)+4a(n-1)$$ with initial conditions $a(0)=1$ and $a(1)=5$.