1
$\begingroup$

I was trying to prove the identity $$\sum_{k=1}^n {n \choose k} f_{k-1} = f_{2n-1}$$ for $n\geq0$ combinatorially. Here,$f_{n}$ means the number of ways to tile an $n$-board(A board with n-cells) using identical square tiles and identical dominoes. Here is an illustartion(The very black ones are dominoes),enter image description here

Here, The number of ways to tile a $2n-1$ board is $f_{2n-1}$. The other way is:

Since, there are $2n-1$ cells in the board, $n$ of them must be in odd places. Let us put a restriction on the number of square tiles in the $n$ odd-placed cells.There must be at least one square tile covering at least one of the $n$ cells at odd places.
Now, given that I will cover only $k$ of the $n$ odd placed cells with square tiles, I can make a choice of those $k$ square tiles in ${n\choose k}$ ways. Now, the remaining of the $n-k$ odd cells have to be covered by dominoes. Thus, these dominoes will cover $2(n-k)$ cells. Thus, remaining number of cells are $$2n-1-(k+2n-2k)=k-1$$ None of these cells will be consecutive since if they were any one of them would be odd(But we have covered all odd cells). Thus, they can be covered only by square tiles,i.e, only one way. Thus, we obtain the equation(contrary to the identity) $$\sum_{k=1}^n {n \choose k} = f_{2n-1}$$ I am not able to figure out where I made a mistake. Please, help me identify it.

$\endgroup$
1
  • 1
    $\begingroup$ It will be patched in the next update $\endgroup$
    – DatBoi
    May 29, 2021 at 14:21

2 Answers 2

1
$\begingroup$

I guess the number of ways to distribute the dominoes among the $n-k$ cells have been under-counted. Let us consider the remaining $k-1$ cells carefully. None of these cells can be at odd places. Thus, they must be at even places.Thus, they must be proceeded and succeeded by an odd cell which is covered by a domino. Thus, there are $k-1$ such dominoes. Now, these dominoes too cover some even cells. Additional ways are created by choosing which domino has to be slided to make the covered even cell naked. This can be done in $f_{k-1}$ ways since you can just create an analogy by assigning every domino that has to be slided as a 2 and the remaining of the $k-1$ dominoes as 1. This corrects your identity.

$\endgroup$
1
  • $\begingroup$ I fear possible overlapping of dominoes. But there is another way to reach the same correction by choosing which $k-1$ empty even cells have to be covered by sliding adjacent dominoes. $\endgroup$ May 29, 2021 at 13:53
1
$\begingroup$

This is Identity 6 in Proofs That Really Count: The Art of Combinatorial Proof, where the proof conditions on the number $k$ of squares that appear among the first $n$ tiles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.