Combinatorial Proof vs. Algebraic Proof
I'm learning combinatorics and need a little help differentiating between a combinatorial proof and an algebraic proof. Here is an example I came across:
Prove the following two formulas by combinatorial means and algebraic manipulation:
(i) For all $k$, $n \in \mathbb{N}$ with $k \leq n$.
${n \choose 2} + {n+1 \choose 2} = n^{2}$.
(ii) For all $k$, $n \in \mathbb{N}$ with $k \leq n$.
$k{n \choose k} = n{n-1 \choose k-1}$.
$\endgroup$ 41 Answer
$\begingroup$Algebraic manipulations consist of calculation using explicit formulas. In your two examples, we have:$$ \binom{n}{2} + \binom{n+1}{2} = \frac{n(n-1) + (n+1)n}{2} = n^2, $$and$$ k\binom{n}{k} = k\frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n\frac{(n-1)!}{(k-1)!(n-k)!} = n\binom{n-1}{k-1}. $$
Combinatorial proofs represent both sides of the equation as counting certain objects, and then exhibit a bijection between the two sides. In your two examples, we have:
The left-hand side counts the size of two sets of ordered pairs: pairs of integers in $[n]$ (type A), and pairs of integers in $[n+1]$ (type B). The right-hand side counts the size of the set $[n]^2$. We exhibit a bijection between them in the following way:
- A pair $i<j$ of type A is mapped to $(i,j)$.
- A pair $i<j$ of type B with $j \neq n+1$ is mapped to $(j,i)$.
- A pair $i<n+1$ of type B is mapped to $(i,i)$.
We can check that this is a bijection by giving the inverse mapping:
- A pair $(i,j)$ with $i < j$ is mapped to the pair $i<j$ of type A.
- A pair $(i,j)$ with $i > j$ is mapped to the pair $j<i$ of type B.
- A pair $(i,i)$ is mapped to the pair $i<n+1$ of type B.
The second example is of a somewhat different kind.
- The left-hand side counts the number of $k$-element subsets of $[n]$ with a distinguished element. The right-hand side offers another way of counting the same set: first choose the distinguished element, and then choose the remaining $k-1$ elements out of the remaining $n-1$ elements. This is an example of double counting.
Another kind of proof which sometimes appears is probabilistic proofs, which are really a variant of combinatorial proofs. As an example,$$ \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} = 1 $$expresses the fact that if we toss $n$ many $p$-biased coins, then $k$ of them will turn up heads for exactly one value of $k$. (While this works only for $0 \leq p \leq 1$, the general result follows since two degree $n$ polynomials are equal whenever they agree on more than $n$ points.)
$\endgroup$
