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).
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)
