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!