Binomial Formula Combinatorial Proof

Question

Find a formula (not involving $\sum$) for the function $\mathbb{N} \to \mathbb{N}$ given by:

$$f(n):= \sum\limits_{k = 0}^n {n \choose k} k^2.$$

Current thinking:

To get the formula for $f(n):= \sum\limits_{k = 0}^{n} {n \choose k} {k}$, I differentiated which gives

$$\frac{\mathrm d}{\mathrm dx}(1+x)^n = n(1+x)^{n-1}$$ $$\frac{d}{dx}\sum\limits_{k = 0}^{n} {n \choose k} {k} = \sum\limits_{k = 0}^{n} {n \choose k} {kx^{k-1}}$$

Can I just differentiate twice in a similar manner if I wanted to get $f(n):= \Sigma_{k = 0}^{n} {n \choose k} {k^2}$?

Answer 1

As alluded to in the comments, your current approach that you have added is correct and will get you to the right answer. Complete the process by a multiplication by $x$ and then differentiating by $x$ once more. Finally, plugging in $x=1$ will allow you to see the original sum you were after.

$\frac{d}{dx}\left(nx(1+x)^{n-1}\right) = n(nx+1)(x+1)^{n-2} = \sum\limits_{k=0}^n\binom{n}{k}k^2x^{k-1}$

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

---

Continuing from my suggestion: Consider counting how many committees of any size from n people are possible where there is a president of the committee and a treasurer for the committee but the president can be the same person as the treasurer. Consider counting by breaking into cases based on the size of the committee and choosing the president and treasurer from among those picked. Compare to your sum. Find a different way to count this scenario.

The first method of counting yields exactly the sum from your question. For an alternate method of counting, consider choosing the president first from all $n$ available people. Now, break into cases based on whether or not the treasurer is the same person as the president. In the case they are the same person, for the remaining $(n-1)$ people choose whether they are included as a committee member or not for a total of $2^{n-1}$ ways to expand the committee. In the case they are not the same person, choose who that other person was and then for the remaining $(n-2)$ people choose whether they are included or not. This gives an answer of:

$$n2^{n-1}+n(n-1)2^{n-2}$$

As both ways of counting successfully and correctly counted the same scenario, their expressions must be equal.

You can check with a bit of algebra that this is in fact equal to the same answer as the other method.

Answer 2

You're approach is fine. You've got your question answered.

An alternative way, using probability.

$B(n,k)=2^{-n} \binom{n}{k}$ corresponds to the Binomial distribution with $p=1/2$ (probability that $n$ fair coins give $k$ heads). Then, calling $X$ the random variable that follows that distribution we have

$$ \sum_{k=0}^{n} k^2 B(n,k)=E[X^2] = Var(X)+(E[X])^2=n p (1-p) + (np)^2=\frac{n}{4}+\frac{n^2}{4}$$

Hence your sum is

$$\sum\limits_{k = 0}^n {n \choose k} k^2 = 2^{n-2} (n + n^2)$$

Answer 3

Here's a fun way to get every power sum

$$f_r(n) = \sum_{k=0}^n {n \choose k} k^r$$

simultaneously. For fixed $n$ we can arrange them into an exponential generating function

$$\begin{align*} \sum_{r \ge 0} f_r(n) \frac{x^r}{r!} &= \sum_{k=0}^n {n \choose k} \sum_{r \ge 0} k^r \frac{x^r}{r!} \\ &= \sum_{k=0}^n {n \choose k} e^{kx} \\ &= (e^x + 1)^n \\ &= (2 + (e^x - 1))^n. \end{align*}$$

The point of the funny rewrite $e^x + 1 = 2 + (e^x - 1)$ is that the powers of $e^x - 1$ are well-understood; $\frac{(e^x - 1)^k}{k!}$ is the exponential generating function for partitions of a set into $k$ non-empty subsets, which means it can be expressed in terms of Stirling numbers of the second kind, giving

$$(e^x - 1)^k = k! \sum_{r \ge 0} \left\{ {r \atop k} \right\} \frac{x^r}{r!}$$

where $\left\{ {r \atop k} \right\}$ is the number of partitions of a set of size $r$ into $k$ non-empty subsets. Now binomial expanding $(2 + (e^x - 1))^n$ gives

$$\sum_{r \ge 0} f_r(n) \frac{x^r}{r!} = \sum_{k=0}^n {n \choose k} 2^{n-k} k! \sum_{r \ge 0} \left\{ {r \atop k} \right\} \frac{x^r}{r!}$$

which gives

$$\boxed{ f_r(n) = \sum_{k=0}^r 2^{n-k} (n)_k \left\{ {r \atop k} \right\} }$$

where $(n)_k = n(n-1) \dots (n-k+1) = {n \choose k} k!$ is the falling factorial. Note that the sum now only goes from $0$ to $r$; that is, for fixed $r$ it now only has a bounded number of terms. Also, the $k = 0$ term vanishes unless $r = 0$ since a non-empty subset can't be partitioned into zero sets. The case $r = 2$ gives

$$f_2(n) = 2^{n-1} n + 2^{n-2} n(n-1)$$

as computed by other answers, but we can now also easily do $r = 3$ (for example), which gives

$$f_3(n) = 2^{n-1} n + 3 \cdot 2^{n-2} n(n-1) + 2^{n-3} n(n-1)(n-2).$$

The $3$ in the middle is $\left\{ {3 \atop 2} \right\}$.

This result can alternatively be derived by instead evaluating the sums $\sum {n \choose k} {k \choose r}$, then writing $k^r$ as a linear combination of ${k \choose r}$, which also involves Stirling numbers, and a committee-counting argument also works and is basically equivalent.

Answer 4

Hint: We can also use the binomial identities \begin{align*} \binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}\qquad\mathrm{and}\qquad \binom{n}{k}=\frac{n(n-1)}{k(k-1)}\binom{n-2}{k-2} \end{align*} and start with \begin{align*} \sum_{k=0}^n\binom{n}{k}k^2=\sum_{k=2}^n\binom{n}{k}k(k-1)+\sum_{k=1}^n\binom{n}{k}k \end{align*}