Return to Revisions

This can be proved by induction on $m$ (for all $n$). That is, we want to prove by induction on $m \geq 0$ that $$ \binom{m+n}{n} \sum_{k=0}^m \binom{m}{k} \frac{n(-1)^k}{n+k} = 1 $$ for all $n \geq 1$. When $m = 0$ the left side is 1 for all $n$. If the above equation holds for $m$, then we want to show $$ \binom{m+1+n}{n} \sum_{k=0}^{m+1} \binom{m+1}{k} \frac{n(-1)^k}{n+k} \stackrel{?}{=} 1 $$ for all $n$. In the sum, split off $k = 0$ from the rest and for $k \geq 1$ rewrite $\binom{m+1}{k}$ as $\binom{m}{k-1} + \binom{m}{k}$: \begin{eqnarray*} \sum_{k=0}^{m+1} \binom{m+1}{k} \frac{n(-1)^k}{n+k} &=& 1 + \sum_{k=1}^{m+1} \binom{m}{k-1}\frac{n(-1)^k}{n+k} + \sum_{k=1}^{m+1}\binom{m}{k}\frac{n(-1)^k}{n+k} \\ & = & 1+\sum_{k=0}^{m} \binom{m}{k}\frac{n(-1)^{k+1}}{n+k+1} + \sum_{k=1}^{m}\binom{m}{k}\frac{n(-1)^k}{n+k}. \end{eqnarray*} Absorb the 1 into the second sum as a term at $k=0$ and massage the first sum to make it look like a sum of the type we care about with $n+1$ in place of $n$: \begin{eqnarray*} \sum_{k=0}^{m+1} \binom{m+1}{k} \frac{n(-1)^k}{n+k} & = & \sum_{k=0}^{m} \binom{m}{k}\frac{n(-1)^{k+1}}{n+k+1} + \sum_{k=0}^{m}\binom{m}{k}\frac{n(-1)^k}{n+k} \\ & = & -n\sum_{k=0}^{m} \binom{m}{k}\frac{(-1)^{k}}{(n+1)+k} + \sum_{k=1}^{m}\binom{m}{k}\frac{n(-1)^k}{n+k} \\ & = & \frac{-n}{n+1}\sum_{k=0}^{m} \binom{m}{k}\frac{(n+1)(-1)^{k}}{(n+1)+k} + \sum_{k=0}^{m}\binom{m}{k}\frac{n(-1)^k}{n+k}. \end{eqnarray*} By induction (on $m$) the first sum is $1/\binom{m+n+1}{n+1}$ and the second sum is $1/\binom{m+n}{n}$. Therefore $$ \binom{m+1+n}{n}\sum_{k=0}^{m+1} \binom{m+1}{k} \frac{n(-1)^k}{n+k} = \frac{-n}{n+1}\frac{\binom{m+1+n}{n}}{\binom{m+n+1}{n+1}} + \frac{\binom{m+1+n}{n}}{\binom{m+n}{n}}. $$ Writing the binomial coefficients as ratios of factorials and simplifying, the first term is $-n/(m+1)$ and the second term is $(m+n+1)/(m+1)$. Add them together and you get $1$.