1

A computer system considers a bit string a valid codeword if and only if it does not contain $3$ consecutive zeroes. Thus $010010$ is a valid codeword of length $6$ while $011000$ is not. Let $a_n$ be the number of valid codewords of length $n$.

The problem is to find $a_1, a_2, a_3$.

I have found $a_1 = 2$ as $O$ and $1$ are the only possibilities in binary bit strings. Our lecturer has told us that $a_2 = 4$ and $a_3 = 7$, but I am not able to work out how he got those. I have looked around and haven't been able to break down the source of $4$ and $7$ ... Could someone give me a hint? Thank you in advance.

kjetil b halvorsen
  • 6,625
user3025494
  • 17
  • 2 and 3 are so tiny that we can simply list all possible bit strings of that length and check which ones are valid. Why don't you do that and for $a_4$ as well? And you should learn LaTeX because we use that on Math SE. For example use "$$$a_n$$$" in your post to get subscript. – user21820 May 13 '14 at 14:57
  • An edit was made to your post making $a_1=4$ and $a_2=7$ where it should be $a_2=4$ and $a_3=7$. Unfortunately I can't edit it back to the correct version since the change is under 6 characters. – RandomUser May 13 '14 at 15:10
  • 1
    $(a_1,a_2,\ldots) = (2,4,7,13,24,44,81,149,274,504,\ldots)$. $a_n = t_{n-3}$ where $t_{n}$ is the Tribonacci numbers (OEIS A000073) – achille hui May 13 '14 at 15:34

3 Answers3

2

This has been answered, but to address the general case for $a_n$ I will add the following analysis.

Let $1_n$ denote the number of valid codewords of length $n$ ending with a $1$. Similarly, let $0_n$ denote the number of valid codewords ending with only one zero and $00_n$ those ending with two consecutive zeros. Then we have $$ a_n=1_n+0_n+00_n $$ and $$ \begin{align} 1_n&=a_{n-1}\\ 0_n&=1_{n-1}=a_{n-2}\\ 00_n&=0_{n-1}=a_{n-3} \end{align} $$ so combining these informations we have $$ a_n=a_{n-1}+a_{n-2}+a_{n-3} $$ If we set $a_{-1}=0_1=0$ and $a_0=1_1=1$ and $a_1=2$ we then get $$ \begin{align} a_{-1}&=1\\ a_0&=1\\ a_1&=2\\ a_2&=2+1+1=4\\ a_3&=4+2+1=7\\ a_4&=7+4+2=13\\ &...\\ &\text{etc.} \end{align} $$

String
  • 18,395
0

The total amount of possible codewords with $n$ bits, valid or not, is $2^n$. $3$ consecutive zeroes are invalid. $a_2$ doesn't have enough digits to make that happen, so every possibility must be valid.$$2^2=4$$

For $3$ digits the only invalid codeword is $000$. You need $3$ zeroes to be invalid, and your length is $3$, so they must all be $0$ to be invalid. That eliminates one out of your set of all possible codewords of length $3$. $$2^3-1=7$$

RandomUser
  • 1,275
0

There are $2^2=4$ possible 2-bit strings.
They are all valid because no 2-bit string can contain 3 consecutive 0's.
So, $a_2=4$

There are $2^3=8$ possible 3-bit strings.
Only 1 of the possible strings has 3 zeros, namely '000'.
So, $a_3=2^3-1=7$

user137481
  • 2,605