# Binomial coefficient identity

It seems to be nontrivial (to me) to show that the following identity holds: $$\binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} \frac {n(-1)^k}{n+k} = 1.$$ This quantity is related to the volume of the certain polytope.

• Look at $\int_0^1 (1-x)^m x^{n-1} dx$ and use the binomial theorem together with the beta integral. – Lucia Jan 10 '15 at 15:14
• Somewhat more elementary than the beta integral, whatever it is: use partial integration to reduce computing $\int_0^1 \left(1-x\right)^m x^{n-1} dx$ to computing $\int_0^1 \left(1-x\right)^{m+1} x^n dx$, and proceed by induction over $n$. This is purely algebraic. – darij grinberg Jan 10 '15 at 16:03
• You mean, to reduce $\int_0^1 (1-x)^m x^{n-1} dx$ to $\frac{m}{n} \int_0^1 (1-x)^{m-1} x^{n} dx$ using integration by parts, and so on..., right ? – hkju Jan 10 '15 at 21:58
• This identity implies that $$\sum_{k=0}^m \frac {n(-1)^k}{n+k} = \sum_{k=0}^n \frac {m(-1)^k}{m+k}$$. – hkju Jan 10 '15 at 22:19
• This identity is also a special case of Vandermonde's theorem. – Ira Gessel Jan 11 '15 at 6:11

This is a specialization at $x = n$ of the rational function identity $$\frac{1}{x(x+1)\cdots(x+m)} = \frac{1}{m!}\sum_{k=0}^m \binom{m}{k}\frac{(-1)^k}{x+k},$$ and this identity could be proved either by partial fractions with unknown coefficients and limits to find the coefficients (see my comment on Todd Trimble's answer) or by induction on $m$. For the inductive step, divide both sides of the above identity by $x+m+1$: $$\frac{1}{x(x+1)\cdots(x+m)(x+m+1)} = \frac{1}{m!}\sum_{k=0}^m \binom{m}{k}\frac{(-1)^k}{(x+k)(x+m+1)}.$$ Split up the right side by partial fractions to make it $$\frac{1}{m!}\sum_{k=0}^m \binom{m}{k}\frac{(-1)^k}{m+1-k}\left(\frac{1}{x+k} - \frac{1}{x+m+1}\right).$$ Break this into a sum of two terms: $$\frac{1}{m!}\sum_{k=0}^m \binom{m}{k}\frac{1}{m+1-k}\frac{(-1)^k}{x+k} - \frac{1}{m!}\left(\sum_{k=0}^m\binom{m}{k}\frac{(-1)^k}{m+1-k}\right)\frac{1}{x+m+1}.$$ Since $\binom{m}{k}/(m+1-k) = \binom{m+1}{k}/(m+1)$, the difference is $$\frac{1}{(m+1)!}\sum_{k=0}^m \binom{m+1}{k}\frac{(-1)^k}{x+k} - \frac{1}{(m+1)!}\left(\sum_{k=0}^m\binom{m+1}{k}(-1)^k\right)\frac{1}{x+m+1}.$$ The sum inside parentheses is $(1-1)^{m+1} - (-1)^{m+1} = (-1)^m$, so finally we have $$\frac{1}{x(x+1)\cdots(x+m)(x+m+1)} = \frac{1}{(m+1)!}\sum_{k=0}^m \binom{m+1}{k}\frac{(-1)^k}{x+k} - \frac{1}{(m+1)!}\frac{(-1)^m}{x+m+1}.$$ Since $-(-1)^m = (-1)^{m+1}$, we're done.

This is an elaboration of Lucia's comment. On the one hand, by the beta integral we have $$\int_0^1 (1-x)^m x^{n-1}\,dx = \frac{m!(n-1)!}{(m+n)!}=\frac{1}{n\binom{m+n}{n}}.$$ The same integral equals, by the binomial theorem, $$\int_0^1 (1-x)^m x^{n-1}\,dx = \int_0^1 \sum_{k=0}^m \binom{m}{k}(-1)^kx^{n+k-1}\,dx= \sum_{k=0}^m \binom{m}{k}\frac{(-1)^k}{n+k}.$$ Hence $$\sum_{k=0}^m\binom{m}{k}\frac{(-1)^k}{n+k}=\frac{1}{n\binom{m+n}{n}},$$ and the result follows.

• Without the knowledge on beta integral, one can get the value as grinberg's comments mentioned. – hkju Jan 11 '15 at 1:19
• @hkju: Yes, but I like the beta integral! Also, my first display is straightforward to prove directly, using induction and integration by parts. – GH from MO Jan 11 '15 at 3:13

My natural inclination would be to see this as an application of basic finite difference calculus. Essentially all of this is covered in Concrete Mathematics by Graham, Knuth, and Patashnik, so I'll just run through the highlights.

Given a sequence $f: \mathbb{N} \to \mathbb{R}$, we define $(\Delta f)(x) := f(x+1) - f(x)$. The operator $\Delta$ can be iterated and one has the useful formula

$$(\Delta^m f)(x) = \sum_{k=0}^m (-1)^{m-k} \binom{m}{k} f(x+k).$$

In finite difference calculus, the analogue of the power function $x^k$ (in ordinary calculus) is the falling power $x^{\underline{k}} := x(x-1)\ldots(x-k+1)$. Here $\Delta x^{\underline{k}} = k x^{\underline{k-1}}$. An easy way to see this is by reformulating the Pascal's triangle recurrence in the form

$$\Delta \frac{x^{\underline{k}}}{k!} = \frac{x^{\underline{k-1}}}{(k-1)!}.$$

Extrapolating from the exponential law $x^{\underline{m+n}} = x^{\underline{m}}(x-m)^{\underline{n}}$, negative falling powers are naturally defined by $x^{\underline{-k}} := \frac1{(x+k)(x+k-1)\ldots(x+1)}$, and the same finite difference formula $\Delta x^{\underline{k}} = k x^{\underline{k-1}}$ holds for all $k \in \mathbb{Z}$.

Now hold $n$ fixed and put $f(x) = \frac{n}{n+x} = n(x+n-1)^{\underline{-1}}$. We have $(\Delta^m f)(x) = (-1)^m n \cdot m! \cdot (x+n-1)^{\underline{-m-1}}$. Hence

$$\begin{array}{ccc} \sum_{k=0}^m (-1)^k \binom{m}{k} \frac{n}{n+k} & = & (-1)^m \sum_{k=0}^m (-1)^{m-k} \binom{m}{k} f(k) \\ & = & (-1)^m (\Delta^m f)(0) \\ & = & n \cdot m! \cdot (n-1)^{\underline{-m-1}} \\ & = & \frac{m!}{(m+n)(m+n-1)\ldots(n+1)} \end{array}$$

as was to be shown.

• In fact, when expressed as the rational function identity $\sum_{k=0}^m \binom{m}{k} (-1)^k/(x+k) = m!/(x(x+1)\cdots(x+m))$ this is equivalent (after changing $k$ to $m-k$ and replacing $x$ with $x-m$) to the rational function identity $\sum_{k=0}^m \binom{m}{k} (-1)^k/(x-k) = (-1)^mm!/(x(x-1)\cdots(x-m))$, which appears in the middle of the page en.wikipedia.org/wiki/Table_of_Newtonian_series with a sign error (which someone may fix after seeing this comment). – KConrad Jan 11 '15 at 4:10
• To prove that rational function identity, the rational function $\frac{1}{x(x+1)\cdots(x+m)}$ can be expanded by partial fractions as $\sum_{k=0}^m \frac{c_k}{x+k}$ for unknown constants $c_k$. For any $i$ from $0$ to $m$, multiply both sides by $x+i$ and take a limit as $x \rightarrow -i$: $c_i = \lim_{x \rightarrow -i} \frac{1}{x(x+1)\cdots(x+i-1)(x+i+1)\cdots(x+m)}$, which is $\frac{1}{(-1)^ii!}\cdot \frac{1}{(m-i)!} = \frac{(-1)^i}{m!}\binom{m}{i}$. – KConrad Jan 11 '15 at 4:17
• Yes, certainly @KConrad -- that's one nice way of looking at it. Another method is to use a finite difference analogue of the product rule. Speaking of Newtonian series and such, we also have (something like) $f(x) = \sum_{m \geq 0} (\Delta^m f)(0) \frac{x^{\underline{m}}}{m!}$ for a reasonable class of functions. All of this is further illuminated by passing to generating functions -- I recommend the book by Graham, Knuth, and Patashnik for anyone interested (can't find my copy at the moment). – Todd Trimble Jan 11 '15 at 4:25

Here is an even simpler take on this. Let $$F(m,n)=\binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} \frac {n(-1)^k}{n+k}.$$

Claim: If $m\geq 1$, then we have$$F(m,n)=F(m-1,n+1),$$ for all $n$.

proof: $$F(m,n)=\binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} (-1)^k \left(1-\frac{k}{n+k}\right)=\binom {m+n}{n} \sum_{k=0}^m \binom {m}{k} \frac {k(-1)^{k+1}}{n+k}$$ where I used the fact that $\sum_{k} \binom{m}{k}(-1)^k=0$ for $m\geq 1$. We can further say $$F(m,n)=\binom{(m-1)+(n+1)}{n+1}\sum_{r=0}^{m-1}\binom{m-1}{r}\frac{(n+1)(-1)^{r}}{n+1+r},$$ where I basically just substituted $r=k-1$ and rearranged the terms. However this last sum is just $F(m-1,n+1)$.

Moreover, it is very easy to check that $F(0,m+n)=1$.

• $\sum_{k=0}^m \binom{m}{k}(-1)^k$ is not $0$ if $m = 0$. – KConrad Jan 11 '15 at 1:55
• True, but I'm also only using it whenever $m\geq 1$. :) – Gjergji Zaimi Jan 11 '15 at 1:58
• Then you should say before you get to the step that you're taking $m \geq 1$ when doing the simplification, since the result itself is true at $m=0$. – KConrad Jan 11 '15 at 2:05
• @GHfromMO, It is actually correct as it is. If you notice the $\binom{n+m}{n}$, became $\binom{n+m}{n+1}$, and that's where the ${n+1}$ in the numerator came from. – Gjergji Zaimi Jan 11 '15 at 3:17
• @GjergjiZaimi: You are right. I checked this in my head, but stopped half-way :-) – GH from MO Jan 11 '15 at 3:27

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=0}^{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$.

This is an automated proof (but rigorous) based on the Wilf-Zeilberger method, for which Zeilberger wrote a code freely available here. Different versions are already built into Maple and Mathematica.

Let $F(m,k):=\binom{m+n}n\binom{m}k\frac{n(-1)^k}{n+k}$ and your sum $f(m):=\sum_{k=0}^mF(m,k)$. Then, the above algorithm generates a WZ-mate $G(m,k):=-\binom{m+n}n\binom{m+1}k\frac{n(-1)^k}{(m+1)^2}$ satisfying the equation $$F(m+1,k)-F(m,k)=G(m,k+1)-G(m,k). \tag1$$ To verify (1), divide through by $F(m,k)$ and simplify. The result is a simple rational function equality. Now, sum (1) over all integers $k$ and note that each summand has compact support; i.e. a finite sum. Furthermore, the RHS vanishes up on this summation process.

The outcome is $f(m+1)-f(m)=0$; that is, $f(m)$ is a constant in $m$.

If we set $m=0$, we get $f(0)=1$. Hence, $f(m)=1$ for all $m\geq0$. The proof is complete.

When this question was first posted I wrote two solutions, one a direct induction and the other using a rational function identity. Recently, in the course of recentering a power series around a zero in two ways, I realized that the compatibility of the two methods is equivalent to a nonobvious identity... exactly the one posted here. It's presented below as a calculation with formal power series in two indeterminates.

Let $F(X) = \sum_{m \geq 0} a_mX^m$ in $\mathbf Z[[X]]$. The difference $F(X) - F(Y)$ in $\mathbf Z[[X,Y]]$ vanishes when $Y = X$, so it is divisible by $X-Y$. Let's factor out $X-Y$ from $F(X) - F(Y)$ in two ways.

Method 1: Factoring $X - Y$ out of each difference $X^m - Y^m$ and changing the order of summation, \begin{eqnarray*} F(X) - F(Y) & = & \sum_{m \geq 1} a_m(X^m-Y^m) \\ & = & (X-Y)\sum_{m\geq 1} a_m\sum_{\ell = 0}^{m-1}X^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq \ell+1}a_mX^\ell Y^{m-1-\ell} \\ & = & (X-Y)\sum_{\ell \geq 0}\sum_{m \geq 0}a_{m+\ell+1}X^\ell Y^{m}. \end{eqnarray*}

Method 2: Let's expand $F(X)$ as a series centered at $Y$ instead of $0$ and change the order of summation: \begin{eqnarray*} F(X) & = & \sum_{m \geq 0} a_m(X-Y+Y)^m \\ & = & \sum_{m \geq 0} a_m\sum_{k=0}^m \binom{m}{k}(X-Y)^kY^{m-k} \\ &= & \sum_{k \geq 0} \left(\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}\right)(X-Y)^k. \end{eqnarray*} The term at $k = 0$ is $\sum_{m\geq 0} a_mY^m = F(Y)$, so \begin{eqnarray*} F(X) - F(Y) & = & (X-Y)\sum_{k \geq 1}\sum_{m \geq k} a_m\binom{m}{k}Y^{m-k}(X-Y)^{k-1} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}(X-Y)^{k} \\ & = & (X-Y)\sum_{k \geq 0} \sum_{m \geq k+1} a_m\binom{m}{k+1}Y^{m-k-1}\sum_{\ell=0}^k \binom{k}{\ell}X^\ell(-Y)^{k-\ell}. \end{eqnarray*} Let's change the order of summation again: \begin{eqnarray*} F(X)-F(Y) & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq \ell+1}\left(\sum_{k=\ell}^{m-1} a_m\binom{m}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m-\ell-1} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=\ell}^{m+\ell} a_{m+\ell+1}\binom{m+\ell+1}{k+1}\binom{k}{\ell}(-1)^{k-\ell}\right)X^\ell{Y}^{m} \\ & = & (X-Y)\sum_{\ell \geq 0} \sum_{m \geq 0}\left(\sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}\right)a_{m+\ell+1}X^\ell{Y}^{m}. \end{eqnarray*}

Comparing this final expression with the one at the end of Method 1, we see that $$a_{m+\ell+1} = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}a_{m+\ell+1}.$$ The coefficients in $F(X)$ were just used to illustrate the generality of the calculation, but we can now set them all equal to 1: $$1 = \sum_{k=0}^{m}\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell}(-1)^{k}.$$ The product of binomial coefficients in the $k$th term can be rewritten to have $k$ in just one binomial coefficient and in an additional factor: $$\binom{m+\ell+1}{k+\ell+1}\binom{k+\ell}{\ell} = \binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}.$$ Therefore $$1 = \sum_{k=0}^{m}\binom{m+\ell+1}{\ell+1}\binom{m}{k}\frac{\ell+1}{\ell+1+k}(-1)^{k} = \binom{m+\ell+1}{\ell+1}\sum_{k=0}^m\binom{m}{k}\frac{(\ell+1)(-1)^k}{\ell+1+k}.$$ Since $\ell$ is an arbitrary nonnegative integer and occurs throughout as $\ell+1$, rewrite $\ell+1$ as $n$ and we get the desired binomial coefficient identity.

This is mechanized in Maple:

binomial(m+n, n)*(sum(binomial(m, k)*n*(-1)^k/(n+k), k = 0 .. m));


$${\frac {{m+n\choose n}}{{m+n\choose m}}}$$ PS. Please, don't change my answer.

• Yeah. But evidently OP wants a proof, not just an appeal to Maple authority. – Todd Trimble Jan 10 '15 at 22:05