Binomial summation $\sum\binom nkk^2$

Question

Question:

Find $$\sum_{k=0}^n\binom nkk^2$$

I know how to do $$\sum_{k=0}^n\binom nkk=n\space2^{n-1}$$

I tried applying same thing and reached $$\sum_{k=0}^n\binom nkk^2=n\sum_{k=0}^n\binom{n-1}{k-1}k$$

How to proceed?

Answer 1

Here's one way to do it:

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

Plugging in $x = 1$ gives that the sum of the binomial coefficients is $2^n$. Notice that $$x \frac{d}{dx} \left(x \frac{d}{dx} \left( (1 + x)^n\right) \right) = \sum_{k = 0}^n k^2 \binom{n}{k} x^k .$$

Computing the left-hand side and evaluating at $x = 1$ will give you the answer.

Answer 2

There are $n$ people. You want to select some of them to form a committee. Amongst the committee members, you choose a person to be the president. You also pick from the committee members one person (not necessarily different from the president) to be the treasury. Thus, if the committee consists of $k$ members, then the number of ways to pick the president and the treasury is $k^2$. That is, the total number of ways to pick the committee and the two extra positions is $$\sum_{k=0}^n\,k^2\,\binom{n}{k}\,.$$

On the other hand, you can pick the president and the treasury first. In the case that the president and the treasury are different, there are $n$ ways to choose the president, $n-1$ ways to pick the treasury, and $2^{n-2}$ ways to select the remaining committee members, whence there are $n(n-1)\,2^{n-2}$ ways in total. If the president is the same as the treasury, then there are $n$ ways to choose this person for two positions, and $2^{n-1}$ ways to complete the committee, making $n\,2^{n-1}$ ways in total.

Combining the two ways of counting, we conclude that $$\sum_{k=0}^n\,k^2\,\binom{n}{k}=n(n-1)\,2^{n-2}+n\,2^{n-1}=n(n+1)\,2^{n-2}\,.$$ The claim is now proven.

Answer 3

From your procedure:

$$\sum_{k=0}^n\binom nkk^2=n\sum_{k=1}^n\binom{n-1}{k-1}{(k\color{red}{-1+1})} = n\left( (n-1)\sum_{k=2}^{n} \binom{n-2}{k-2}+\sum_{k=1}^{n} \binom{n-1}{k-1}\right)$$

The sum is thus similar to

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

Answer 4

You can also give a combinatorial argument (based on A. Engel's book on problem solving): the sum counts the number of ways to choose a committee from a group of $n$ people, and then appoint a chairman and a secretary (where they could be appointed to the same person). If we first choose the chairman and the secretary, we consider two cases. If one person is both chariman and secretary, you can choose him/her in $n$ ways, and then the rest of the committee can be chosen in $2^{n - 1}$ ways. If they are different persons, you can choose them in $n(n - 1)$ ways and then select the rest of the committee in $2^{n - 2}$ ways. This gives $$ n 2^{n - 1} + n(n - 1)2^{n - 2} = n(n + 1)2^{n - 2}. $$ Hence, we have the equality $$ \sum_{k = 0}^n {n \choose k} k^2 = n(n + 1)2^{n - 2}. $$

EDIT: For more examples/information/exercises on combinatorial arguments for this type of sums: Chapter 5 of Engel's Problem-Solving Strategies (you can find a pdf online).

Answer 5

A probabilistic approach.

Let $X_i$ be iid Bernoulli trials with $P(X_i=1)=1/2$ for $i=1,\dotsc,n$. Then $X=X_1+\dotsb+X_n$ follows a Binomial distribution with $n$ trials and probability of success $1/2$ i.e. $$ P(X=k)=\binom{n}{k}2^{-n}\quad(0\leq k\leq n) $$ In particular $EX_i=P(X_i=1)=1/2$, and $X_i^2=X_i$ so $EX_i^2=EX_i$ and thus $\text{Var}(X_i)=EX_i^2-(EX_i)^2=1/4$ for all $i$. Moreover, $$ \text{Var}(X)=\sum_{i=1}^n\text{Var}(X_i)=n(1/4)=n/4;\quad EX=\sum_{i=1}^nEX_i=n/2 \tag{0} $$ since the $X_i$ are independent and identically distributed.

Notice that $$ EX^2=2^{-n}\sum_{k=0}^n\binom{n}{k}k^2\tag{1} $$ but from (0), we have that $$ EX^2=\text{Var}(X)+(EX)^2=\frac{n(n+1)}{4}\tag{2} $$ whence (1) and (2) imply that $$ \sum_{k=0}^n\binom{n}{k}k^2=2^nEX^2=2^{n-2}n(n+1). $$

Answer 6

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

Answer 7

Note that $k^2 = k(k-1)+k$. Use this fact together with the following properties of binomials: $$ k \cdot \binom{n}{k} = k \cdot \frac{n!}{k! (n-k)!} = n \cdot \frac{(n-1)!}{(k-1)! (n-k)!} = n \cdot \binom{n-1}{k-1} $$ Similarly: $$ k(k-1) \cdot \binom{n}{k} = n(n-1) \cdot \binom{n-2}{k-2} $$

Answer 8

Hint:

$$k^{r+1}=k(k-1)\cdots(k-r)+A_1k(k-1)\cdots(k-r+1)+\cdots+A_rk$$ where $A_i,1\le i\le r$ are arbitrary constants

$$\binom nkk^2=\cdots=\dfrac{n!k(k-1)}{(n-k)!k!}+\dfrac{n!k}{(n-k)!k!}$$

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

Now use $$(1+1)^m=\sum_{r=0}^m\binom mr$$

Little Generalization:

For $r=2,$ $$k^3=k(k-1)(k-2)+A_1k(k-1)+A_2k$$

$k=1\implies A_2=1,k=2\implies2A_1+2A_2=8$

$$\binom nkk^3=n(n-1)(n-2)\binom{n-3}{k-3}+4n(n-1)\binom{n-2}{k-2}+n\binom{n-1}{k-1}$$

Answer 9

Using Formula :

$$r^2\binom{n}{r} ＝n(n-1)\binom{n-2}{r-2}＋n\binom{n-1}{r-1}$$

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

Answer 10

Mathematica

f@r_ := Sum[Binomial[n, k]*k^r, {k, 0, n}] // FullSimplify
f /@ Range[1, 10, 1] // MatrixForm

The results of $\sum\limits_{k=0}^n k^r \binom{n}{k}$ for r=1..=10 are:

$$ \begin{pmatrix} 2^{n-1} n \\ 2^{n-2} n (n+1) \\ 2^{n-3} n^2 (n+3) \\ n \, _4F_3(2,2,2,1-n;1,1,1;-1) \\ n \, _5F_4(2,2,2,2,1-n;1,1,1,1;-1) \\ n \, _6F_5(2,2,2,2,2,1-n;1,1,1,1,1;-1) \\ n \, _7F_6(2,2,2,2,2,2,1-n;1,1,1,1,1,1;-1) \\ n \, _8F_7(2,2,2,2,2,2,2,1-n;1,1,1,1,1,1,1;-1) \\ n \, _9F_8(2,2,2,2,2,2,2,2,1-n;1,1,1,1,1,1,1,1;-1) \\ n \, _{10}F_9(2,2,2,2,2,2,2,2,1-n;1,1,1,1,1,1,1,1,1;-1) \end{pmatrix} $$