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