- #1
silvermane
Gold Member
- 117
- 0
Homework Statement
1. Recall that Fn denotes the number of perfect coverings of a 2–by–n chessboard with dominoes.
Use combinatorial reasoning to show that
F2n = Sum [of k=0 to k=n] of (nCk) Fk
for all integers n ≥ 0. Make sure to describeFk in the context of perfect coverings of a 2–by–2n
chessboard.
Homework Equations
(it's given above, we just have to prove it combinatorially)
The Attempt at a Solution
The idea here is to count perfect coverings of a 2–by–2n chessboard based on the number of vertical dominoes that appear in the first n dominoes in the top row of the board from left to right, but I'm having trouble applying it, because there are certain restraints in how the vertical dominoes may be placed.
Last edited: