7
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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

$\endgroup$
3
  • $\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, 2018 at 0:21
  • $\begingroup$ Maybe lost $k$ in the first line of the latter equations. $\endgroup$
    – Socho
    Mar 10, 2018 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, 2018 at 19:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .