Proof $n \geq 3\hspace{0.5cm} \sum\limits_{k=1}^{n-2}{n-k\choose 2}={n\choose 3}$ How do you prove this expression trough mathematical induction ? It just ends up as a messy string of expressions when I try to solve it.
$n \geq 3\hspace{0.5cm} \sum\limits_{k=1}^{n-2}{n-k\choose 2}={n\choose 3}$
 A: HINT: observe that $$\sum_{k=1}^{n-2}\binom{n-k}2=\sum_{k=2}^{n-1}\binom{k}2=\frac12\sum_{k=1}^{n-1}k(k-1)$$
and also observe that $\binom{n}3=\frac{n(n-1)(n-2)}6$. This will make easier to apply induction.
A: *

*a ) it is true for $n=3$
$$
n = 3\quad  \Rightarrow \quad \sum\limits_{k\, = \,1}^1 {\left( \matrix{
  3 - k \cr 
  2 \cr}  \right)}  = \left( \matrix{
  2 \cr 
  2 \cr}  \right) = \left( \matrix{
  3 \cr 
  3 \cr}  \right) = 1
$$

*b ) if it is true for $n$, then it is true for $n+1$;
in fact it is
$$
\eqalign{
  & \sum\limits_{k\, = \,1}^{n + 1 - 2} {\left( \matrix{
  n + 1 - k \cr 
  2 \cr}  \right)}  = \sum\limits_{k\, = \,1}^{n - 1} {\left( {\left( \matrix{
  n - k \cr 
  2 \cr}  \right) + \left( \matrix{
  n - k \cr 
  1 \cr}  \right)} \right)}  =   \cr 
  &  = \sum\limits_{k\, = \,1}^{n - 1} {\left( \matrix{
  n - k \cr 
  2 \cr}  \right)}  + \sum\limits_{k\, = \,1}^{n - 1} {\left( {n - k} \right)}  =   \cr 
  &  = \sum\limits_{k\, = \,1}^{n - 2} {\left( \matrix{
  n - k \cr 
  2 \cr}  \right)}  + \sum\limits_{k\, = \,n - 1}^{n - 1} {\left( \matrix{
  n - k \cr 
  2 \cr}  \right)}  + \sum\limits_{k\, = \,1}^{n - 1} n  - \sum\limits_{k\, = \,1}^{n - 1} k  =   \cr 
  &  = \left( \matrix{
  n \cr 
  3 \cr}  \right) + \left( \matrix{
  1 \cr 
  2 \cr}  \right) + n\left( {n - 1} \right) - {{n\left( {n - 1} \right)} \over 2} =   \cr 
  &  = \left( \matrix{
  n \cr 
  3 \cr}  \right) + {{n\left( {n - 1} \right)} \over 2} = \left( \matrix{
  n \cr 
  3 \cr}  \right) + \left( \matrix{
  n \cr 
  2 \cr}  \right) = \left( \matrix{
  n + 1 \cr 
  3 \cr}  \right) \cr} 
$$
A: To prove:
$$\sum_{k=1}^{n-2} \binom{n-k}{2} = \binom{n}{3}$$
Base case ($n = 3$):
$$ \sum_{k=1}^{1} \binom{3-k}{2} = \binom{2}{2} = 1 = \binom{3}{3}
$$
Induction hypothesis:
For fixed $n$ we may assume: $\sum_{k=1}^{n-2} \binom{n-k}{2} = \binom{n}{3}$
Induction step ($n \to n+1$):  
\begin{align}
\sum_{k=1}^{n-1} \binom{n+1-k}{2} &= \binom{2}{2} + \sum_{k=1}^{n-2} \binom{n+1-k}{2} \\
&= 1 + \sum_{k=1}^{n-2} \left(\binom{n-k}{2} + n-k\right) \\
&= 1 + n(n-2) - \frac{(n-2)(n-1)}{2} +\sum_{k=1}^{n-2} \binom{n-k}{2} \\
&\overset{IH}{=} \frac{n(n-1)}{2} + \binom{n}{3} \\
&= \frac{n!}{2(n-2)!} + \binom{n}{3} \\
&= \binom{n}{2} + \binom{n}{3} \\
&= \binom{n+1}{3}
\end{align}
A: The equality can be written as 
$$
\sum_{u=2}^{n-1}\binom{u}{2}=\binom{n}{3}.
$$
Observe that by Pascal's identity
$$
\binom{u+1}{3}-\binom{u}{3}=\binom{u}{2}
$$
(here $\binom{m}{k}=0$ for $m<k$) whence
$$
\sum_{u=2}^{n-1}\binom{u}{2}=\sum_{u=2}^{n-1}\binom{u+1}{3}-\binom{u}{3}
$$
which is a telescoping sum.
