combinatorics - Closed form for a formula with a summation over $ibinom{n-i}{k-1}$, and combinatorial proof?

I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end.

$$\displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i \binom{n-i}{k-1}}{ \displaystyle{n \choose k}}$$

Is there any way to simplify the numerator so that the whole expression simplifies into a nice closed formula? A combinatorial approach would be greatly appreciated.

Answer

Consider the number of ordered pairs $(a, S)$ such that $S$ is a $k$-element subset of $\{1,2, \dots, n\}$ and $a \le \min S$.

One way of counting:

Fix $\min S$.

If $\min S = i$, the number of sets = $\binom{n-i}{k-1}$ (choose $k-1$ from $\{i+1, i+2, \dots, n\}$. For each such $S$, you have $i$ possibilities for $a$.

Thus the number of $(a,S)$ pairs = $\sum_{i=1}^{n-k+1} i\binom{n-i}{k-1}$

Now count that differently: either $a = \min S$ or not.

If $a \neq \min S$, then the number is $\binom{n}{k+1}$ (pick $k+1$ elements basically)

If $a = \min S$, the number is $\binom{n}{k}$.

Thus the numerator you seek is $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$

So your expression simplifies to $\dfrac{n+1}{k+1}$.

(Note, I have assumed you wanted the sum upto $n-k+1$)