3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is $k$ supposed to be $u$ in the first formula? $u$ is not defined. $\endgroup$ – saulspatz Apr 24 '18 at 16:23
  • $\begingroup$ I reckon $u(u-1)\binom{22}u=22\times21\binom{20}{u-2}$. $\endgroup$ – Lord Shark the Unknown Apr 24 '18 at 16:23
  • $\begingroup$ @saulspatz, yes exactly sorry... I will correct it now! $\endgroup$ – John Snow Apr 24 '18 at 16:24
  • $\begingroup$ 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. $\endgroup$ – saulspatz Apr 24 '18 at 16:29
  • $\begingroup$ I dont understand the hint... :/ Can someone explain the step? $\endgroup$ – John Snow Apr 24 '18 at 16:31
11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

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

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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