0

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!

Drew Pesall
  • 167

1 Answers1

1

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

Henry
  • 157,058