I want to know how to simplify the following sum (given $i, n \in \mathbb{N}$):
$$ \sum_{k=1}^i \frac{k}{n-k} \frac{\binom{i-1}{k-1}}{\binom{n-1}{k-1}}\ . $$
$\binom{a}{b}$ is a binomial coefficient. WolframAlpha says this equals $\frac{n}{(n-i+1)(n-i)}$, but it doesn't show how to calculate this step-by-step. I tackled to solve this for a day, but I couldn't figure out. Could you let me know an approach?
Note: This sum is needed to calculate a complexity of Chang and Roberts algorithm.
Let's start by simplifying the summand \begin{eqnarray*} \frac{k}{n-k} \frac{\binom{i-1}{k-1}}{\binom{n-1}{k-1}} &=& \frac{(i-1)!}{(i-k)!} \frac{(n-k)!}{(n-1)!} \frac{k}{n-k} \\ &=& \frac{(i-1)!(n-i-1)!}{(n-1)!} k \frac{(n-k-1)!}{(i-k)! (n-i-1)!} \\ &=& \frac{(i-1)!(n-i-1)!}{(n-1)!} k \binom{n-k-1}{i-k}. \\ \end{eqnarray*} Now do the coefficient trick $\binom{n-k-1}{i-k}= [x^{i-k}]:(1+x)^{n-k-1} =[x^i]: x^k (1+x)^{n-k-1}$ \begin{eqnarray*} \sum_{k=1}^i \frac{k}{n-k} \frac{\binom{i-1}{k-1}}{\binom{n-1}{k-1}} &=& \frac{(i-1)!(n-i-1)!}{(n-1)!} [x^i]: \sum_{k=1}^i k x^k (1+x)^{n-k-1} \\ &=& \frac{(i-1)!(n-i-1)!}{(n-1)!} [x^i]: \sum_{k=1}^{\infty} k x^k (1+x)^{n-k-1} \\ &=& \frac{(i-1)!(n-i-1)!}{(n-1)!} [x^i]: \frac{\frac{x}{1+x} (1+x)^{n-1}}{(1-\frac{x}{1+x})^2} \\ &=& \frac{(i-1)!(n-i-1)!}{(n-1)!} [x^i]: x(1+x)^n \\ &=& \frac{(i-1)!(n-i-1)!}{(n-1)!} \binom{n}{i-1} \\ &=& \frac{n}{(n-i+1)(n-i)}. \end{eqnarray*}