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*}

  • $\begingroup$ 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)$? $\endgroup$ – Socho Mar 10 '18 at 0:21
  • $\begingroup$ Maybe lost $k$ in the first line of the latter equations. $\endgroup$ – Socho Mar 10 '18 at 0:30
  • 1
    $\begingroup$ @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$ $\endgroup$ – Donald Splutterwit Mar 10 '18 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.