(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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.

2. Relevant equations

(it's given above, we just have to prove it combinatorially)

3. 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Combinatorics fun

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**