combinatorics - 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}$.

Answer

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:

1. 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 of type A is mapped to $(i,j)$.
   
   
   • A pair $i of type B with $j \neq n+1$ is mapped to $(j,i)$.
   
   
   • A pair $i 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 of type A.


• A pair $(i,j)$ with $i > j$ is mapped to the pair $j of type B.


• A pair $(i,i)$ is mapped to the pair $i of type B.

The second example is of a somewhat different kind.

2. 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.)