Show that $\sum_{i=0}^l \dfrac{{l\choose i}}{{n\choose k + i}} = \dfrac{n+1}{(n-l+1) {n-l\choose k}}$

Question

Show that $\displaystyle\sum_{i=0}^l \dfrac{{l\choose i}}{{n\choose k + i}} = \dfrac{n+1}{(n-l+1) {n-l\choose k}}$ for all $k,l, n\geq 0$ with $k+l \leq n.$

The $k+l\leq n$ part doesn't seem that important. The claim clearly holds for $n=0,$ and in that case $k$ and $l$ must both be zero. I think the claim can be shown by induction, but I'm not sure how to do so; I'm not sure how to use the inductive hypothesis to prove the inductive step. The sum on the LHS is not always an integer, so finding a combinatorial argument doesn't seem very feasible. For $n = 1,$ we can have $(k,l) = (0,0), (1,0), (0,1),$ and in each case the sum holds. Perhaps multiplying both sides by a number (idk ${n-l\choose k}$) might be useful?

Answer 1

Here is a hint for a combinatorial approach: Suppose there are $n+1$ balls in a bag. $l$ of them are blue, and $n+1-l$ of them are red. You draw without replacement until you get the $(k+1)$st red ball, and then you stop. What is the probability that you drew $i$ blue balls?

One way to compute this probability is to first note that you need to draw $i$ blue balls and $k$ red balls in some order, and then end with one more red ball. This is $\frac{\binom{l}{i} \binom{n+1-l}{k}}{\binom{n+1}{k+i}} \cdot \frac{n+1-l-k}{n+1-k-i}$, which can be shown to equal $\frac{\binom{l}{i} \binom{n-l}{k}}{\binom{n}{k+i}} \cdot \frac{n+1-l}{n+1}$ by algebraic manipulation, since $\binom{n+1}{k+i}/\binom{n}{k+i} = \frac{n+1}{n+1-k-i}$ and $\binom{n+1-l}{k}/\binom{n-l}{k} = \frac{n+1-l}{n+1-l-k}$.

Alternatively, you can argue that by symmetry this probability is equivalent to the probability of first drawing a blue ball, and then drawing $i$ blue balls and $k$ red balls in some order. This immediately gives you $\frac{\binom{l}{i} \binom{n-l}{k}}{\binom{n}{k+i}} \cdot \frac{n+1-l}{n+1}$.