sum of binomial coefficients expansion to prove equation

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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