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:
-
Beginning of the induction: $\sum\limits_{k=2}^{2} {2 \choose 2} = 1 = {3 \choose 3}$
-
Induction step n + 1: $\sum\limits_{k=2}^{n} {k \choose 2} + {n \choose 3}$
Thats my assumption: ${n \choose 3}$. -
Change the first addend with the assumption, so I get ${n \choose 2} + {n \choose 3}$
-
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.
Best Answer
Your equation is a special case of the identity $$ \sum_{j=k}^{n-m}\binom{j}{k}\binom{n-j}{m}=\binom{n+1}{k+m+1}\tag{1} $$ with $m=0$.
Equation $(1)$ can also be shown by induction, but it also follows from the identity $$ \frac{1}{(1-x)^{k+1}}=\sum_{n=k}^\infty\binom{n}{k}x^{n-k}\tag{2} $$ while considering $$ \frac{1}{(1-x)^{k+1}}\frac{1}{(1-x)^{m+1}}=\frac{1}{(1-x)^{k+m+2}}\tag{3} $$