Jump to content

recurrence relation problem..


xoxpe

Recommended Posts

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

  • 1 month later...
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?

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.