MHB Sum of binomial coefficients multiplied by k^2

[alexmahone]

Evaluate [math]\sum\limits_{k=1}^{12} {12\choose{k}}k^2[/math]

The answer is 159744.

 

[MarkFL]

I would begin with:

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

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

We could begin with the binomial theorem and state:

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

Multiply through by $x$:

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

Differentiate w.r.t $x$:

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

$$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 $$\sum_{k=0}^n\left({n \choose k}\right)=(1+1)^n=2^n$$

And so we have:

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

Hence:

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

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

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

We could begin with the binomial theorem and state:

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

Multiply through by $x$:

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

Differentiate w.r.t $x$:

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

$$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 $$\sum_{k=0}^n\left({n \choose k}\right)=(1+1)^n=2^n$$

And so we have:

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

Hence:

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

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

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

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

$$(1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k\right)$$ once and set [math]x=1[/math].

 

[MarkFL]

In order to find a formula for:

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

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

$$(1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k\right)$$ once and set [math]x=1[/math].

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

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

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

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

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

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

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

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

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

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

And so, we may now write:

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