Binomial coefficient identity

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$.

Answer 4

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.

Answer 5

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$.

Answer 6

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.

Answer 7

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.

Answer 8

We recite Theorem 2.1 and its proof in the paper [1] below as an answer.

Theorem 2.1. Let $n\ge0$ be an integer and $\Re(z)>0$. Then \begin{equation}\label{sum-recip-binom-ext}\tag{1} \sum_{q=0}^{n}\binom{n}{q}\frac{(-1)^q}{q+z}=B(z,n+1) \end{equation} and \begin{equation}\label{sum-recip-binom-ext-inv}\tag{2} \sum _{q=0}^n \binom{n}{q}[(-1)^qB(z,q+1)]=\frac1{z+n}, \end{equation} where \begin{equation*} B(z,w)=\int_{0}^{1}t^{z-1}(1-t)^{w-1}\textrm{d}\,t, \quad \Re(z),\Re(w)>0 \end{equation*} denotes the classical Euler beta function.

Proof. Let \begin{equation*} f(t)=\sum_{q=0}^{n}\frac{(-1)^q}{q+z}\binom{n}{q}t^{q+z}, \quad t\ge0. \end{equation*} It is obvious that $f(0)=0$ and \begin{equation*} f'(t)=\sum_{q=0}^{n}(-1)^q\binom{n}{q}t^{q+z-1} =t^{z-1}\sum_{q=0}^{n}(-1)^q\binom{n}{q}t^q =t^{z-1}(1-t)^n. \end{equation*} Integrating on both sides of the above equality with respect to $t$ over $[0,1]$ gives $f(1)=B(z,n+1)$. The formula \eqref{sum-recip-binom-ext} is thus proved.

The identity \eqref{sum-recip-binom-ext-inv} follows from applying the binomial inversion formula \begin{equation}\label{binomial-inversion-formula} g(n)=\sum_{\ell=0}^n\binom{n}{\ell}(-1)^\ell f(\ell) \Longleftrightarrow f(n)=\sum_{\ell=0}^n\binom{n}{\ell}(-1)^\ell g(\ell), \end{equation} see the formula (5.48) on page 192 in the monograph [3] below, to the formula \eqref{sum-recip-binom-ext}. The required proof of is complete.

Remark 2.2. The formula \eqref{sum-recip-binom-ext} recovers the formula (7.7) on page 82 in the monograph [2] below.

References

1. Feng Qi and Chuan-Jun Huang, Computing sums in terms of beta, polygamma, and Gauss hypergeometric functions, Revista de la Real Academia de Ciencias Exactas Fisicas y Naturales Serie A Matematicas 114 (2020), Paper No. 191, 9 pages; available online at https://doi.org/10.1007/s13398-020-00927-y.
2. J. Quaintance and H. W. Gould, Combinatorial Identities for Stirling Numbers, the unpublished notes of H. W. Gould, with a foreword by George E. Andrews, World Scientific Publishing Co. Pte. Ltd., Singapore, 2016.
3. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics---A Foundation for Computer Science, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994.

Answer 9

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.