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
  • 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$ Nov 4, 2016 at 16:06
  • $\begingroup$ Differentiate the series $(1+x)^n$ wrt to $x$ twice to get your sum. $\endgroup$
    – SirXYZ
    Nov 4, 2016 at 16:11

3 Answers 3

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .