2
$\begingroup$

I want to prove that $$ \sum_{i=1}^{n}{\binom{i}{2}} = \binom{n+1}{3} $$

I already expanded

$$ \binom{n+1}{3} $$ to $$ \binom{n+1}{3} = \frac{1}{6} * (n+1) *n*(n-1) $$ and I know that the following equation must be right $$ \sum_{i=1}^{n}{\binom{i}{2}} = \frac{1}{6} * (n+1) *n*(n-1) $$ but I do not get the expansion right, I tried starting with writing the sum explicit $$ \binom{1}{2}+\binom{2}{2}+\ldots+\binom{n-1}{2}+\binom{n}{2} $$ since 1 over 2 is zero it can be shortened to $$ \sum_{i=2}^{n}{\binom{i}{2}} = \binom{2}{2}+\ldots+\binom{n-1}{2}+\binom{n}{2} $$ then I expanded the binomial coefficients to the corresponding factorial form $$ \binom{n}{k} = \frac{n!}{k! * (n-k)!} $$ but I do not get it right, could someone please help me?

$\endgroup$
1
$\begingroup$

$$\binom{2}{2}+\ldots+\binom{n-1}{2}+\binom{n}{2}=\frac{1\times 2}{2}+\frac{2\times 3}{2}+\frac{3\times 4}{2}+...+\frac{(n-1)\times n}{2}=\frac{1}{2}(1\times 2+2\times 3+3\times 4+...+(n-1)\times n)=\frac {1}{2}\times \frac{(n-1)n(n+1)}{3}=\frac{(n-1)n(n+1)}{6}$$

$\endgroup$
1
$\begingroup$

$\begin{array}\\ \binom{n+1}{3}-\binom{n}{3} &=\dfrac{(n+1)n(n-1)}{6}-\dfrac{n(n-1)(n-2)}{6}\\ &=\dfrac{n(n-1)((n+1)-(n-2))}{6}\\ &=\dfrac{3n(n-1)}{6}\\ &=\dfrac{n(n-1)}{2}\\ &=\binom{n}{2}\\ \end{array} $

Therefore $\sum_{i=1}^{n}\binom{i}{2} =\sum_{i=1}^{n}(\binom{i+1}{3}-\binom{i}{3}) =\binom{n+1}{3} $.

Note that $\binom{n}{m} = 0$ for $m > n$.

In general, since $\binom{n}{m} =\dfrac{\prod_{k=0}^{m-1}(n-k)}{m!} $,

$\begin{array}\\ \binom{n+1}{m}-\binom{n}{m} &=\dfrac{\prod_{k=0}^{m-1}(n+1-k)}{m!}-\dfrac{\prod_{k=0}^{m-1}(n-k)}{m!}\\ &=\dfrac{\prod_{k=-1}^{m-2}(n-k)}{m!}-\dfrac{\prod_{k=0}^{m-1}(n-k)}{m!}\\ &=\dfrac{(n+1)\prod_{k=0}^{m-2}(n-k)-(n-m+1)\prod_{k=0}^{m-2}(n-k)}{m!}\\ &=\dfrac{((n+1)-(n-m+1))\prod_{k=0}^{m-2}(n-k)}{m!}\\ &=\dfrac{m\prod_{k=0}^{m-2}(n-k)}{m!}\\ &=\dfrac{\prod_{k=0}^{m-2}(n-k)}{(m-1)!}\\ &=\binom{n}{m-1}\\ \end{array} $

so that

$\sum_{i=1}^{n}\binom{i}{m-1} =\sum_{i=1}^{n}(\binom{i+1}{m}-\binom{i}{m}) =\binom{n+1}{m} $.

$\endgroup$
1
$\begingroup$

A variation based upon the binomial theorem and the finite geometric series formula.

We consider the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We can write this way \begin{align*} \binom{n}{k}=[x^k](1+x)^n\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{i=1}^n\binom{i}{2}}&=\sum_{i=0}^n[x^2](1+x)^i\tag{2}\\ &=[x^2]\sum_{i=0}^n(1+x)^i\tag{3}\\ &=[x^2]\frac{(1+x)^{n+1}-1}{(1+x)-1}\tag{4}\\ &=[x^3]\left((1+x)^{n+1}-1\right)\tag{5}\\ &\,\,\color{blue}{=\binom{n+1}{3}}\tag{6} \end{align*} and the claim follows.

Comment:

  • In (2) we apply the coefficient of operator according to (1). The lower limit of the index $i$ is set to $i=0$ which doesn't change anything, since $\binom{0}{2}=[x^2](1+x)^0=[x^2]1=0$.

  • In (3) we use the linearity of the coefficient of operator: $[x^p]A(x)+[x^p]B(x)=[x^p]\left(A(x)+B(x)\right)$.

  • In (4) we use the finite geometric summation formula.

  • In (5) we observe the denominator is $x$ and we use the rule $[x^p]\frac{1}{x}A(x)=[x^{p+1}]A(x)$.

  • In (6) we select the coefficient of $x^3$.

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