Show that: $\binom{n}{3}= \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2}+ \ldots + \binom{n-1}{2}$

Question

This question is from Book of Proof by Richard H. Hammack. This is exercise number 13 of chapter 3 section 6.

This is exercise I think is related to Pascal identity, but I'm struggling to understand it.

Answer 1

By using the Pascal's identity and the telescoping summation we obtain: $$\sum_{k=2}^{n-1}\binom{k}{2}=\sum_{k=2}^{n-1}\left(\binom{k+1}{3}-\binom{k}{3}\right)=\binom{n}{3}-\binom{2}{3}=\binom{n}{3}.$$

Answer 2

There is a more generalised form of that (we assume that $\binom{a}{b}:=0$ is $b>a$)

Identity: $$\sum_{t=k}^{n}\binom{t}{k}=\binom{n+1}{k+1}\quad\text{for $n\geq k$}$$

Proof using telescoping summation method: $$\sum_{t=k}^{n}\binom{t}{k}=\sum_{t=k}^{n}\left\{\binom{t+1}{k+1}-\binom{t}{k+1}\right\}\\=\sum_{t=k}^{n}\binom{t+1}{k+1}-\sum_{t=k}^{n}\binom{t}{k+1}\\=\sum_{t=k+1}^{n+1}\binom{t+1}{k+1}-\sum_{t=k}^{n}\binom{t}{k}\\=\binom{n+1}{k+1}-\underbrace{\binom{k}{k+1}}_{\text{$0$ by definition}}\\=\binom{n+1}{k+1}$$

This identity is known as Hockey-stick identity.

Answer 3

$$\sum _{k=2}^{n-1} \binom{k}{2}=\binom{n}{3}\tag{1}$$ By induction

It is trivially true for $n = 3$

Now suppose that $(1)$ holds for $n$ and let's prove it for $(n+1)$

$$\sum _{k=2}^{n} \binom{k}{2}=\sum _{k=2}^{n-1} \binom{k}{2}+\binom{n}{2}=\binom{n}{3}+\binom{n}{2}=\binom{n+1}{3}$$ which proves that $(1)$ holds for any $n$.