Sum of binomial coefficients multiplied by k^2

[alexmahone]

Evaluate \(\displaystyle \sum\limits_{k=1}^{12} {12\choose{k}}k^2\)

The answer is 159744.

 

[MarkFL]

I would begin with:

\(\displaystyle x^2\left(1+x^2\right)^n=\sum_{k=0}^n\left({n \choose k}\left(x^2\right)^{k+1}\right)\)

And then differentiating twice with respect to $x$, you should get the general formula you need. :)

 

[MarkFL]

Suppose we wish to find a formula for:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k\right)\)

We could begin with the binomial theorem and state:

\(\displaystyle (1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k\right)\)

Multiply through by $x$:

\(\displaystyle x(1+x)^n=\sum_{k=0}^n\left({n \choose k}x^{k+1}\right)\)

Differentiate w.r.t $x$:

\(\displaystyle x\left(n(1+x)^{n-1}\right)+(1)(1+x)^n=\sum_{k=0}^n\left({n \choose k}(k+1)x^{k}\right)\)

Letting $x=1$, we obtain:

\(\displaystyle n2^{n-1}+2^n=\sum_{k=0}^n\left({n \choose k}(k+1)\right)=\sum_{k=0}^n\left({n \choose k}k\right)+\sum_{k=0}^n\left({n \choose k}\right)\)

We should observe that \(\displaystyle \sum_{k=0}^n\left({n \choose k}\right)=(1+1)^n=2^n\)

And so we have:

\(\displaystyle n2^{n-1}+2^n=\sum_{k=0}^n\left({n \choose k}k\right)+2^n\)

Hence:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k\right)=n2^{n-1}\tag{1}\)

Now, use a similar approach to find a formula for:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k^2\right)\)

And you will find you can use the formula (1) I derived above.

 

[alexmahone]

Suppose we wish to find a formula for:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k\right)\)

We could begin with the binomial theorem and state:

\(\displaystyle (1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k\right)\)

Multiply through by $x$:

\(\displaystyle x(1+x)^n=\sum_{k=0}^n\left({n \choose k}x^{k+1}\right)\)

Differentiate w.r.t $x$:

\(\displaystyle x\left(n(1+x)^{n-1}\right)+(1)(1+x)^n=\sum_{k=0}^n\left({n \choose k}(k+1)x^{k}\right)\)

Letting $x=1$, we obtain:

\(\displaystyle n2^{n-1}+2^n=\sum_{k=0}^n\left({n \choose k}(k+1)\right)=\sum_{k=0}^n\left({n \choose k}k\right)+\sum_{k=0}^n\left({n \choose k}\right)\)

We should observe that \(\displaystyle \sum_{k=0}^n\left({n \choose k}\right)=(1+1)^n=2^n\)

And so we have:

\(\displaystyle n2^{n-1}+2^n=\sum_{k=0}^n\left({n \choose k}k\right)+2^n\)

Hence:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k\right)=n2^{n-1}\tag{1}\)

Now, use a similar approach to find a formula for:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k^2\right)\)

And you will find you can use the formula (1) I derived above.

In order to find a formula for:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k\right)\),

we just need to differentiate (w.r.t. x)

\(\displaystyle (1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k\right)\) once and set \(\displaystyle x=1\).

 

[MarkFL]

In order to find a formula for:

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k\right)\),

we just need to differentiate (w.r.t. x)

\(\displaystyle (1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k\right)\) once and set \(\displaystyle x=1\).

Yes, that works too and is simpler. Likewise, to find the formula you need, we could take:

\(\displaystyle \left(1+x\right)^n=\sum_{k=0}^n\left({n \choose k}x^{k}\right)\)

And differentiate twice, and let $x=1$ and (1) to get the result. What do you find?

 

[MarkFL]

We begin with:

\(\displaystyle \left(1+x\right)^n=\sum_{k=0}^n\left({n \choose k}x^{k}\right)\)

Differentiating twice w.r.t $x$, there results:

\(\displaystyle n(n-1)\left(1+x\right)^{n-2}=\sum_{k=0}^n\left({n \choose k}k(k-1)x^{k-2}\right)\)

Letting $x=1$, we have:

\(\displaystyle n(n-1)2^{n-2}=\sum_{k=0}^n\left({n \choose k}k^2\right)-\sum_{k=0}^n\left({n \choose k}k\right)\)

Using our previous result:

\(\displaystyle n(n-1)2^{n-2}=\sum_{k=0}^n\left({n \choose k}k^2\right)-n2^{n-1}\)

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k^2\right)=n(n-1)2^{n-2}+n2^{n-1}\)

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k^2\right)=n2^{n-2}\left((n-1)+2\right)\)

\(\displaystyle \sum_{k=0}^n\left({n \choose k}k^2\right)=n(n+1)2^{n-2}\)

And so, we may now write:

\(\displaystyle \sum_{k=0}^{12}\left({12 \choose k}k^2\right)=12(12+1)2^{12-2}=156\cdot1024=159744\)

 

[Euge]

Hello,

Here is an alternative to the calculus method displayed here. First write

$$\sum_{k = 1}^n \binom{n}{k}k^2 = n\sum_{k = 1}^n \binom{n-1}{k-1}k.\tag{*}$$

This holds due to the binomial identity

$$\binom{m}{r} = \frac{m}{r}\binom{m-1}{r-1}.$$

Using this binomial identity once more we obtain

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

By the binomial theorem,

$$\sum_{k = 2}^n \binom{n-2}{k-2} = \sum_{k = 0}^{n-2} \binom{n-2}{k} = (1 + 1)^{n-2} = 2^{n-2},$$

and

$$\sum_{k = 1}^n \binom{n-1}{k-1} = \sum_{k = 0}^{n-1} \binom{n-1}{k} = (1 + 1)^{n-1} = 2^{n-1}.$$

Hence

$$\sum_{k = 1}^n \binom{n-1}{k-1}k = (n-1)2^{n-2} + 2^{n-1},$$

and finally by (*),

$$\sum_{k = 1}^n \binom{n}{k}k^2 = n(n-1)2^{n-2} + n2^{n-1} = n[(n-1) + 2]2^{n-2} = n(n+1)2^{n-2}.$$