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.
Best Answer
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.