# Binomial Theorem

By finding appropriate values for $x$ and $y$, evaluate $$\sum_{k=0}^{n} k(k-1)\binom{n}{k}$$

I thought to take the derivative of $(1 + x)^n$ twice, but I noticed the index on $k$ remained at $0$.

-
Hint: first simplify the sum by evaluating the first two of the $n+1$ terms. Then cancel a $k(k-1)$ in the numerator of each term with a $k(k-1)$ in the denominator (look at $k!$). – Dilip Sarwate Feb 5 '13 at 2:39

The index on $k$ is not a problem. Look at, for example, the case $n=4$. $$(1+x)^4=1+4x+6x^2+4x^3+x^4$$ Differentiating twice, $$12(1+x)^2=(2)(1)(6)+(3)(2)(4)x+(4)(3)x^2$$ Note that the $k(k-1)$ is zero for $k=0$ and for $k=1$, so you can begin the sum at zero or at two, and it makes no difference.

-

You have $$\sum_{k=0}^n {n\choose k} x^k = (1 + x)^n.$$ Differentiate. The constant term drops off, and you have $$\sum_{k=1}^n {n\choose k} kx^{k-1} = n(1 + x)^{n-1}.$$ Do it again to get $$\sum_{k=2}^n {n\choose k} x^{k-2} = n(n-1)(1 + x)^{n-2}.$$ You can take $x=0$, exhibit a little care, and see all.

-

That works fine.

\begin{align*} \frac{d^2}{dx^2}\left((1+x)^n\right)&=\frac{d^2}{dx^2}\left(\sum_{k\ge 0}\binom{n}kx^k\right)\\\\ &=\frac{d}{dx}\left(\sum_{k\ge 0}k\binom{n}kx^{k-1}\right)\\\\ &=\sum_{k\ge 0}k(k-1)\binom{n}kx^{k-2}\;. \end{align*}

(Recall that $\binom{n}k=0$ if $k>n$, so there’s no need to worry about the upper limit.)

Now substitute $x=1$ to get

$$n(n-1)2^{n-2}=\sum_{k\ge 0}k(k-1)\binom{n}k\;.$$

It’s perfectly true that the first two terms are $0$, and we could just as well write

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

but that’s unnecessarily ugly. It’s also true that if we were differentiating by hand a small example, we’d never even write down those terms: we don’t normally write

$$(-1)(0)x^{-2}+(0)(1)4x^{-1}+(1)(2)6x^0+(2)(3)4x^1+(3)(4)x^2$$

for the second derivative of $1+4x+6x^2+4x^3+x^4$, but those factors of $0$ ensure that there’s no actual harm in it.

-

Without using derivatives,

$$\text{ for }k\ge 2, k(k-1)\binom nk=\frac{k(k-1)n!}{(n-k)!k!}=\frac{n(n-1)k(k-1)(n-2)!}{\{n-2-(k-2)\}!(k-2)!k(k-1)}=n(n-1)\binom{n-2}{k-2}$$

So, $$\sum_{0\le k\le n}k(k-1)\binom nk$$ $$=\sum_{2\le k\le n}k(k-1)\binom nk$$ $$=\sum_{2\le k\le n}n(n-1)\binom{n-2}{k-2}$$ $$=n(n-1)\sum_{0\le r\le n-2}\binom {n-2}r$$ $$=n(n-1)(1+1)^{n-2}$$

-