1
$\begingroup$

I encountered a problem as follows:

Show that $\sum^n_{k=0}\binom{n}{k} \binom{m}{k}^{-1} = \frac{m+1}{m+1-n}$ for $m\geq n$.

I wanted to use the binomial inversion formula, but I don't know where to start since the RHS is not a polynomial.

Any help would be appreciated.

$\endgroup$
3
$\begingroup$

HINT: Notice that

$$\frac{m+1}{m+1-n}\binom{m}n=\frac{m+1}{m-n+1}\binom{m}{m-n}=\binom{m+1}{m-n+1}\;,$$

something relatively nice, so let’s see if we can evaluate $\binom{m}n$ times the summation.

$$\begin{align*} \binom{m}n\sum_{k=0}^n\binom{n}k\binom{m}k^{-1}&=\sum_{k=0}^n\left(\frac{m!}{n!(m-n)!}\cdot\frac{n!}{k!(n-k)!}\cdot\frac{k!(m-k)!}{m!}\right)\\ &=\sum_{k=0}^n\frac{(m-k)!}{(m-n)!(n-k)!}\\ &=\sum_{k=0}^n\binom{m-k}{m-n}\\ &=\sum_{k=m-n}^m\binom{k}{m-n}\;. \end{align*}$$

(In each of the last two summations the upper number runs through the integers from $m-n$ to $m$ inclusive; it just does so in opposite orders.) Now use the hockey stick identity and a little algebra, and you’re home free.

$\endgroup$

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.