Question

What is meant by a combinatorial proof of an identity? How is such a proof different from an algebraic one?

Short answer

A proof by counting is the combinatorial proof of an identity. This proof is different for an algebraic proof as it uses two different interpretations of the dame numerical quantity.

Step-by-step solution

Concept Introduction          

The word combinatorial proof is frequently used in mathematics to refer to one of two types of mathematical proof:

• A double-counting proof. The different formulations of a combinatorial identity are obtained by counting the number of elements of a carefully chosen set in two different ways. Because such expressions count the identical items, they must be equal to one another, establishing the identity.
• This is a bijective proof. A bijection, or one-to-one connection, between two sets demonstrates that they have the same number of members.

Combinatorial Proof

A combinatorial interpretation of a numerical quantity is a set of combinatorial objects that is counted by the quantity.

A combinatorial proof of an identity is a proof by counting. If the identity is X=Y , finding a set of objects that can be interpreted as a combinatorial interpretation of both X and Y proves that the numerical quantities on both sides of the equation are actually equal.

The main difference with an algebraic proof is the two different (combinatorial) interpretations of the same numerical quantity. Often it leads to getting rid of the cumbersome and tedious nature of an algebraic proof.

Therefore, a combinatorial proof of an identity is proof by counting. This proof is different as it has two interpretations for a single quantity.