Closed form for a formula with a summation over $i\binom{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.
 A: Write the numerator (after replacing the upper bound by $n$ or $n-k+1$, which I suppose was intended) as $\sum_{i=0}^n\binom i1\binom{n-i}{k-1}$. This summation then gives $\binom{n+1}{k+1}$ because of the more general formula
$$
\sum_{i=0}^k\binom im\binom{k-i}n=\binom{k+1}{m+n+1}
$$
that I mentioned with a combinatorial proof in this answer; put $(k,m,n):=(n,1,k-1)$ to get the special case needed here.
The proof specialises for this special case $\sum_{i=0}^n\binom i1\binom{n-i}{k-1}=\binom{n+1}{k+1}$ as follows. Locate, in the subset of $k+1$ elements out of $n+1$ for the right hand side, the second-smallest element, and let $i$ be the number of elements strictly smaller than that element. Then $\binom i1$ choices remain for the smallest element, and $\binom{n-i}{k-1}$ choices for the set of $k-1$ larger elements, and all possibilities are counted by the left hand side.
All in all your formula simplifies to $\left.\binom{n+1}{k+1}\right/\binom nk=\frac{n+1}{k+1}$.
A: 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$)
A: I am very bad in combinatorics (as in so many other areas) so I shall not prove anything. 
Intrigued by the expression (almost by the upper bound for the summation) and using a CAS, what was found is that  $$\sum_{i=1}^{n+k-1} i \binom{n-i}{k-1}=\frac{(k-1) \binom{-k}{k-1} \Big(k (k+n-1)+n+1\Big)+n (n+1) \binom{n-1}{k-1}}{k (k+1)}$$ where appears a generalized binomial coefficient $\binom{-k}{k-1}$.
Hoping this could be of some use.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{{\ds{\sum_{j\ =\ 1}^{n\ +\ k\ -\ 1}j{n - j \choose k - 1}}\over
     \ds{n \choose k}}:\ {\large ?}.\qquad}$ Lets $\ds{\quad n + k - 1 \equiv m}$.

\begin{align}&\color{#66f}{\large\sum_{j\ =\ 1}^{m}j{n - j \choose k - 1}}
=\sum_{j\ =\ 1}^{m}j\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{n - j} \over z^{k}}
\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}
{\pars{1 + z}^{n} \over z^{k}}\sum_{j\ =\ 1}^{m}j\pars{1 \over z + 1}^{j}
\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}
{\pars{1 + z}^{n} \over z^{k}}\bracks{%
{1 + z \over z^{2}} - {\pars{1 + z}^{-m + 1} \over z^{2}}
-m\,{\pars{1 + z}^{-m} \over z}}\,{\dd z \over 2\pi\ic}
\\[5mm]&={n + 1 \choose k + 1} - {n - m + 1 \choose k + 1} - m{n - m \choose k}
\\[5mm]&=\color{#66f}{\large{n + 1 \choose k + 1} - {2 - k \choose k + 1}
-\pars{n + k - 1}{1 - k \choose k}}\,,\qquad
\boxed{\ds{\quad n + k \geq 2\quad}}
\end{align}
