1)

(a) Find a recurrence relation for the number of ways to completely cover a 2 x n checkerboard with 1 x 2 dominoes. [Hint: Consider separately the coverings where the position in the top right corner of the checkerboard is covered by a domino positioned horizontally and where it is covered by a domino positioned vertically.]

(b) What are the initial conditions for the recurrence relation in part (a)?

(c) How many ways are there to completely cover a 2 x 17 checkerboard with 1 x 2 dominoes?

2) Find f(n) when n = 2^k, where f satisfies the recurrence relation f(n) = f(n/2) + 1 with f(1)=1.

3) Suppose that there are n = 2^k teams in an elimination tournament, where there are n/2 games in the first round, with then n/2 = 2^(k-1) winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.

4) Solve the recurrence relation for the number of rounds in the tournament described in Exercise 3.

5) Show that f_(0) – f_(1) + f_(2) – … – f_(2n-1) + f_(2n) = f_(2n-1) -1 when n is a positive integer.

Word Doc attached because I don't know how to format Superscript and subscript in this forum. Please refer to it.

Thank You

Anu