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}. }$$