Let $n$ be an integer.

Calculate

$$
\sum_{k=0}^{n} k^{2}\binom{n}{k}
$$
In fact, it is easier to calculate the following sum:

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

Then it remains to notice that

$$
\begin{aligned}
\sum_{k=0}^{n} k^{2}\binom{n}{k} & =\sum_{k=0}^{n}(k(k-1)+k)\binom{n}{k} \\
& =\left(\sum_{k=2}^{n} k(k-1)\binom{n}{k}\right)+\left(\sum_{k=1}^{n} k\binom{n}{k}\right)
\end{aligned}
$$

the second sum being $n 2^{n-1}$ by the previous exercise.

To calculate $\sum_{k=2}^{n} k(k-1)\binom{n}{k}$, we proceed similarly to exercise 3.

Using exercises 1 and 2

We have for all $k$ greater than 2

$$
\begin{aligned}
k(k-1)\binom{n}{k} & =(k-1)\left(k\binom{n}{k}\right) \\
& =(k-1)\left(n\binom{n-1}{k-1}\right) \\
& =n\left((k-1)\binom{n-1}{k-1}\right) \\
& =n\left((n-1)\binom{n-2}{k-2}\right)
\end{aligned}
$$

hence

$$
\begin{aligned}
\sum_{k=2}^{n} k(k-1)\binom{n}{k} & =\sum_{k=2}^{n} n(n-1)\binom{n-2}{k-2} \\
& =n(n-1) \sum_{k=2}^{n}\binom{n-2}{k-2} \\
& =n(n-1) \sum_{j=0}^{n-2}\binom{n-2}{j} \\
& =n(n-1) 2^{n-2}
\end{aligned}
$$

and thus we conclude that

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

Binomial Formula

We have for all real $x$, by the binomial formula

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

and since both sides are differentiable, by differentiating with respect to $x$ we obtain that for all real $x$

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

Similarly, by differentiating again with respect to $x$ we obtain that for all $x$

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

Evaluating at $x=1$, since $1+1=2$ we deduce that

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

Double Counting

We count in two different ways the number of possibilities to form a group of students with a leader and a deputy in a class of $n$ students.

Counting 1 First, we choose the leader, which gives $n$ possibilities.

Among the remaining students, we choose the deputy, which gives $n-1$ possibilities.

Then we choose any subset from the remaining $n-2$ students, which gives $2^{n-2}$ possibilities.

In total, we have

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

possibilities.

Counting 2 For a fixed $k$, we first look at how many such groups of size $k$ exist.

First, we choose the $k$ students, which gives $\binom{n}{k}$ possibilities.

Then we choose a leader from the group, which gives $k$ possibilities.

Next, we choose a deputy from the group members excluding the leader, which gives $k-1$ possibilities.

We thus obtain $k(k-1)\binom{n}{k}$ possibilities.

And by summing over all possible sizes, we finally have

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

And thus by double counting

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