Irish Mathematical Olympiad

By the symmetry of the binomial coefficients,
$$2 \sum_{k=0}^{n} k^j \binom{n}{k} = \sum_{k=0}^{n} (k^j + (n-k)^j) \binom{n}{k}.$$
Now
$$k^j + (n-k)^j = n^j \left( \left( \frac{k}{n} \right)^j + \left( 1 - \frac{k}{n} \right)^j \right) = n^j f_j \left( \frac{k}{n} \right),$$
where $f_j(x) = x^j + (1-x)^j$, $(0 \le x \le 1)$. By using the convexity of $x \mapsto x^j$, calculus methods or otherwise, it is easy to see that
$$\min \{f_j(x) : x \in [0, 1]\} = f_j\left(\frac{1}{2}\right) = 2^{1-j}, \quad j = 0, 1, \dots,$$
whence
$$2 \sum_{k=0}^{n} k^j \binom{n}{k} \ge n^j 2^{1-j} \sum_{k=0}^{n} \binom{n}{k} = n^j 2^{n+1-j},$$
from which the result follows.

First, if $j = 0, 1$ we get equalities $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ and $\sum_{k=0}^{n} k \binom{n}{k} = n 2^{n-1}$. The first follows from the Binomial Theorem and the second can be obtained by differentiating and evaluating at $x = 1$ the function
$$(1+x)^n = \sum_{k=0}^{n} x^k \binom{n}{k}.$$
Further differentiation leads to sums of $\sum_{k=0}^{n} k^j \binom{n}{k}$ for small values of $j$, but without a new idea (see Solution 3) it may run into the sand for large values of $j$. But viewing
$$\frac{n}{2} = 2^{-n} \sum_{k=0}^{n} k \binom{n}{k} = \frac{\sum_{k=0}^{n} k \binom{n}{k}}{\sum_{k=0}^{n} \binom{n}{k}}$$
as a convex sum, and using the convexity of $f(x) = x^j$, Jensen's inequality
$$f\left(\frac{n}{2}\right) \le 2^{-n} \sum_{k=0}^{n} f(k) \binom{n}{k} \quad \text{yields the result.}$$

The Stirling numbers of the second kind $\binom{j}{k}$ can be defined recursively as follows.
$$\begin{cases} \begin{pmatrix} 0 \\ 0 \end{pmatrix} = 1 & \text{and} \quad \begin{pmatrix} j \\ k \end{pmatrix} = 0 & \text{if } k < 0 \text{ or } k > j, \\ \begin{pmatrix} j+1 \\ k \end{pmatrix} = k \begin{pmatrix} j \\ k \end{pmatrix} + \begin{pmatrix} j \\ k-1 \end{pmatrix} & \text{if } j \ge 0 \text{ and } k \ge 0. \end{cases}$$
They satisfy the identity
$$x^j = \sum_{k=0}^{j} \begin{pmatrix} j \\ k \end{pmatrix} x^k$$
where $x^k$ stands for the product of $k$ factors $x(x-1)(x-2)\cdots(x-k+1)$, a so-called falling power. By convention, $x^0 = 1$. The proof of this identity is a simple induction (like the proof of the binomial theorem), see e.g. [1]. We now fix the value of $n$ and introduce the functions $f_0(x) = \left(\frac{1+x}{2}\right)^n$ and
$$f_k(x) = \frac{n(n-1)(n-2)\cdots(n-k+1)}{2^k} \cdot x^k \left(\frac{1+x}{2}\right)^{n-k}, \quad k=1,2,3\dots$$
Note that, with the notation introduced above, we have $f_k(1) = \frac{n^k}{2^k}$.
Let $D$ denote the differential operator $x^{\frac{d}{dx}}$. Its main feature for us is that $Dx^k = kx^k$. After $j$ applications of the operator $D$, the binomial theorem
$$(1+x)^n = \sum_{k=0}^{n} x^k \binom{n}{k} \quad \text{implies} \quad D^j ((1+x)^n) = \sum_{k=0}^{n} k^j x^k \binom{n}{k}$$
The desired inequality now reads as $D^j ((1+x)^n)|_{x=1} \ge 2^{n-j}n^j$ which can be rewritten as $D^j f_0|_{x=1} \ge \frac{n^j}{2^j}$.
It is easy to observe that $Df_0 = f_1$, $Df_1 = f_1 + f_2$ and in general that $Df_k = k f_k + f_{k+1}$ for $k \ge 0$. Using induction and the recursion for the Stirling numbers, this implies the key identity
$$D^j f_0 = \sum_{k=0}^{j} \binom{j}{k} f_k.$$
From above we obtain now the desired inequality
$$D^j f_0|_{x=1} = \sum_{k=0}^{j} \binom{j}{k} f_k(1) = \sum_{k=0}^{j} \binom{j}{k} \frac{n^k}{2^k} \ge \frac{1}{2^j} \sum_{k=0}^{j} \binom{j}{k} n^k = \frac{n^j}{2^j}.$$

The LHS counts the total number $N$ of ways of choosing a committee of any size from $n$ people and assigning $j$ distinct 'roles' $R_1, R_2, \dots, R_j$ to people in the committee (here any person can have multiple roles, and there can be more roles than committee members).
The LHS counts this by partitioning the count according to the size $k$ of the committee. For each $k$, we first choose a committee of size $k$ (there are $\binom{n}{k}$ ways to do this), and then we assign each role in turn (there are $k^j$ ways to assign the roles for each such chosen committee).
The RHS forms a lower bound on $N$. Consider first assigning the $j$ roles among the $n$ people - there are $n^j$ ways to do this. Next we consider 2 cases. First consider the case $j < n$. In this case, once the $j$ roles are assigned, at most $j$ people have roles assigned to them, and these people must therefore all be in the committee. There remain at least $n - j > 0$ people who may be either included in, or excluded from, the committee - this yields at least $2^{n-j}$ choices to complete the committee for each initial assignment of roles. Second, consider the case $j \ge n$. In this case, all people may have roles assigned, so that $N$ is lower bounded by $n^j$. But this in turn is greater than or equal to $2^{n-j}n^j$ since $2^{n-j} \le 1$. This proves the desired inequality.

We use strong induction on $j$. The induction statement is
$$S_j: \text{ for all non-negative integers } n, \sum_{k=0}^{n} k^j \binom{n}{k} \ge 2^{n-j} n^j.$$
First observe that $S_0: \sum_{k=0}^{n} \binom{n}{k} \ge 2^n$ is true, since both sides are equal. Assume $S_0, S_1, \dots, S_m$ are true. We want to prove
$$S_{m+1}: \sum_{k=0}^{n} k^{m+1} \binom{n}{k} \ge 2^{n-m-1} n^{m+1} \quad \text{for all } n \ge 0.$$
First note the binomial identity $k(\binom{n}{k}) = n(\binom{n-1}{k-1})$. So
$$\begin{align*} \sum_{k=0}^{n} k^{m+1} \binom{n}{k} &= \sum_{k=0}^{n} k^m n \binom{n-1}{k-1} = n \sum_{k=0}^{n-1} (k+1)^m \binom{n-1}{k} \\ &= n \sum_{k=0}^{n-1} \sum_{i=0}^{m} k^i \binom{m}{i} \binom{n-1}{k} = n \sum_{i=0}^{m} \binom{m}{i} \sum_{k=0}^{n-1} k^i \binom{n-1}{k} \\ &\ge n \sum_{i=0}^{m} \binom{m}{i} 2^{n-1-i} (n-1)^i = n 2^{n-1} \sum_{i=0}^{m} \binom{m}{i} \left(\frac{n-1}{2}\right)^i \\ &= n 2^{n-1} \left(1 + \frac{n-1}{2}\right)^m = n 2^{n-1-m} (n+1)^m \ge 2^{n-1-m} n^{m+1}. \end{align*}$$
This proves $S_{m+1}$ and hence the result follows by induction.