Hello, narbe!
Crank out the new few terms . . .5) Find the solution to the following recurrence relation and initial condition:
. .
. .
Got it?
1)
Find a recurrence relation for the number of bit string of length n that contain three consecutive 0's
What are the initial conditions? how many bit strings of length 7 contain three consecutive 0's?
2)
Give the recursive algorithm for finding the minimum of a finite set of
integers.
3)
Find the solution to the following recurrence relation and initial
condition:
xn+2 = 4xn; n = 0, 1, 2, ... x0 = 2, x1 = 1.
4)
Give the recursive algorithm for finding the sum of the first n odd
positive integers.
5)
Find the solution to the following recurrence relation and initial
condition:
xn+2 = 2xn+1 + 3xn; n = 0, 1, 2, ... x0 = 1, x1 = -1.
Thanks in advance
I think it's easiest to count the number of strings of length n that do not contain three consecutive zeros. Call this number .
We can get a string of length n+1 without three consecutive zeros in three ways: (1) take such a string of length n and add a 1 at the end, (2) take such a string of length n-1 and add 10 at the end, (3) take such a string of length n-2 and add 100 at the end. Therefore .
Now let denote the number of strings of length n that do contain three consecutive zeros. There are altogether strings of length n, so . It easily follows from the relation for the y's that . The initial conditions are . From there, you can use the recurrence relation to work your way up to 7. (I get the answer , but don't rely on my arithmetic.)
This is a second order difference equation with a constant coefficient, there is a very simple way for this equation.
Such equations have solution of the type for , where are arbitrary constants.
Just substitute this value into the solution and solve and , then use these values together with the initial conditions to find the desired solution.
However, here, I would like to show you a different solution way for this equation.
First set, for , then from the equation, we get
or simply for .
It is easy to solve this equation and we get for all , where is an arbitrary constant.
Since , we see that .
Thus, we have is a solution of the equation.
Next, set for and solve or simply for with .
Finally, sum these results.