Combinatorial proof (not by induction): $1 + 2 + 3 +...+ n = {n+1\choose 2}$

Question

Provide a combinatorial proof (not by induction) for

$1 + 2 + 3 +...+ n = {n+1\choose 2}$

I am just learning combinatorial proofs and this is how I attempted to provide the proof. Please let me know how to improve the proof and if I got it really wrong what the right answer is.

Proof

Consider the Question: How many ways are there to pick two players from a team of $n+1$ players?

RHS: There are $n+1 \choose 2$ ways to pick two players

LHS:

There are $1 \choose 0$ ways to pick $1$ player or

there are $2 \choose 1$ ways to pick $2$ players or

there are $3 \choose 2$ ways to pick $3$ players or...

there are $n+1 \choose n$ ways to pick $n$ players

So, ${1 \choose 0} + {2 \choose 1} + {3 \choose 2} + ... + {n+1 \choose n}$, which is the same as $1 + 2 + 3 +...+ n$.

Since, the RHS and LHS are both correct, so they must be equal.

Answer 1

As Austin Mohr pointed out in the comments, you counted the number of ways of picking $2$ players on your RHS and the number of ways of choosing $k$ players, $1 \leq k \leq n$, on the LHS. Therefore, your proof is incorrect.

Strategy: Count the number of two-element subsets of the set $\{0, 1, 2, 3, \ldots, n\}$ in two different ways.

How many such subsets are there?

For the LHS, consider the number of two-element subsets with larger element $k$, $1 \leq k \leq n$. Note that the number of such subsets is equal to the number of ways of choosing the smaller element.

Answer 2

Often, the trick to combinatorial proofs is to figure out a clever way to partition a set. You are correct that $\binom{n+1}{2}$ counts the number of two-person teams that you can build from $n+1$ available players. Call the collection of all these teams $T$.

Suppose the players are numbered from $1$ to $n+1$. I'll partition $T$ into disjoint subcollections $T_i$ for $1 \leq i \leq n$. For each $i$, the collection $T_i$ will contain all two-person teams whose least numbered player is $i$. These subcollections partition $T$ (though you may want to argue for this).

How many teams belong to $T_i$? Since the least numbered player is $i$, I have $n + 1 - i$ possible partners for player $i$. Thus, $$ |T| = |T_1| + |T_2| + \cdots + |T_n| = n + (n-1) + \cdots + 1, $$ which gives you the desired equality.

Answer 3

Consider the $2$ element subsets of $A=\{1, \dotsc, n+1\}$ and classify the subsets based on their minimum element. For example there are $n$ two-element subsets of $A$ with $1$ as the minimum, $n-1$ two-element subsets of $A$ with $2$ as the minimum and so on.