I need some help writing the recurrence relation for this problem, or problem 30, since they are very similar. I've worked out some solutions and this is what I've got:

a1 = 0
a2 = 0
a3 = 1
a4 = 1 + 1 = 2
a5 = 2 + 1 + 2 = 5
a6 = 4 + 2 + 2 + 4 = 12
a7 = 8 + 4 + 4 + 4 + 8 = 28

So, from here I can't find the sequence that gives me those sums. I believe what's above is right, but if it isn't or there is a better way to look at it, let me know. Thanks for the help. --Aoser 17:09, 15 October 2008 (UTC)


I'm not sure if I'm correct, but I arrived at different values of strings with consecutive 0's of length (n). granted I don't read the problem as having "ONLY" 3 consecutive 0's so strings with more then 3 consecutive 0's are also counted (but only once){0000 and 0000 are the same and only counted once}.
a1 = 0
a2 = 0
a3 = 1 {000}
a4 = 1 + 2 = 3 {0001, 0000, 1000}
a5 = 3 + 4 = 7 {00011, 00010, 00001, 00000, 10001, 10000, 11000 }
a6 = 7 + 8 = 15 {000111, 000110, 000101, 000100, 000011, 000010, 000001, 000000, 100011, 100010, 100001, 100000, 110001, 110000, 111000 }
this is simplified to a(n) = 2*a(n-1)+1, but I'm unsure if this is correct, or why. --mnoah 20:23, 15 October 2008 (UTC)


In your solution, for example, a5 is not 7, but 8. You don't count "01000". And so on. The initial conditions were found correctly: a1=0, a2=0, a3=1. To construct the recurrence relation, here is a hint: an = # of bit strings starting from "1" + # of bit strings starting from "01" + # of bit strings starting from "001" + # of bit strings starting from "000". Hope it helps. --Asuleime 20:53, 15 October 2008 (UTC)


I considered strings of lenght n to which you can add a 0 or a 1 to make it of lenght n+1; then I considered the strings of lenght n which do not contain 3 consecutive 0's, fixed two 0's at the end of the strings, and added one 0 to make it of lenght n+1. --rtabchou


I found Asuleime's example to be helpful. Mainly you need to consider the number of bit strings which satisfy the condition at each recursion until you reach a point where all the bit strings of that type satisfies to condition. --ysuo 15:23, 16 October 2008 (UTC)


I did about what rtabchou did. There is an example in the book that shows how to find all the strings that DON'T have a string of 3 zeroes in it. Find that then find the converse by subtracting from the total number of ways possible...MUCH easier, although it may not seem that way on the outside.

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood