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