multiple sums when lower bound depends on previous index Let $n, k, u$ and $s$ be positive integers with $u \le \min \left\{ n, k \right\}$.
I would like a 'closed form' representation for
\begin{equation}
  P \left( n, k, u, s \right) = \frac{1}{k^n} \sum_{i_1 = 1}^{k-u+1} \sum_{i_2 = i_1 + 1}^{k-u+2} \cdots \sum_{i_u = i_{u-1} + 1}^{k} s;
\end{equation}
that is, a representation without summation operators (e.g. in terms of Bernoulli numbers).
 A: With thanks to Ralph Bailey:
Let $Q_{n,k}\left( r \right)$ be the probability that, after $n$ agents have been assigned to arrival slots, exactly $r$ slots are occupied (have at least one occupant agent), where
$r \in \left\{  1, 2, 3, \ldots, k \right\}$.
Fix $k$ and suppress the subscript $k$, so $Q_{n,k} \left( r \right)$ is written $Q_{n} \left( r \right)$.
The only ways for exactly $r$ slots to be occupied after $n+1$ balls are if:


*

*exactly $r$ slots were occupied after $n$ agents (probability $Q_{n}\left( r \right)$), and one of these received the new ball (probability $\tfrac{r}{k}$); or if

*exactly $r-1$ slots were occupied after $n$ agents (probability $Q_{n}\left( r-1 \right)$), and one of the other $k - \left(  r-1 \right)$ received the new agent (probability $\frac{k-r+1}{k}$).


So we have the recurrence relation
\begin{equation} \label{eq:recur}
  Q_{n+1}\left( r \right) = Q_{n} \left( r \right) \frac{r}{k} + Q_{n} \left( r-1 \right) \frac{k-r+1}{k} \text{ where } N \geq 1, r \geq 1, k \geq 1.
\end{equation}
Denote Stirling numbers of the second kind by $\mathcal{S}_k^{\left( r \right)}$ and use the `falling factorial' notation $\left( x \right)_j \equiv \frac{x!}{\left( x-j \right)!}$. Then:
Theorem
Assuming that $n \geq 1$ and $k \geq 1$, we have
\begin{align*}
  Q_n \left( 0 \right) & = 0 \\
  Q_n \left( r \right) & =\mathcal{S}_{n}^{\left( r \right)} \frac{\left( k \right)_r}{k^n} \text{ for } r \geq 1.
\end{align*}
Proof
Evidently the statement $Q_n \left( 0 \right) = 0$ is correct. 
The proof of the second claim is by induction, starting at $Q_1 \left( 1 \right) = 1$.  Suppose the theorem is true for a particular $n$. We have to show only that it is then true for $n+1$. According to the recurrence relation,
\begin{align*}
   Q_{n+1}\left( r \right) & = Q_n \left( r \right) \frac{r}{k} + Q_n \left( r-1 \right) \frac{k-r+1}{k}\\
   & =\mathcal{S}_n^{\left( r \right)}\frac{\left( k \right)_r}{k^n} \times \frac{r}{k} + \mathcal{S}_n^{\left( r-1 \right)} \frac{\left( k \right)_{r-1}}{k^n} \times \frac{k-r+1}{k}\\
   & = \left( r \mathcal{S}_n^{\left( r \right)} + \left( k-r+1 \right) \frac{\left( k \right)_{r-1}}{\left( k \right)_r} \mathcal{S}_n^{\left( r-1 \right)} \right) \frac{ \left( k \right)_r}{k^{n+1}}.
\end{align*}
Now
\begin{equation}
  \left( k-r+1 \right) \frac{\left( k \right)_{r-1}}{\left( k \right)_r} = \left( k-r+1 \right) \frac{k!}{\left( k-r+1 \right)!} \frac{\left( k-r \right)!}{k!} = 1
\end{equation}
so that
\begin{equation}
  Q_{n+1} \left( r \right) = \left( r \mathcal{S}_n^{\left( r \right)} + \mathcal{S}_n^{\left( r-1 \right)} \right) \frac{\left(  k \right)_r}{k^{n+1}}.
\end{equation}
However the Stirling numbers of the second kind satisfy
\begin{equation}
  \mathcal{S}_{n+1}^{\left( r \right)} = r\mathcal{S}_n^{\left( r \right)} + \mathcal{S}_n^{\left( r-1 \right)}
\end{equation}
for $n \ge r \ge 1$ (Abramowitz & Stegun, p.825) so we get
\begin{equation}
  Q_{n+1}\left( r \right) = \mathcal{S}_{n+1}^{\left( r \right)} \frac{\left( k \right)_r}{k^{n+1}}.
\end{equation}
