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

2. ## Recursive

On problem 1:

A. If we have 2 rows and n columns (2xn board) and we put a domino vertically in the upper right corner, then we have the rest of the board equivalent to a 2x(n-1) board. If we put the domino in the corner horizontally, we have to put another horizontal one below it, leaving the rest of the board equivalent to a 2x(n-2) board. This should give you the recurrence relation.
B. Consider n=1 and n=2 cases
C. Use your formula (creating a table may be fastest).

--Kevin C.

3. ## Recursion

Problems 2-4:

2) Consider $g(k)=f(2^k)$. As $f(n)=f(\frac{n}{2})+1$ with $f(1)=1$ and $\frac{2^k}{2}=2^{k-1}$, you can find the recurrence relation for g(k) which is easily solvable, and use that to find solution for $f(2^k)=g(k)$

3) Notice that after the first round (of n/2 games) we have n/2 winners left. The rest of the tournament is then equivalent to a tournament of n/2 players. Thus we can find a recurrence relation for the number of rounds f(n) in terms of f(n/2).

4) Use 2 and 3

I'm not sure on 5, because of the question of what f(n) is for odd n.

--Kevin C.

4. Originally Posted by TwistedOne151
On problem 1:

A. If we have 2 rows and n columns (2xn board) and we put a domino vertically in the upper right corner, then we have the rest of the board equivalent to a 2x(n-1) board. If we put the domino in the corner horizontally, we have to put another horizontal one below it, leaving the rest of the board equivalent to a 2x(n-2) board. This should give you the recurrence relation.
B. Consider n=1 and n=2 cases
C. Use your formula (creating a table may be fastest).

--Kevin C.
Sorry, but I cannot understand...can u explain more?

5. ## A diagram

I'll try to draw a picture of sorts:

Let us call the number of ways of filling a 2xn board with dominoes F(n)

Consider a 2xn board (here 2x8):

_ _ _ _ _ _ _ _
| | | | | | | | |
_ _ _ _ _ _ _ _
| | | | | | | | |
_ _ _ _ _ _ _ _

In the upper right corner we could put a domino vertically

_ _ _ _ _ _ _ _
| | | | | | | |*|
_ _ _ _ _ _ _ _
| | | | | | | |*|
_ _ _ _ _ _ _ _

Leaving a space equal to a 2x(n-1) board (here 2X7), so there are F(n-1) ways to fill the board with a domino on the right like this.

We could instead put a domino horizontally in the corner:

_ _ _ _ _ _ _ _
| | | | | | |*|*|
_ _ _ _ _ _ _ _
| | | | | | | | |
_ _ _ _ _ _ _ _

We would then need to put another below this one (marked by @)

_ _ _ _ _ _ _ _
| | | | | | |*|*|
_ _ _ _ _ _ _ _
| | | | | | |@|@|
_ _ _ _ _ _ _ _

Leaving a 2x(n-2) space, so we have F(n-2) ways to fill the board with a pair of dominoes on the right like this.

Thus the total number of ways to fill a 2xn board is F(n)=F(n-1)+F(n-2)
And we have our recurrence relation for part (a).

--Kevin C.

6. Thank You for the 1 - 4 problems

7. Some one please help me on number 5. Do I need to do the proof by induction? If yes, I don't understand how. Is there any other way to do it?