# Sum of binomial coefficient

My question is the following. Calculate the value of:

$$\sum_{u=0}^{22} u(u-1) \binom {22}u$$

I am not too sure I'm allowed to perform each of these steps, but what I thought was the following:

$$\sum_{u=0}^n \binom nu = 2^n.$$

$$2^{22}\sum_{u=0}^{22} u(u-1)$$

$$2^{22}\sum_{u=0}^{22} (u^2-u)$$

$$2^{22}\sum_{u=0}^{22} u^2- 2^{22}\sum_{k=0}^{22}u$$

My thought is to use the following equations afterwards. However, I don't get the correct answer.

$$\sum_{k=0}^{n} k^2 = n(n+1)(2n+1)/6$$

$$\sum_{k=0}^{n} k = n(n+1)/2$$

• Is $k$ supposed to be $u$ in the first formula? $u$ is not defined. – saulspatz Apr 24 '18 at 16:23
• I reckon $u(u-1)\binom{22}u=22\times21\binom{20}{u-2}$. – Lord Shark the Unknown Apr 24 '18 at 16:23
• @saulspatz, yes exactly sorry... I will correct it now! – John Snow Apr 24 '18 at 16:24
• First, notice that the terms for $u=0$ and $u=1$ are zero, so that the sum really starts at $u=2$. Then apply the hint in the comment from Lord Shark the Unknown. – saulspatz Apr 24 '18 at 16:29
• I dont understand the hint... :/ Can someone explain the step? – John Snow Apr 24 '18 at 16:31

It will be lot easier if you do following to reduce the expression: \begin{align} \sum_{u=0}^{22} u(u-1) {22 \choose u} &= \sum_{u=2}^{22} u(u-1) \frac{22!}{(22-u)! u!} \\ &= \sum_{u=2}^{22} \frac{22!}{(22-u)! (u-2)!} \\&= 22\times 21\times \sum_{u=2}^{22} \frac{20!}{(20-(u - 2))! (u-2)!} \\ &= 22\times 21\times \sum_{k=0}^{20} \frac{20!}{(20-k)! k!} \\ &= 22\times 21\times \sum_{k=0}^{20} {20 \choose k} \\ &= 22 \times 21 \times 2^{20} \end{align} Note that:

(1) at the first equality we discarded $u = 0$, and $u = 1$ terms since they are both zeros.

(2) at second equality we cancelled $u(u-1)$ terms against $u!$.

(3) at forth equality, we substituted $u-2$ by $k$.

Rest steps are easy to follow.

It is enough to give a combinatorial interpretation to $$2\sum_{u=0}^{22}\binom{22}{u}\binom{u}{2}=2\sum_{u=2}^{22}\binom{22}{u}\binom{u}{2}.$$ Assume to have $22$ people, and to graduate some ($\geq 2$) of them, then to want to select $2$ graduated people and to give them a laude (is there a specific English translation of the expression magna cum laude for denoting an excellent outcome?). The number of ways this can be done is $\sum_{u=2}^{22}\binom{22}{u}\binom{u}{2}$. On the other hand you may select the excellent students first, then the other people to graduate. This leads to $$\sum_{u=2}^{22}\binom{22}{u}\binom{u}{2} = \binom{22}{2} 2^{20},\qquad \sum_{u=0}^{22}u(u-1)\binom{22}{u} = 22\cdot 21\cdot 2^{20}.$$

• In the US I've seen "cum laude", "magna cum laude", and "summa cum laude" when graduating University. – Brian J Apr 24 '18 at 17:46
• well magna cum laude literally means "with great praise/honors" so perhaps to "give them an award" is what you're looking for? – Giuseppe Apr 25 '18 at 12:38

If I understand it correctly, your logic is the following:

$$\sum_{u=0}^{22} u(u-1) \binom {22}u =$$

$$\sum_{u=0}^{22} u(u-1) \sum_{u=0}^{22} \binom {22}u=$$

