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.
