Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

While studying a problem about orthogonal polynomials I encountered the following expressions \begin{equation} f(n)=\sum_{k=0}^{n}(-1)^k\binom{n+k}{2k} \frac{1}{k+1}\binom{2k}{k} \end{equation} and \begin{equation} g(n)=\sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1} \frac{1}{k+2}\binom{2k+2}{k+1} \end{equation}

I can prove that $f(n)=0$ for all integers $n\geq 1$ and $g(n)=0$ for all integers $n>1$ using properties of orthogonal polynomials. However, I would like to find an elementary proof, which might also be more illuminating. While doing some experiments with calculations using Mathematica, I defined the functions $f(n)$ and $g(n)$ with the above formulas but forgot to specify that $n$ is an integer value. When I typed $f(n)$ and $g(n)$ for a generic variable $n$, I guess that Mathematica "assumed" that the variables involved were real and provided the following simple formulas:

\begin{equation} f(x)=\frac{\sin \pi x}{x(x+1)\pi} \end{equation} and \begin{equation} g(x)=-\frac{2\sin \pi x}{(x+1)(x-1)\pi} \end{equation} which makes it evident that these functions are zero for all positive (and negative) integers with the possible exceptions of $0,1,-1$.

Why are these equalities true?

I realize it might have to do, perhaps, with properties of the Euler Beta and Gamma functions, but I know too little about these functions to figure out a proof along these lines. Can anybody help? Thank you!

share|improve this question
    
When non-integer $n$ (or $x$) occurs as the upper bound on a summation, I'd interpret the sum as ranging just over integers below that bound. And I'd interpret binomial coefficients $\binom{y}{m}$, with integer $m$ but non-integer $y$, as polynomials in $y$. So I'd get piecewise polynomial results for the sum. Apparently, Mathematica interprets things differently than I do --- but how? Maybe the sums become infinite series, because it keeps adding terms until the summation variable equals the upper bound? –  Andreas Blass Oct 11 '12 at 12:40
    
For $k>n$ the first binomial in $f(n)$ vanishes, for $k>n-1$ the first binomial in $g(n)$ vanishes. So you can ignore the upper limit, i.e. replace it with infinity. –  Martin Rubey Oct 11 '12 at 13:03
    
It seems to me that the vanishing of $\binom{n+k}{2k}$ for $n>k$ depends on $n$'s being an integer. –  Andreas Blass Oct 11 '12 at 13:16
2  
Yes it does. All I'm saying is that $f$ and $g$ can be first understood as infinite series without changing the value. In a second step we replace $n$ in the summands by a continues variable $x$, which again doesn't change the value for integer $x$. This explains how mathematica arrives at the nice closed forms. –  Martin Rubey Oct 11 '12 at 13:30
add comment

2 Answers 2

up vote 7 down vote accepted

Let's consider more generally the sums (from $0$ to $n$, resp. from $0$ to $n-1$) with a real or complex number $x$ in place of the $n$ inside the sums:

\begin{equation} \sum_{k=0}^{n}(-1)^k\binom{x+k}{2k} \frac{1}{k+1}\binom{2k}{k} \end{equation} and \begin{equation} \sum_{k=0}^{n-1}(-1)^k\binom{x+k}{2k+1} \frac{1}{k+2}\binom{2k+2}{k+1}\, . \end{equation}

These sums can be evaluated by induction as:

\begin{equation} (-1)^n\frac{n+1}{x(x+1)} \binom{x+n+1}{2n+2}\binom{2n+2}{n+1} \end{equation} and \begin{equation} (-1)^n\frac{n+1}{x^2-1} \binom{x+n+1}{2n+3}\binom{2n+4}{n+2}\, . \end{equation} We can write these expression respectively as

\begin{equation} \frac{1}{x+1}\left(1+\frac{x}{n+1} \right)\prod_{k=1}^n\left(1-\frac{x^2}{k^2}\right) \end{equation} and \begin{equation} -\frac{2x}{x^2-1}\frac{n+1}{n+2}\prod_{k=1}^{n+1}\left(1-\frac{x^2}{k^2}\right)\, . \end{equation}

The limit of these expression can be evaluated by means of the Euler's infinite product for $\sin(\pi x)$, obtaining respectively the values of the series :

