Cómo calcular esta suma de fracciones de los coeficientes binomiales?

Question

Quiero saber cómo simplificar la siguiente suma (dado $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}$ es un coeficiente binomial. WolframAlpha dice que esto es igual a $\frac{n}{(n-i+1)(n-i)}$, pero no muestra cómo calcular este paso-por-paso. Yo abordó a resolver esto por un día, pero yo no podía entender. Podría usted, hágamelo saber un enfoque?

Nota: Esta cantidad es necesaria para calcular la complejidad de Chang y Roberts algoritmo.

Answer 1

Vamos a empezar por la simplificación sumando \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*} Ahora el coeficiente de engañar a $\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*}