summation - Mathematical induction proof that $sumlimits_{k=2}^{n-1} {k choose 2} = {n choose 3} $

I have a problem with a mathematical equation. I don’t find the given solution.

This is the equation: $\sum\limits_{k=2}^{n-1} {k \choose 2} = {n \choose 3} $

I should show with induction that the expression is correct for every $n >= 3$.

I started with the beginning of the induction. For $n = 3$.

$\sum\limits_{k=2}^{2} {2 \choose 2} = 1 = {3 \choose 3} $
That’s correct.

Now I don’t know how to dissolve that equation. The solution should be:

$\sum\limits_{k=2}^{n-1} {k \choose 2} + {n \choose 2} = {n \choose 3} + {n \choose 2} = {n + 1 \choose 3} $

Why ${n \choose 2}$? It would be awesome, if someone could tell me the steps or give some tips how I could reach that solution.

Edit:

Well, at that point I am:

1. Beginning of the induction: $\sum\limits_{k=2}^{2} {2 \choose 2} = 1 = {3 \choose 3}$




2. Induction step n + 1: $\sum\limits_{k=2}^{n} {k \choose 2} + {n \choose 3}$
   Thats my assumption: ${n \choose 3}$.




3. Change the first addend with the assumption, so I get ${n \choose 2} + {n \choose 3}$




4. Add it into the binomial coefficient formula: ${n! \choose 2!(n-2)!} + {n! \choose 3!(n-3)!}$

I have it like @david-mitra. Whats wrong with that way?

Thanks.

Answer

We wish to prove:
$$
\sum_{k=2}^{n-1} {k\choose 2}= {n\choose3},\quad n\ge3.\tag{1}
$$

If you want to prove that equation (1) holds for all $n\ge 3$ using induction:

1) Show that the equation is true for $n=3$:

$$
\sum_{k=2}^{3-1} {k\choose 2}= {2\choose2}= {3\choose3}.\tag{1}
$$

2) Assume that the equation is true for $n=m$:
$$
\color{maroon}{\sum_{k=2}^{m-1} {k\choose 2}}= \color{maroon}{m\choose3 }.

$$

3) Now show that the equation must be true for $n=m+1$:

$$\eqalign{
\sum_{k=2}^{(m+1)-1} {k\choose 2}
&=\sum_{k=2}^{m } {k\choose 2}\cr
&=\sum_{k=2}^{m-1 } {k\choose2} +\color{darkgreen}{\sum_{k=m}^m {k\choose2}}\cr
&=\biggl[\ \color{maroon}{ \sum_{k=2}^{m-1 } {k\choose 2}}\ \biggr]+\color{darkgreen}{m\choose2}\cr
&= \color{maroon}{ m\choose 3} +{m\choose2}\cr


&= {m!\over (m-3)! 3!}+ {m!\over (m-2)! 2!}\cr
&={ m(m-1)(m-2)\over 3!} +{ m(m-1) \over 2!} \cr
&= m(m-1)({m-2\over 6}+{3\over 6 })\cr

&= { m(m-1)(m+1)\over 6} \cr
&={m+1\choose 3}.

}
$$