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!


Let $Y(n)$ enumerating the admissible words of length $n$ whose last letter is not $0$ and $Z(n)$ enumerating the admissible words of length $n$ whose last letter is $0$. Then $Y(n+1)=2U(n)$ and $Z(n+1)=Y(n)$, hence $$ Z(n+1)=2Z(n)+2Z(n-1). $$ One sees that $U(n)=Y(n)+Z(n)=Z(n+1)+Z(n)$ and that $(Z(n))_n$ is a linear combination of the sequences $(r^n)_n$ and $(s^n)_n$, where $r$ and $s$ are the roots of the polynomial $x^2-2x-2$, that is, $$ r=1+\sqrt3,\qquad s=1-\sqrt3. $$ The initial conditions $Z(0)=1$ and $Z(1)=2$ imply that $Z(n)=\dfrac{r^{n+1}-s^{n+1}}{r-s}$ for every $n\geqslant0$, hence $$ U(n)=\frac{(1+r)r^{n+1}-(1+s)s^{n+1}}{r-s}=\frac{r^{n+3}-s^{n+3}}{4\sqrt3}. $$

  • $\begingroup$ Thanks. I actually got had $U(n) = 2*U(n-1) + 2*U(n-2)$ which gave me $c_1 = 1 + \sqrt{3}$ and $c_2 = 1 - \sqrt{3}$. However, I may have set it up wrong, because I used my initial condition that $U(1) = 3$ which caused me to get a completely wrong formula. Why is $Z(1) = 2$? $\endgroup$ – alexbake Dec 2 '12 at 18:26
  • $\begingroup$ Z(1) enumerates the set {10,20}. $\endgroup$ – Did Dec 2 '12 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.