direct proof of combination

Question

Prove that $(^{n}_{2}) = 1+2+3+...+(n-1)=\sum^{n-1}_{k=1}k$ for $n \ge 2$

After some time flipping through notes I think I should use the sum of the 1st n natural is $\sum^{n}_{k=1}k=\frac{n(n+1)}{2}$ this looks like it relates right into this if I could figure out how to adapt it to the first n-1 naturals

I thought to simply plug in n-1 for n but I am not sure if that would work, it isn't seem to give me anything useful when I tried to use it. $$\sum^{n-1}_{k=1}k=\frac{(n-1)(n)}{2}$$ Either I did it wrong, I'm not seeing the connection or I'm chasing a goose

since $(^n_2) = \frac{n(n-1)}{2}$ couldn't I simply state that and then say something like therefore it equals $\sum^{n-1}_{k=1}k$ since that also equals $\frac{n(n-1)}{2}$ ?

He said this one would be really easy when we found the trick and the sum of the 1st n naturals is something we did recently.

Answer 1

Proof 1 (Induction)

Base case: When $n=2$ $$\sum\limits_{k=1}^1 k = 1 = \frac{(2-1)\times2}{2}$$

Iterative case: Show $ \forall n : \displaystyle \sum\limits_{k=1}^{n-1} k = \frac{(n-1)n}2 \implies \sum\limits_{k=1}^{n} k = \frac{n(n+1)}{2}$.

$$\sum\limits_{k=1}^n k = n + \sum\limits_{k=1}^{n-1} k\\ \implies \sum\limits_{k=1}^{n} k = n + \frac{(n-1)n}{2} \\ \implies \sum\limits_{k=1}^{n} k = \frac{2n + n^2- n}{2} \\ \implies \sum\limits_{k=1}^{n} k = \frac{n(n+1)}{2}$$

The assumption holds for the base case and holds under iterative step for all $n$, thus by induction:$$\displaystyle \sum\limits_{k=1}^{n-1} k = \binom{n}{2} $$

---

Proof 2 (Direct)

Let $\displaystyle S_n = \sum_{k=1}^{n} k$

$\implies 2 S_n = 2 (1 + 2 + 3 + \ldots (n-1) + n)$

$\implies 2 S_n = (1 + 2 + 3 + \ldots (n-1) + n) + (n + (n-1) + \ldots + 3 + 2 + 1)$

$\implies 2 S_n = (1+n) + (2+(n-2)) + (3+(n-3)) + \ldots + (n-1 + 1) + (n+1)$

$\implies 2 S_n = n(n+1)$

$\displaystyle \implies \sum_{k=1}^n = \frac{n(n+1)}2$

$\displaystyle \therefore \sum_{k=1}^{n-1} = \frac{(n-1)n}{2} k$

---

Proof 3 Same but different

$\displaystyle 2 \sum_{k=1}^{n-1} k = \left(\sum_{k=1}^{n-1} k\right) + \left(\sum_{j=1}^{n-1} j\right)$

$\displaystyle 2 \sum_{k=1}^{n-1} k = \left(\sum_{k=1}^{n-1} k\right) + \left(\sum_{k=1}^{n-1} (n-k)\right)$

$\displaystyle 2 \sum_{k=1}^{n-1} k = \left(\sum_{k=1}^{n-1} (k+(n-k))\right)$

$\displaystyle 2 \sum_{k=1}^{n-1} k = \sum_{k=1}^{n-1} n$

$\displaystyle 2 \sum_{k=1}^{n-1} k = n(n-1)$

$\displaystyle \therefore \sum_{k=1}^{n-1} k = \frac{n(n-1)}2$

Answer 2

Awesome Proof :

Clearly, $\binom{n}{2}$ represents number of way of choosing $2$ things out of $n$.

Let us compute the answer using another method. Make following cases :

1. $1st$ item is included : Second item can be $2,3...n$. Hence, $n-1$ ways.
2. $2nd$ item is included : As in choosing $(1,2)$ and $(2,1)$ are same, and $(1,2)$ is already included in case $1$ we can choose $3,4...n-1$ Hence, n-2 ways.

We will make such cases till $n-1th$ item is to be included which will have $1$ case. All cases for $nth$ item have already been covered.

Hence, number of cases = $(n-1)+(n-2)+...1$=$RHS$

Another way of proving to $n(n-1)/2$ :

We can see that we can choose first object in $n$ ways and second object in $n-1$ ways... By fundamental principle of counting, number of ways = $n(n-1)$. But, we are $choosing$ where order does not matter, hence we divide by $2!$. Answer : $n(n-1)/2$

Answer 3

Using combinatorics, you could try to compute $(^{n}_{2})$ by logic. Assuming you know that $(^{n}_{2})$ means "how many different pairs can you get, when you have n persons?":

• The first person can be paired with the rest (n-1) persons.
• The first person can be paired with the rest (n-2) persons (everyone else except the first one, because this pair has already been computed)
• ...
• The n-1 person can be paired with just the last person.

The sum of these is $\sum^{n-1}_{k=1}k$