Combinatorial proofs

Prove the following using combinational proofs (i.e not using the formulas)

C(n, k) = C(n - 1, k) + C(n - 1, k - 1) C(n, k) = C(n - 1, k) + C(n - 1, k - 1)

C(n, k) = C(n, n - k).

C(n, r)C(r, k) = C(n, k)C(n-k, r-k)

 k·C(n, k) = n·C(n - 1, k - 1)

Dominoes and Chess Board Problem

Consider a chess board with two of the diagonally opposite corners removed. Is it possible to cover the board with pieces of domino whose size is exactly two board squares?

Solution

No, it's not possible. Two diagonally opposite squares on a chess board are of the same color. Therefore, when these are removed, the number of squares of one color exceeds by 2 the number of squares of another color. However, every piece of domino covers exactly two squares and these are of different colors. Every placement of domino pieces establishes a 1-1correspondence between the set of white squares and the set of black squares. If the two sets have different number of elements, then, by the Pigeonhole Principle, no 1-1 correspondence between the two sets is possible.