Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

4 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.