7
$\begingroup$

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.

$\endgroup$
7
  • 12
    $\begingroup$ Look at $\int_0^1 (1-x)^m x^{n-1} dx$ and use the binomial theorem together with the beta integral. $\endgroup$
    – Lucia
    Jan 10, 2015 at 15:14
  • 6
    $\begingroup$ 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. $\endgroup$ Jan 10, 2015 at 16:03
  • 1
    $\begingroup$ This identity implies that $$ \sum_{k=0}^m \frac {n(-1)^k}{n+k} = \sum_{k=0}^n \frac {m(-1)^k}{m+k}$$. $\endgroup$
    – hkju
    Jan 10, 2015 at 22:19
  • 2
    $\begingroup$ This identity is also a special case of Vandermonde's theorem. $\endgroup$
    – Ira Gessel
    Jan 11, 2015 at 6:11
  • 1
    $\begingroup$ This has also recently appeared on math.stackexchange: math.stackexchange.com/questions/2455428/… $\endgroup$ Nov 20, 2017 at 10:06

9 Answers 9

11
$\begingroup$

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.

$\endgroup$
0
10
$\begingroup$

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.

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

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

$\endgroup$
7
  • $\begingroup$ $\sum_{k=0}^m \binom{m}{k}(-1)^k$ is not $0$ if $m = 0$. $\endgroup$
    – KConrad
    Jan 11, 2015 at 1:55
  • 3
    $\begingroup$ True, but I'm also only using it whenever $m\geq 1$. :) $\endgroup$ Jan 11, 2015 at 1:58
  • $\begingroup$ 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$. $\endgroup$
    – KConrad
    Jan 11, 2015 at 2:05
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 11, 2015 at 3:17
  • 1
    $\begingroup$ @GjergjiZaimi: You are right. I checked this in my head, but stopped half-way :-) $\endgroup$
    – GH from MO
    Jan 11, 2015 at 3:27
9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – KConrad
    Jan 11, 2015 at 4:10
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – KConrad
    Jan 11, 2015 at 4:17
  • $\begingroup$ 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). $\endgroup$
    – Todd Trimble
    Jan 11, 2015 at 4:25
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
1
  • 8
    $\begingroup$ Yeah. But evidently OP wants a proof, not just an appeal to Maple authority. $\endgroup$
    – Todd Trimble
    Jan 10, 2015 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.