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

Question

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?

Answer 1

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.

Answer 2

$$\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?

Answer 3

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

Now use this OR How to get to the formula for the sum of squares of first n numbers?

Answer 4

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}

Answer 5

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

Answer 6

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\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}

Answer 7

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$