<s>[INST] sum of binomial coefficients expansion to prove equation I want to prove that
$$
\sum_{i=1}^{n}{\binom{i}{2}} = \binom{n+1}{3}
$$
I already expanded
$$
\binom{n+1}{3}
$$
to
$$
\binom{n+1}{3} = \frac{1}{6} * (n+1) *n*(n-1)
$$
and I know that the following equation must be right
$$
\sum_{i=1}^{n}{\binom{i}{2}} = \frac{1}{6} * (n+1) *n*(n-1)
$$
but I do not get the expansion right, I tried starting with writing the sum explicit
$$
\binom{1}{2}+\binom{2}{2}+\ldots+\binom{n-1}{2}+\binom{n}{2}
$$
since 1 over 2 is zero it can be shortened to
$$
\sum_{i=2}^{n}{\binom{i}{2}} = \binom{2}{2}+\ldots+\binom{n-1}{2}+\binom{n}{2}
$$
then I expanded the binomial coefficients to the corresponding factorial form
$$
\binom{n}{k} = \frac{n!}{k! * (n-k)!}
$$
but I do not get it right, could someone please help me?
 [/INST] $\begin{array}\\
\binom{n+1}{3}-\binom{n}{3}
&=\dfrac{(n+1)n(n-1)}{6}-\dfrac{n(n-1)(n-2)}{6}\\
&=\dfrac{n(n-1)((n+1)-(n-2))}{6}\\
&=\dfrac{3n(n-1)}{6}\\
&=\dfrac{n(n-1)}{2}\\
&=\binom{n}{2}\\
\end{array}
$
Therefore
$\sum_{i=1}^{n}\binom{i}{2}
=\sum_{i=1}^{n}(\binom{i+1}{3}-\binom{i}{3})
=\binom{n+1}{3}
$.
Note that
$\binom{n}{m} = 0$
for $m > n$.
In general,
since
$\binom{n}{m}
=\dfrac{\prod_{k=0}^{m-1}(n-k)}{m!}
$,
$\begin{array}\\
\binom{n+1}{m}-\binom{n}{m}
&=\dfrac{\prod_{k=0}^{m-1}(n+1-k)}{m!}-\dfrac{\prod_{k=0}^{m-1}(n-k)}{m!}\\
&=\dfrac{\prod_{k=-1}^{m-2}(n-k)}{m!}-\dfrac{\prod_{k=0}^{m-1}(n-k)}{m!}\\
&=\dfrac{(n+1)\prod_{k=0}^{m-2}(n-k)-(n-m+1)\prod_{k=0}^{m-2}(n-k)}{m!}\\
&=\dfrac{((n+1)-(n-m+1))\prod_{k=0}^{m-2}(n-k)}{m!}\\
&=\dfrac{m\prod_{k=0}^{m-2}(n-k)}{m!}\\
&=\dfrac{\prod_{k=0}^{m-2}(n-k)}{(m-1)!}\\
&=\binom{n}{m-1}\\
\end{array}
$
so that
$\sum_{i=1}^{n}\binom{i}{m-1}
=\sum_{i=1}^{n}(\binom{i+1}{m}-\binom{i}{m})
=\binom{n+1}{m}
$.
</s>