5
$\begingroup$

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?

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

7 Answers 7

4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 29, 2017 at 5:56
  • $\begingroup$ Thanks for comment. I got it and because of this I deleted my comment. $\endgroup$
    – Amin235
    Commented Apr 29, 2017 at 6:10
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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}

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .