# How to calculate this summation of fractions of binomial coefficients?

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*}
• Thanks for answering. What is the meaning of the symbol $[x^i] : f(x)$? Maybe... a coefficient of $x^i$ of a generating function $f(x)$? – Socho Mar 10 '18 at 0:21
• Maybe lost $k$ in the first line of the latter equations. – Socho Mar 10 '18 at 0:30
• @Socho If $f(x)=a_0+a_1 x+ \cdots + a_i x^i + \cdots$ then \begin{eqnarray*} a_i = [x^i]: f(x) \end{eqnarray*} and reads as aye eye equals the coefficient of ecks to the eye in the function eff, I refer to this as the coefficient trick. Secondly, you are right I had lost a $k$ ... I have edited now $\ddot \smile$ – Donald Splutterwit Mar 10 '18 at 19:08