4
$\begingroup$

I'm asked to prove the identity $$n(n+1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k}$$ using the binomial theorem.

What I've been able to come up with so far is letting $$f(x) = (x+1)^n = \sum_{k=0}^{n}x^k\binom{n}{k}$$ taking two derivatives gives $$f''(x) = n(n-1)(x+1)^{n-2} = \sum_{k=2}^{n}k(k-1)x^{k-2}\binom{n}{k}$$ If I plug in x = 1, I get something super close to the required identity: $$n(n-1)2^{n-2} = \sum_{k=2}^{n}k(k-1)\binom{n}{k}$$

I think the method I'm using is correct, and I just need to tweak it a little bit... Any help is appreciated!

$\endgroup$
  • $\begingroup$ Easy. Just multiply through by $x$ before you differentiate the second time! $\endgroup$ – almagest Mar 21 '16 at 17:44
4
$\begingroup$

After you take the first derivative, you have

$$n(x+1)^{n-1}=\sum_{k=1}^nkx^{k-1}\binom{n}k\;.$$

Now multiply both sides by $x$ before you differentiate again.

Here’s an alternative that uses the binomial theorem only to evaluate $\sum_k\binom{m}k=2^m$. Using the fact that $k\binom{n}k=n\binom{n-1}{k-1}$, we can calculate

$$\begin{align*} \sum_kk^2\binom{n}k&=\sum_kkn\binom{n-1}{k-1}\\ &=n\sum_kk\binom{n-1}{k-1}\\ &=n\sum_k(k+1)\binom{n-1}k\\ &=n\sum_kk\binom{n-1}k+n\sum_k\binom{n-1}k\\ &=n\sum_k(n-1)\binom{n-2}{k-1}+n2^{n-1}\;, \end{align*}$$

and I expect that you can finish it from there.

$\endgroup$
  • $\begingroup$ Multiplying both sides of the first derivative by $x$ gives me $$xn(x+1)^{n-1} = \sum_{k=1}^{n}kx^{k}\binom{n}{k}$$ Differentiating gives $$f''(x) = xn(n-1)(x+1)^{n-2} = \sum_{k=1}^{n}k^2x^{k-1}\binom{n}{k}$$ Plugging in $x=1$: $$n(n-1)2^{n-2} = \sum_{k=1}^{n}k^2\binom{n}{k}$$ Which still contains an $n-1$ term where I need a $n+1$ term, what am I doing wrong here? $\endgroup$ – Jim Jj Mar 21 '16 at 19:15
  • $\begingroup$ @Jim: Your differentiation is wrong: $x(x+1)^{n-1}$ is a product, so you’ll have two terms in the derivative (before simplification). $\endgroup$ – Brian M. Scott Mar 21 '16 at 19:17

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.