# Is there a closed form expression for these combinatorial sums?

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

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

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.

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

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

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