Binary strings and recurrence relations [closed]

So the problem is: How many binary strings of length n contains 111? Give a recurrence relation Tn, where Tn is the number of binary strings of length n that contains 111.

How could we possibly figure this out if there are an infinite number of sequences that could be generated? Could someone please solve this problem and explain what is going on at each step? Thank you so much!

closed as unclear what you're asking by Daniel W. Farlow, user147263, Chappers, HK Lee, BungoApr 14 '15 at 4:20

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

One intuitive approach to this problem is to let $B_n$ be the number of strings of length $n$ that contain 111, and let $A_{n,k}$ be the number of strings of length $n$ that do NOT contain 111 which end with $k$ 1's ($k=0,1,2$). Then obviously,

$$B_n = 2*B_{n-1} + A_{n-1,2}$$ $$A_{n,0} = A_{n-1,0} + A_{n-1,1} + A_{n-1,2}$$ $$A_{n,1} = A_{n-1,0}$$ $$A_{n,2} = A_{n-1,1}$$

You can reduce this to a single recurrence in $B$ by noting that $B_n + A_{n,0} + A_{n,1} + A_{n,2} = 2^n$.