Proof $n \geq 3\hspace{0.5cm} \sum\limits_{k=1}^{n-2}{n-k\choose 2}={n\choose 3}$

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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}