$$2^{22}\sum_{u=0}^{22} u(u-1)$$

This is not valid logic; you can't separate out factors within a summation into separate summations.

$$\sum a_kb_k \neq \sum a_k \sum b_k$$

\begin{align} \sum_{u=0}^{22}\color{blue}{u(u-1)}\binom {22}u &=\color{blue}2\sum_{u=0}^{22}\binom {22}u\color{blue}{\binom u2}\\ &=2\sum_{u=0}^{22}\binom {22}2\binom {20}{u-2} &&\scriptsize \text{using }\binom ab\binom bc=\binom ac\binom {a-c}{b-c}\\ &=2\binom {22}2\sum_{u=0}^{22}\binom {22}{u-2}\\ &=22\cdot 21\cdot \sum_{u=0}^{20}\binom {20}u\\ &=\color{red}{22\cdot 21\cdot 2^{20}}\end{align}

$$(1+x)^n = \sum_{k=0}^n \binom {n}k x^k$$

and

$$\frac{d^2}{dx^2}(1+x)^n = n(n-1)(1+x)^{n-2} = \sum_{k=2}^n k(k-1)\binom {n}k x^{k-2}$$

making $x = 1 \Rightarrow n(n-1)2^{n-2}$

\begin{align} & \sum_{u=0}^{22} u(u-1) \binom {22} u \\[10pt] = {} & \sum_{u=2}^{22} u(u-1) \binom {22} u \quad \text{because the first two terms are 0} \\[10pt] = {} & \sum_{v=0}^{20} (v+2)(v+1) \binom {22}{v+2}. \end{align} Here we have let $v=u-2,$ so that $u = v+2,$ and as $u$ goes from $2$ to $22$ then $v$ goes from $0$ to $20.$

Then our sum becomes \begin{align} & \sum_{v=0}^{20} (v+2)(v+1) \frac{22!}{(v+2)!(20-v)!} \\[10pt] = {} & \sum_{v=0}^{20} \frac{22!}{v!(20-v)!} \\[10pt] = {} & 22\cdot21\cdot\sum_{v=0}^{20} \frac{20!}{v!(20-v)!} \\[10pt] = {} & 22\cdot21\cdot \sum_{v=0}^{20} \binom {20} v \\[10pt] = {} & 22\cdot21\cdot 2^{20}. \end{align}

A probabilistic approach. Let $X$ be binomial random variable with $22$ trials and probability of success $1/2$. Then $X=\sum_{i=1}^{22} X_i$ where $X_i$ are iid bernoulli trials with $P(X_i=1)=P(X_i=0)=1/2$. In particular $EX=\sum_{i}EX_i=22/2=11$ and $\text{Var} X=\sum_{i} \text{Var} X_i=22/4$ by independence.

In relation to the desired sum, we note that $$EX(X-1)=\frac{1}{2^{22}}\sum_{u=0}^{22}\binom{22}{u}u(u-1).$$ But $$EX(X-1)=\text{Var}(X)+(EX)^2-(EX)=\frac{11}{2}+11^2-11=11(21/2)$$ whence $$\sum_{u=0}^{22}\binom{22}{u}u(u-1)=2^{22}\times11\times\frac{21}{2}=2^{20}\times22\times21$$

We can also answer the general case using the binomial coefficient identity $$k\binom{n}{k} = n\binom{n-1}{k-1}$$ For ease of computation we define $\binom{n}{k}$ to be $0$ for integrers $n, k$ where $k < 0$ or $k > n$. We get: \begin{align} \sum_k k(k-1)\binom{n}{k} & = n\sum_k (k-1)\binom{n-1}{k-1}\\ & = n(n-1)\sum_k\binom{n-2}{k-2} \\ & = n(n-1)\sum_k\binom{n-2}{k} \\ & = n(n-1)2^{n-2} \end{align} For $n = 22$ we get $\sum_k k(k-1)\binom{22}{k} = 22*21*2^{20}$