3
$\begingroup$

I needed to compute this sum: $$\sum_{i=0}^n\binom{n}{i}i^2$$ I don't want any proofs or formulae, but just a yes/no answer. Is there a closed form expression for this sum?

Just to share, I was able to find a closed form expression for this sum: $$\sum_{i=0}^n\binom{n}{i}i=n.2^{n-1}$$ by using a property of arithmetic progressions and sums of combinations.
Is there any closed form expression for my sum, or more generally, sums like: $$\sum_{i=0}^n\binom{n}{i}i^k$$ , for some $k\in\mathbb{N}$?

$\endgroup$
  • 2
    $\begingroup$ There is a closed form for your sum, and you can get it by applying what you already found for $\sum_k\binom{n}kk$. (You can also use calculus methods, but they’re not necessary.) $\endgroup$ – Brian M. Scott Nov 4 '16 at 16:06
  • $\begingroup$ Differentiate the series $(1+x)^n$ wrt to $x$ twice to get your sum. $\endgroup$ – SirXYZ Nov 4 '16 at 16:11
3
$\begingroup$

Yes. You can find the formula as follows: by the binomial theorem we have

$$(1+x)^n = \sum_{i=0}^n {n\choose i} x^i.$$

Now apply the differential operator $\Big(x\frac{d}{dx}\Big)^k$ on both sides.

$\endgroup$
  • $\begingroup$ Concise and complete. +1 ... You might consider adding "then set $x=1$" at the end of the answer. $\endgroup$ – Mark Viola Nov 4 '16 at 16:07
  • $\begingroup$ Thanks @Dr.MV, I trust that the OP will extract that information from your comment ;). $\endgroup$ – J.R. Nov 4 '16 at 16:13
1
$\begingroup$

An alternative approach. Us that $\binom{n}{i}\binom{i}{k}=\binom{n}{k}\binom{n-k}{i-k}$ to get:

$$\sum_{i=0}^n \binom{n}{i}\binom{i}{k}= \binom{n}{k}\sum_{i=0}^{n} \binom{n-k}{i-k}=\binom{n}{k}2^{n-k}$$

So, since $i^2=2\binom{i}{2}+\binom{i}{1}$ to get that $$\sum \binom{n}{i}i^2 = 2\binom{n}{2}2^{n-2} + \binom{n}{1}2^{n-1}$$

In general, $i^k = \sum_{j=0}^{k} a_j \binom{i}{j}$ for some sequence $a_j$, yielding the result:

$$\sum \binom{n}{i}i^k = \sum_{j=0}^k a_j\binom{n}{j}2^{n-j}$$

So it just amounts to finding the $a_j$ for each $k$.

$\endgroup$
1
$\begingroup$

Hint:

$$\binom{n}{i}i^{2}=\binom{n}{i}i\left(i-1\right)+\binom{n}{i}i=n\left(n-1\right)\binom{n-2}{i-2}+n\binom{n-1}{i-1}$$

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