\begin{equation} \sum_{k=0}^{\infty}(-1)^k\binom{x+k}{2k} \frac{1}{k+1}\binom{2k}{k}=\frac{\sin(\pi x)}{\pi x(x+1)} \end{equation} and \begin{equation} \sum_{k=0}^{\infty}(-1)^k\binom{x+k}{2k+1} \frac{1}{k+2}\binom{2k+2}{k+1}=-\frac{2\sin(\pi x)}{\pi(x^2-1)}\, . \end{equation} As observed in the comments, for a positive integer $x=n$, these series coincide respectively with the initially considered finite sums $f$ and $g$, of which they may be considered therefore as a natural extension to complex values of $x$.

share|improve this answer
    
mmmh, wait, actually evaluating the sums I assumed x to be an integer! so I'm not sure of the result. –  Pietro Majer Oct 11 '12 at 15:17
    
The sums are polynomials in $x$ so if they agree on the integers then they are equal everywhere. I personally don't see how Maple is computing the sums, but that's another story. –  Matt Young Oct 11 '12 at 17:34
    
Yes, sorry, I was in a big hurry and I was taken by some sudden silly doubt. Checking now the details, there were no problem at all, so I roll back to the first version. The identities for the sums are easily proven by induction, and contain a partial product of the infinite product for $\sin(\pi x)/\pi x$. –  Pietro Majer Oct 12 '12 at 13:56
    
Thanks a lot. I really enjoyed your solution. Grazie mille. –  Stefano Capparelli Oct 16 '12 at 10:38
add comment

The two identities are both special cases of Vandermonde's theorem (also called the Chu-Vandermonde theorem), which is the most well-known binomial coefficient identity after the binomial theorem. The first sum may be written $$f(n) = \frac 1n \sum_{k=0}^n (-1)^k\binom nk \binom {n+k}{k+1}.$$ Applying the identity $\binom{-c}m = (-1)^{m}\binom{c+m-1}{m}$, we get $$f(n)= -\frac 1n \sum_{k=0}^n \binom nk \binom {-n}{k+1},$$ and reversing the order of summation gives \begin{equation*} f(n) =-\frac 1n \sum_{k=0}^n \binom nk \binom {-n}{n-k+1}. \end{equation*}

Vandermonde's theorem is often written \begin{equation*} \sum_{k=0}^m \binom ak \binom b{m-k} = \binom{a+b}m. \end{equation*} There are many simple proofs of Vandermonde's theorem. For example, we can prove this formula by equating coefficients of $x^m$ in $(1+x)^a (1+x)^b = (1+x)^{a+b}$.

Setting $a=n$, $b=-n$, and $m=n+1$ in this formula (and observing that the $k=n+1$ term vanishes) and using the last formula for $f(n)$ shows that for $n>0$, $f(n) =- \frac 1n\binom 0{n+1}=0.$ Similarly, $g(n)$ can be evaluated by Vandermonde's theorem.

I believe that Pietro's indefinite summation approach is correct, but I don't think that this is what Mathematica is doing. There is a nonterminating generalization of Vandermonde's theorem, called Gauss's theorem (see, e.g., http://mathworld.wolfram.com/GausssHypergeometricTheorem.html) that evaluates the sum $\sum_{k=0}^\infty (-1)^k \binom ak \binom {b+k}{m+k}$ in terms of gamma functions when it converges, where $a$ and $b$ are arbitrary and $m$ is an integer. (Actually Gauss's theorem is a little more general than this.) In the particular case $a=n$, $b=n$, $m=1$, the reflection formula for the gamma function can be applied to give Stefano's formula for $f(x)$ in terms of $\sin \pi x$, and similarly for $g(x)$. Mathematica is probably applying Gauss's theorem, since it knows how to convert binomial coefficient sums to hypergeometric series and it knows how to evaluate them in cases like this one.

share|improve this answer
    
Thank you! This is indeed a nice short proof. I am new here and if I have to choose a single answer as a preferred answer I am going to go for Pietro's as it also gives me a proof of the natural extension of the summation formulas. Of course, you might also be right that the actual Mathematica procedure is a different story. Thanks to all those that took interest in this. –  Stefano Capparelli Oct 16 '12 at 10:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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