Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
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$? –  alexbake Dec 2 '12 at 18:26
    
Z(1) enumerates the set {10,20}. –  Did Dec 2 '12 at 18:38
    
Thanks for the help! –  alexbake Dec 2 '12 at 18:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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