How do I find $\sum_{k=2}^nk(k-1)\binom{n}{k}$

Question

I have come across the following problem in my textbook and I am looking for some help with its execution, thanks!

Find,

$$\sum_{k=2}^nk(k-1)\binom{n}{k}$$

Answer 1

Here's a good way to get this to look more like the binomial theorem.

Expand $$ \dbinom nk = \dfrac {n!}{k!(n-k)!} $$

Then $$ k(k-1) \dbinom nk = \dfrac {n!}{(k-2)!(n-k)!} = n(n-1)\dfrac {(n-2)!}{(k-2)!(n-k)!} = n(n-1)\dbinom {n-2}{k-2}$$

Now the $n(n-1)$ can be pulled out of the sum, so the sum becomes

$$ n(n-1)\sum_{k=2}^n \dbinom{n-2}{k-2} = n(n-1)\sum_{j=0}^{n-2} \dbinom{n-2}j$$

where I used the change of variables $j = k-2$. You should be able to proceed with the binomial theorem.

Answer 2

You want to select $\geq 2$ people from a group of $n$ people, give a gold medal to someone in the selected crew and a silver medal to someone else in the crew. You may pick the gold medalist in $n$ ways, the silver medalist in $n-1$ ways and the other members of the crew in $2^{n-2}$ ways, so $$ \sum_{k=2}^{n}k(k-1)\binom{n}{k} = n(n-1) 2^{n-2}.$$

---

In the standard generating-functions fashion, by applying $\frac{d^2}{dx^2}$ to both sides of $\sum_{k=0}^{n}\binom{n}{k}x^k = (x+1)^n $ we get $\sum_{k=2}^{n}\binom{n}{k}k(k-1)x^{k-2} = n(n-1)(x+1)^{n-2}$ and the same outcome can be recovered by evaluating these terms at $x=1$.

Answer 3

Remember the binomial coefficient $\dbinom nk$ is the coefficient of $x^k$ in the expansion of $(1+x)^n$. So $k(k-1)\dbinom nk$ is the coefficient of $(x^k)''$ in the expansion of $\bigl((1+x)^n\bigr)''$: $$\sum_{k=2}^nk(k-1)\dbinom nk x^{k-2}=n(n-1)(1+x)^{n-2},$$ and setting $x=1$ in this formula, you get $$\sum_{k=2}^nk(k-1)\dbinom nk= n(n-1)2^{n-2}.$$

Answer 4

A probabilistic approach. Let $p=1/2$ and let $X\sim \text{Bin}(n,p)$ so that $X\stackrel{d}{=}X_{1}+\dotsb+X_{n}$ where $X_{i}\sim\text{Ber}(p)$ are i.i.d Bernoulli trials. Then $$ EX=\sum_{i=1}^n EX_{i}=np;\quad EX^2-(EX)^2=\text{Var} X=\sum_{i=1}^n \text{Var}X_{i}=np(1-p). $$ by independence. Hence $$ EX(X-1)=EX^2-EX=np(1-p)+(np)^2-np=p^2(n^2-n)=\frac{n^2-n}{4}. $$ But $$ \sum_{k=2}^nk(k-1)\binom{n}{k}\frac{1}{2^n}=EX(X-1)\implies \sum_{k=2}^nk(k-1)\binom{n}{k}=2^{n-2}n(n-1). $$ Alternatively, use the identity $$ \binom{n}{k}\binom{k}{2}=\binom{n}{2}\binom{n-2}{k-2};\quad n\geq k\geq 2 $$ so that $$ \sum_{k=2}^nk(k-1)\binom{n}{k}= \sum_{k=2}^n2\binom{k}{2}\binom{n}{k}= 2\binom{n}{2}\sum_{k=2}^n\binom{n-2}{k-2} =n(n-1)2^{n-2} $$ by the binomial theorem.