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

| cite | improve this answer | |
$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Ashwin Ganesan Apr 29 '17 at 5:56
  • $\begingroup$ Thanks for comment. I got it and because of this I deleted my comment. $\endgroup$ – Amin235 Apr 29 '17 at 6:10
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?

| cite | improve this answer | |
$\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}

| cite | improve this answer | |
$\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$.

| cite | improve this answer | |
$\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}

| cite | improve this answer | |
$\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$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.