0
$\begingroup$

As the title states, I am tasked with finding finding a recurrence relation according to the specific constraints. I have a start to the problem, but I'm really having trouble identifying the pattern for the recurrence relation. My first step was to go through the first few cases to see if a pattern emerged. Here is what I found: enter image description here

Here's where I got a bit stuck. I am currently trying to look for patterns in terms of taking the previous terms and adding a combination of 1's and 0's to them. I found the terms for length 5 by taking the previous term (length 4) and adding a 1 to the front of all the terms, then adding a 0 to the front of all the terms, then a 1 to the back, then a 0 to the back. I ended up with a few duplicates that I then had to remove. Any help towards the next steps I need to take or hints would be greatly appreciated!

$\endgroup$
  • 1
    $\begingroup$ You should have $a_5=8$. You seem to have double counted 01110 $\endgroup$ – Henry May 3 at 22:05
1
$\begingroup$

Hint:

If you let

  • $a_n$ be the number of the number of binary strings of length $n$ which have $3$ consecutive $1$s

  • $b_n$ be the number of the number of binary strings of length $n$ which do not have $3$ consecutive $1$s but which end with exactly two $1$s

  • $c_n$ be the number of the number of binary strings of length $n$ which do not have $3$ consecutive $1$s but which end with exactly one $1$

  • $d_n$ be the number of the number of binary strings of length $n$ which do not have $3$ consecutive $1$s but which end with exactly zero $1$s

and consider adding a $1$ or $0$ to the end of shorter strings, then you can say $$a_{n}=2a_{n-1}+b_{n-1} \\ b_{n}=c_{n-1} \\ c_{n}=d_{n-1} \\ d_{n}=d_{n-1}+c_{n-1}+b_{n-1}$$

which you can then turn into $$a_{n}=2a_{n-1}+d_{n-3} \\ d_{n}=d_{n-1}+d_{n-2}+d_{n-3}$$ and if you are brave then into something like $$a_{n}=3a_{n-1}-a_{n-2}-a_{n-3}-2a_{n-4}$$

You know the starting conditions up to $a_4$, so could find a generating function solution if not a simple closed form. Incidentally, $d_n$ seems to be related to the so-called Tribonacci numbers

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