# Prove $\sum_{k=0}^{n-2}{n-k \choose 2} = {n+1 \choose 3}$

Prove $$\sum_{k=0}^{n-2}{n-k \choose 2} = {n+1 \choose 3}$$

Is there a relation I can use that easily yields above equation?

• You could start with $\;{n-k \choose 2} = \frac{(n-k)\cdot(n-k-1)}{2\cdot 1}\,$.
– dxiv
Apr 29, 2017 at 4:59
• @mvw not, the same. I edited the problem to consider that. Apr 29, 2017 at 5:00
• @dxiv I already knew that. Thank you. What are the next steps? Apr 29, 2017 at 5:01
• $\sum \frac{(n-k)\cdot(n-k-1)}{2\cdot 1} = \frac{1}{2}\left(n^2 \cdot \sum 1 - n \cdot \sum (2k+1) + \sum k(k+1)\right)$
– dxiv
Apr 29, 2017 at 5:03
• Note: The original question just stated the left hand side
– mvw
Apr 29, 2017 at 11:30

The right hand side ${n+1 \choose 3}$ is the number of ways to choose 3 elements from $\{1,2,\ldots,n+1\}$. Let $A$ denote the set of all 3-subsets of $\{1,2,\ldots,n+1\}$. We want to show that $|A|$ is equal to the left hand side.

Let $A_i$ denote the set of all 3-subsets of $\{1,2,\ldots,n+1\}$ which have $i$ as their largest element. For example, if $i=n+1$, then $A_{n+1}$ is the set of all 3-subsets which contain $n+1$, and the number of ways to choose the remaining 2 elements is ${n \choose 2}$. Hence, $|A_{n+1}| = {n \choose 2}$. More generally, $|A_i| = {i-1 \choose 2}$, for $i=3,\ldots,n+1$, because the remaining 2 elements must be chosen from $\{1,\ldots,i-1\}$. Note that $i$ has to be at least 3 because the largest of 3 elements will be at least 3.

Using the fact that the $A_i$'s $(i=3,4,\ldots,n+1)$ are disjoint and their union is all of $A$, we obtain the desired formula.

• If the largest element in a 3-subset is say 7, then this largest element can't be any of $3, 4, 5, 6, 8, 9,\ldots,n+1$. So $A_7$ is disjoint from $A_3, A_4, A_5, A_6, A_8, A_9, \ldots, A_{n+1}$. Similarly for the other $A_i$'s, and so the $A_i$'s are pairwise disjoint. Apr 29, 2017 at 5:56
• Thanks for comment. I got it and because of this I deleted my comment. Apr 29, 2017 at 6:10

$$\sum_{k=0}^{n-2}\frac{k^2+k(1-2n)+n^2-1}{2}\tag{Simplify what @dixv said}$$ now, $$\sum_{k=1}^nk=\frac{n(n+1)}{2}\text{ and }\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}$$

Hope it helps?

For $$S=\sum_{k=0}^{n-2}(n-k)(n-k-1)$$ set $n-k=r$ to get $$S=\sum_{r=1}^nr(r-1)=\sum_{r=1}^nr^2-\sum_{r=1}^nr$$

Using index transformation $m = n - k$, reversal of the summation order and the definition of the binomial coefficient in terms of factorials we can write for $n\ge 2$: \begin{align} \sum_{k=0}^{n-2} \binom{n-k}{2} &= \sum_{m=2}^{n} \binom{m}{2} \\ &= \sum_{m=2}^{n} \frac{m!}{2! (m-2)!} \\ &= \sum_{m=2}^{n} \frac{m(m-1)}{2} \\ &= \sum_{m=1}^n \frac{m(m-1)}{2} \\ &= \frac{1}{2} \sum_{m=1}^{n} m^2 - \frac{1}{2} \sum_{m=1}^n m \\ &= \frac{n(n+1)(2n+1)}{12} - \frac{n(n+1)}{4} \\ &= \frac{1}{6} n^3 + \frac{1}{4} n^2 + \frac{1}{12} n - \left( \frac{1}{4} n^2 + \frac{1}{4} n \right) \\ &= \frac{1}{6} n^3 - \frac{1}{6} n \end{align} where we used Faulhaber's formula for the square pyramidal and triangular numbers.

On the other side of the equation we have: \begin{align} \binom{n+1}{3} &= \frac{(n+1)!}{3!(n+1-3)!} \\ &= \frac{(n+1)n(n-1)}{6} \\ &= \frac{n^3 - n}{6} \end{align}

You can prove it using generating functions. We wish to prove that $$\sum_{m=0}^{n} \binom{m}{2}=\binom{n+1}{3}\tag{1}$$ Use the identity $$\frac{1}{(1-x)^k}=\sum_{n=0}^\infty \binom{k+n-1}{k-1}x^n.\tag{2}$$ (which can be obtained by repeatedly differentiating the geometric series) where $k\geq1$ to get that the generating function whose $m$th coefficent is $\binom{m+2}{2}$ is $(1-x)^{-3}$ and the generating function whose $m$th coefficent is $\binom{m}{2}$ is $x^2(1-x)^{-3}$. Thus $$\sum_{m=0}^{n} \binom{m}{2}= [x^n]\left(\frac{1}{1-x}\frac{x^2}{(1-x)^{3}}\right) = [x^n] \left(\frac{x^2}{(1-x)^{4}}\right)\tag{3} =\binom{n+1}{3}$$ by (2) as desired where $[x^n]$ extracts the coefficient of $x^n$.

$\newcommand{\bbx}{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}{\mathcal{#1}} \newcommand{\mrm}{\mathrm{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = 0}^{n - 2}{n - k \choose 2} & = \sum_{k = 0}^{n - 2}{k + 2\choose 2} = \sum_{k = 2}^{n}{k \choose 2}= \sum_{k = 2}^{n}{k^{\underline{2}} \over 2} = {1 \over 2}\left.{k^{\underline{3}} \over 3}\,\right\vert_{\ 2}^{\ n + 1} = {\pars{n + 1}^{\underline{3}} - 2^{\underline{3}}\over 6} \\[5mm] & = {\pars{n + 1}n\pars{n - 1} \over 6} \end{align}

With so many proofs there is no need for one more. But I like using finite differences.

Let $f(n)$ represent the sum.

$\Delta f(n) = \binom {n+1}{2} = \Delta \binom {n+1}{3}$

$\implies f(n) = \binom {n+1}{3} + c$

for $n=2$, we get $c + 1 = 1 \implies c=0$