recurrence relation problem..

[xoxpe]

hi.. i got a problem from a book and i cant answer it..

he asked me to find a recurrence relation for the number of bit string of length n that contain 4 consecutive 0s... and the second question is for the number of ways to climb n stairs and the person climbing the stairs can take one or two stairs at a time...

 

can you help me? please explain to me... thank you very much...

[D H]

I'm willing to help, but you I am not willing to give you the answer. That is, you will have to show some work to start with and you will have to do most of the work on the problem. I will give you some help along the way.

 

First of all, do you know what a recurrence relation is? Explain it.

 

The second problem is a bit easier to comprehend, so make an initial stab at a solution for that problem. What information do you need to solve it?

 

Edited to add:

 

The first question is a bit ambiguous. Is the problem to find the number of bit strings of length n that contain exactly 4 consecutive zeros, or to find the number of bit strings of length n that contain at least 4 consecutive zeros? The answers are obviously quite different.

[Ramsey2879]

Edited to add:

 

The first question is a bit ambiguous. Is the problem to find the number of bit strings of length n that contain exactly 4 consecutive zeros, or to find the number of bit strings of length n that contain at least 4 consecutive zeros? The answers are obviously quite different.

I think it would be OK to work this out since this post has aged a bit and doing a someone's "homework" doesn't seem to apply anymore. Lets assume the string consists of only 0's and 1's ; that there must be at least a leading 1, and must contain at least one string of at least 4 consecutive zeros. Question: is this what is wanted-The number of strings of length N of this type?