1
$\begingroup$

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!

1 Answers 1

0

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}. $

  • 0
    Z(1) enumerates the set {10,20}.2012-12-02