8
$\begingroup$

Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications"

Let P(n) be the number of strings not containg two containing two consecutive zeros or two consecutive ones.

I got the answer P(n)=P(n-1)+2P(n-2)+2P(n-3)+...+2P(0) +2

but then the book says the sequence also satisfies the recurrence relation P(n)=2P(n-1)+P(n-2). I am not able to understand this part.

$\endgroup$
9
$\begingroup$

$$P(n-1)=P(n-2)+2P(n-3)+\dots+2$$

So

$$P(n)-P(n-1)=P(n-1)+P(n-2)$$

$\endgroup$
0
5
$\begingroup$

You can think about it like this: start with a string of length $n-1$. It's last character is $x\in \{0, 1, 2\}$. If $x=0$ or $x=1$, then you have $2$ choices for how to finish (either $\{1, 2\}$ if $x=0$ or $\{0, 2\}$ if $x=1$). If $x=2$ then we have $3$ choices for how to finish: $\{0, 1, 2\}$. Let's think about what the end of strings look like. I'll let $x_{0}$ denote that the $n-1$st element is a $0$, $x_{1}$ to denote that the $n-1$st element is a $1$ and $x_{2}$ to denote that the $n-1$st element is a $2$. Strings could end in any of the following ways:

$x_0 1$

$x_0 2$

$x_1 0$

$x_1 2$

$x_2 2$

$x_2 1$

$x_2 0$

Note that if I group the first 6 of these, I have counted $2P(n-1)$ strings; this is because every one of the strings of length $n-1$ either ends in a $0$, $1$ or a $2$ and I've counted each of those occurrences twice. And, I still need to count the strings that end in $x_2 0$ (or the last two digits are $2,0$). The number of ways to end in $2,0$ is precisely $P(n-2)$ since I can append $2,0$ to any string of length $n-2$. Thus all together there are $2P(n-1)+P(n-2)$ strings that fit your criteria.

$\endgroup$
-1
$\begingroup$

Let, $F(n)$=the number of such strings with length $n$.

$Z(n)$=the number of such strings with length $n$ starting with $0$.

$W(n)$=the number of such strings with length $n$ starting with $1$.

$T(n)$=the number of such strings with length $n$ starting with $2$.

So, $F(n)=Z(n)+W(n)+T(n)$ ... (I)

But, we can easily notice that

$Z(n)=T(n-1)+W(n-1)$

$W(n)=T(n-1)+Z(n-1)$

$T(n)=T(n-1)+W(n-1)+Z(n-1)$

Putting them in equation (I), we get

$F(n)$

$= T(n-1)+W(n-1)+T(n-1)+Z(n-1)+T(n-1)+W(n-1)+Z(n-1)$

$= ( T(n-1)+W(n-1)+Z(n-1) ) + ( T(n-1)+W(n-1)+Z(n-1) ) + T(n-1)$

$= 2F(n-1) + T(n-1)$ [ From equation (I) ]

But $T(n-1)$ means you have a $2$ in the second place, which means that you can do anything with the rest of the places, in $F(n-2)$ ways. Therefore,

$F(n) = 2F(n-1) + F(n-2)$

$\endgroup$

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.