Sum of binomial coefficient

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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