0
$\begingroup$

I know that the recurrence relation for the number of bit strings of length n that do not contain three consecutive 0s is $s_n = s_{n−1} + s_{n−2} + s_{n−3}$. Though would this be the same if you did not want three consecutive 1s instead? On one hand I think they would be the same but then I'm wondering how you would tell the difference between not containing three consecutive 0s or not containing three consecutive 1s. Could someone please explain if they are the same and why or if they are not, how you get a different recurrence relation for the number of bit strings of length n that do not contain three consecutive 1s?

$\endgroup$
1
$\begingroup$

They are the same. Let $F$ be the set of all finite bit strings, and let

$$f:F\to F:b_1b_2\ldots b_m\mapsto\hat b_1\hat b_2\ldots\hat b_m\;,$$

where $\hat 0=1$ and $\hat 1=0$. In other words, the map $f$ just changes each zero to a one and each one to a zero. It is straightforward to verify that $f$ is a bijection and that $f^{-1}=f$. Note that a bit string $\beta$ contains three consecutive ones if and only if $f(\beta)$ contains three consecutive zeroes.

Let $A_n$ be the set of bit strings of length $n$ that do not contain three consecutive ones, and let $B_n$ be the set of bit strings of length $n$ that do not contain three consecutive zeroes. Then $f[A_n]=B_n$, so $|A_n|=|B_n|=s_n$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Take any proof of the fact that the number of recurrence relations that do not contain three consecutive $0$s is $s_n=s_{n-1}+s_{n-2}=s_{n-3}$ and replace every time you use the word or symbol $0$ and change it for $1$ and visce-versa.

You will have a proof that the number of recurrence relations that do not contain three consecutive $1$s is $s_n=s_{n-1}+s_{n-2}=s_{n-3}$.


You can also prove directly that the number of sequences that do not contain $3$ consecutive zeros is the same as the number of sequences that do not contain $3$ consecutive ones.

Define the inverse of a bit string as the string in which every character is the opposite. Notice that this operation is a bijection between strings with no $3$ consecutive zeros and string with no $3$ consecutive ones.

| cite | improve this answer | |
$\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.