How can I prove $\Sigma ^{n-1} _{i=1} i = (^n _2)$? (n≥2)

Question

// Through induction or combinatorial explanation, it doesn't matter.

what I've done so far (through induction):

Base: $\Sigma ^{2-1} _{i=1} i = 1 = (^n _2)$
Step: $\Sigma ^{n} _{i=1} i = (^n _2) + n = ... = (^{n+1} _2)$

I'll be happy to get some help :)

Answer 1

That $\sum_{i=1}^{n}i = \frac{n(n+1)}{2}$ can be proved by induction.

The case $k=1$ is trivial and assume it also holds for $k=n-1$. But then $\sum_{i=1}^{n}i = \frac{(n-1)n}{2} + n = \frac{n(n-1) + 2n}{2} = \frac{n(n+1)}{2}$. Hence $\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2}$.

But by definition ${n \choose 2} = \frac{n!}{2!(n-2)!}=\frac{n(n-1)(n-2)!}{2(n-2)!} = \frac{n(n-1)}{2}$.

Therefore we can conclude that $\sum_{i=1}^{n-1}i={n \choose 2}$

Answer 2

Here’s a combinatorial proof: To choose two out of $n$ elements (in $\binom n2$ ways), first choose the $(i+1)$-th element and then choose one of the $i$ elements preceding it.