Thread: New to recursion and have no idea how to solve this problem

For each integer n >= 0, let a(n) be the number of bit strings of length n that do not contain the pattern 101.

a.) Show that a(k) = a(k-1) + a(k-3) + a(k-4) + ... + a(0) + 2, for all integers k>= 3.

b.) Use the result of part (a) to show that if k >= 3, then a(k) = 2a(k-1) - a(k-2) + a(k-3)

**everything in parenthesis is treated as a subscript

This question is totally unlike anything else from this section of the book. I really have no idea where to even start. Part a almost looks like I could do induction but I don't know if that would be correct. The only thing I've done so far is I wrote out the first couple of bit length (don't even know if I'm supposed to do this) and came up with:

Length 0: ∊
Length 1: 0, 1
Length 2: 11, 10, 01, 00
Length 3: 111, 110, 100, 000, 001, 011, 010 (101 is excluded, obviously).

I also understand that a recursive formula I can write is

a(k) = 2a(k-1) + 2a(k-2) + a(k-3) (I think, not sure if this is correct)

are you sure you have the formula in part a) correct?

a3 = 7, but a2 + a0 + 2 = 6.

Induction was my first instinct, but I think regardless you will have to relate the various a(i). To facilitate that, each a(i) has possible bit sequences, of which we'll have to exclude a certain number that include the 101 pattern. You already exposed this in your first four cases: length 0 is the empty bit string, length 1 is (0, 1), length 2 is (11, 10, 01, 00), etc. My intuition is that there is something to be explored when we, say, add a(k-3) + a(k-4), and the like when we think of it in terms of less the 101 bit sequences. I assume the 101 pattern showing up anywhere in a string (e.g., 100101011 would be excluded) rules it out. So, in a string of length k, how many of the will be excluded? Ultimately, that is what I think this algorithm is expressing by putting it in terms of how many are excluded from lesser length bit strings. Therefore, to facilitate the solution, we will need to know how many are excluded along the way, and the reason we're concerned with k greater than 2 is because, as you show, exclusion only begins at length 3 sequences.

I believe the formula is part a is correct. I have uploaded a picture of the actual problem:

http://i.imgur.com/MDsoz.jpg

One thing you might want to try is write the expression for a(k-1) in the form of a(k), and so on for the rest of the a(i)'s. Then by substituting the values for each a(i) you might have something more manageable, maybe. Just something I thought you might want to explore.