Here’s some random combinatorial identities.

Theorem 1For any and ,

*Proof:* For a computational proof,

For a combinatorial proof, the LHS is the number of -element subsets of and the RHS is the number of -element subsets of plus the number of -element subsets of . Since each -element subset of either has elements or elements of , the two quantities are equal.

Theorem 2For any ,

*Proof:* For a computational proof, note that

and if the statement holds for some then

For a combinatorial proof, the LHS is the sum of the number of -element subsets of for and the RHS is the number of subsets of . Since each subset of has exactly one of elements, the two quantities are equal.

Theorem 3For any ,

*Proof:* We compute:

Theorem 4For any and ,

*Proof:* Since

we have