# Thread: Proof Help!!

1. ## Proof Help!!

Prove that:

"The summation" from k=2 to n of (k choose 2) = (n+1 choose 3). Let n be a natural number.

2. Hello, jzellt!

It helps if we know a few summation formulas:

. . $\displaystyle \sum^n_{k=1} k \;=\;\frac{k(k+1)}{2}\qquad\quad \sum^n_{k=1}k^2 \;=\;\frac{n(n+1)(2n+1)}{6}$

Prove that: .$\displaystyle \sum^n_{k=2}{k\choose2} \;=\;{n+1\choose3}$

$\displaystyle \sum^n_{k=2}{k\choose2} \;=\;{2\choose2} + {3\choose2} + {4\choose2} + {5\choose2} + \hdots + {n\choose2}$

. . . . . .$\displaystyle = \;1 + 3 + 6 + 10 + \hdots + \frac{n(n-1)}{2}$

This is the sum of the first $\displaystyle n-1$ triangular numbers.

We have: .$\displaystyle \sum^{n-1}_{k=1}\frac{k(k+1)}{2} \;\;=\;\;\frac{1}{2}\bigg[\sum^{n-1}_{k=1}k^2 + \sum^{n-1}_{k=1} k\bigg] \;\;=\;\;\frac{1}{2}\bigg[\frac{n(n-1)n(2n-1)}{6} + \frac{n(n-1)}{2}\bigg]$

Factor: . $\displaystyle \frac{n(n-1)}{12}(2n-1 + 3) \;\;=\;\;\frac{n(n-1)}{12}(2n+2) \;\;=\;\;\frac{n(n-1)}{12}\cdot2(n+1)$

And we have: . $\displaystyle \frac{(n+1)n(n-1)}{3!}\quad\hdots\quad\text{which equals: }\:{n+1\choose3}$