# How to prove a double sum is always an integer?

I have veriﬁed the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks!

$$\sum_{m=s}^{2s}\sum_{k=0}^{s} {2s\choose s}{s\choose k}{m\choose k}{k\choose m-s} \frac{1}{(s+1)(2k-1)(2m-2k-1)}$$

What I have known is that:

(1) Every term is not always an integer, but I can prove that ${2s\choose s}{s\choose k}{m\choose k}{k\choose m-s} \frac{1}{(2k-1)(2m-2k-1)}$ is always an integer.

(2) $\sum_{k=0}^{s} {2s\choose s}{s\choose k}{m\choose k}{k\choose m-s} ={2s\choose s}^2{s\choose m-s}$. This combinatorial identity may be helpful to solve this problem.

https://mathoverflow.net/questions/190549/how-to-prove-that-the-following-double-sum-is-always-an-integer

• @Michael:Each term is not always an integer.If each term is an integer,this question was very easy. – Ji-Cai Liu Nov 28 '14 at 13:56
• On page 118 of the book "Generatingfunctionology" (available online as a PDF), he discusses the "Snake Oil" method that might be useful here. It might be hard to understand without reading the book from the beginning, though… – Akiva Weinberger Nov 28 '14 at 14:21
• @Kevin: you are right, it is not true that every term belong to $\mathbb{Z}$. However, every term belong to $\frac{1}{s+1}\mathbb{Z}$, so it should suffices to study the residue classes $\pmod{s+1}$. – Jack D'Aurizio Nov 28 '14 at 14:55
• @Kevin Your most recent edit glitched up the latex somehow. – David H Dec 7 '14 at 7:23
• Also posted to MO, mathoverflow.net/questions/190549/… – Gerry Myerson Dec 12 '14 at 11:36

## 1 Answer

Note: The following is not a solution but at least a slight structural simplification of OPs binomial expression. This could be helpful to further simplify the expression but also to find a simpler recurrence with similar means as is it presented in the answer of this question by @Michael Stoll at Math Overflow.

First a few preliminaries:

• Closed formula: In order to show that the expression $A(s)$ is an integer for each natural number $s$, the most attractive way (for me) is to find a closed formula from which we could directly deduce the claim.

If a closed formula is hard to find, we could try to eliminate or at least simplify the fractions. With simplification I mean a transformation of the fraction which reduces the number of summation indices in it, so that the formula becomes more manageable for further calculations.

• Catalan Numbers: We observe the expression contains the well-known and ubiquitous Catalan numbers $$C_s=\frac{1}{s+1}\binom{2s}{s}$$

Since the Catalan numbers are natural numbers, we will simply denote them by $C_s$ in the following and we will put the focus on the other parts of the expression.

Overview: The simplification is done in some steps

• Step 1: Simple rewrite of $A(s)$ which is more convenient for the following calculations.

\begin{align*} A(s)=C_s\sum_{k=0}^{s}\binom{s}{k}\frac{1}{2k-1}\sum_{m=0}^{k}\binom{m+s}{k}\binom{k}{m}\frac{1}{2m+2s-2k-1} \end{align*}

• Step 2: The expression $A(s)$ is split into two sums

$$A(s) = \frac{1}{2}C_s\left(A_1(s) + A_2(s)\right)$$

We show, that $A_1(s) = A_2(s)$ and get a first structural simplification of $A(s)$.

\begin{align*} A(s)=C_s\sum_{k=0}^{s}\binom{s}{k}\frac{1}{2k-1}\sum_{m=0}^{k}\binom{m+s}{k}\binom{k}{m}\frac{1}{m+s-1} \end{align*}

• Step 3: We split the sum $A_1$ and use a technique by Egorychev to transform the parts. We will see how powers of $2$ are involved in the formula and it enables a way to further simplify the formula.

• Step 4: For $s\geq 2$ we get the following representation of $A(s)$

\begin{align*} A(s)&=C_s\left((s+1)+B_1(s)+B_2(s)\right)\\ &=\binom{2s}{s}+\frac{C_s}{s-1}\sum_{k=2}^{s}\binom{s-1}{k-1} \frac{1}{2k-1}\sum_{m=2}^{k}\binom{k-2}{m-2}\binom{s}{m}2^m\tag{1}\\ &\qquad\qquad+\frac{C_s}{s-1}\sum_{k=2}^{s}\binom{s}{k} \frac{1}{2k-1}\sum_{m=1}^{k}\binom{k-1}{m-1}\binom{s-1}{m}2^m\tag{2}\\ \end{align*}

• Observe, that now there's only one fraction left within the outer sum. Based on this representation it would be nice to find some more simplifications or a less complex recurrence relation. Since $B_1(s)$ and $B_2(s)$ are structurally similar, we can put the focus e.g. on this part:

$$\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\sum_{m=1}^{k}\binom{k-1}{m-1}\binom{s-1}{m}2^m$$

which seems to be easier to study than the original formula in the question.

And now the gory details:

Step 1: Simple rewrite of $A(s)$ which is more convenient for the following calculations.

We start by introducing the symbol $C_s$ for the Catalan numbers $C_s=\frac{1}{s+1}\binom{2s}{s}$, exchanging the sums and changing the index range of $m$ from $[s,2s]$ to $[0,s]$.

\begin{align*} A(s)&=\sum_{m=s}^{2s}\sum_{k=0}^{s}\binom{2s}{s}\binom{s}{k}\binom{m}{k}\binom{k}{m-s} \frac{1}{(s+1)(2k-1)(2m-2k-1)}\\ &=C_s\sum_{k=0}^{s}\sum_{m=0}^{s}\binom{s}{k}\binom{m+s}{k}\binom{k}{m} \frac{1}{(2k-1)(2m+2s-2k-1)}\\ &=C_s\sum_{k=0}^{s}\binom{s}{k}\frac{1}{2k-1}\sum_{m=0}^{k}\binom{m+s}{k}\binom{k}{m} \frac{1}{2m+2s-2k-1}\tag{3}\\ \end{align*}

Observe, that in (3) the index range of $m$ is $[0,k]$, since $\binom{k}{m}=0$ if $m>k$. Therefore we effectively sum up over a triangular region $0\leq k \leq s,0 \leq m \leq k$ and not over a square $0\leq k,m\leq s$.

Step 2: The expression $A(s)$ will be split into two sums $A_1(s)$ and $A_2(s)$

Since

$$\frac{1}{2k-1}+\frac{1}{2m+2s-2k-1}=\frac{2(m+s-1)}{(2k-1)(2m+2s-2k-1)}$$

The expression (3) can be written as

\begin{align*} A(s)&=\frac{1}{2}C_s\sum_{k=0}^{s}\binom{s}{k}\frac{1}{2k-1} \sum_{m=0}^{k}\binom{m+s}{k}\binom{k}{m}\frac{1}{m+s-1}\tag{4}\\ &+\frac{1}{2}C_s\sum_{k=0}^{s}\binom{s}{k} \sum_{m=0}^{k}\binom{m+s}{k}\binom{k}{m}\frac{1}{m+s-1}\cdot\frac{1}{2m+2s-2k-1}\tag{5}\\ &=\frac{1}{2}C_s\left(A_1(s)+A_2(s)\right) \end{align*}

with $A_1$ the double sum in (4) and $A_2$ the double sum in (5).

When looking at $A_1(s)$ and $A_2(s)$ in more detail, it was a great pleasure to observe that $A_1(s)=A_2(s)$ for small $s$.

We now show the following is valid:

$$A_1(s) = A_2(s) \qquad\qquad s \geq 0$$

We start with transforming $A_2(s)$ by exchanging the sums:

\begin{align*} A_2(s)&=\sum_{k=0}^{s}\binom{s}{k} \sum_{m=0}^{k}\binom{m+s}{k}\binom{k}{m}\frac{1}{m+s-1}\cdot\frac{1}{2m+2s-2k-1}\\ &=\sum_{m=0}^{s}\sum_{k=m}^{s}\binom{s}{k}\binom{m+s}{k}\binom{k}{m}\frac{1}{m+s-1}\cdot\frac{1}{2m+2s-2k-1} \end{align*}

Next we introduce the index $l:=s-k+m$ and substitute it with the index $k=s-l+m$ by respecting the index range:

\begin{array}{lcl} k=m&\qquad\longrightarrow\qquad &l=s\\ k=s&\qquad\longrightarrow\qquad &l=m \end{array}

We therefore get after substition and exchange of summation: \begin{align*} A_2(s)&=\sum_{m=0}^{s}\sum_{l=m}^{s}\binom{s}{s-l+m}\binom{m+s}{s-l+m} \binom{s-l+m}{m}\frac{1}{m+s-1}\cdot\frac{1}{2l-1}\\ &=\sum_{l=0}^{s}\sum_{m=0}^{l}\binom{s}{s-l+m}\binom{m+s}{s-l+m} \binom{s-l+m}{m}\frac{1}{m+s-1}\cdot\frac{1}{2l-1}\tag{6} \end{align*}

Next observe, that following binomial identities are valid:

\begin{align*} \binom{m+s}{s-l+m}\binom{s-l+m}{m}&=\binom{m+s}{m}\binom{s}{s-l}\\ \binom{s}{l-m}\binom{m+s}{m}&=\binom{l}{m}\binom{m+s}{l} \end{align*}

Using these identity relation in (6) gives:

\begin{align*} A_2(s)&=\sum_{l=0}^{s}\sum_{m=0}^{l}\binom{s}{l-m}\binom{m+s}{m}\binom{s}{l} \frac{1}{m+s-1}\cdot\frac{1}{2l-1}\\ &=\sum_{l=0}^{s}\binom{s}{l-m}\frac{1}{2l-1}\sum_{m=0}^{l}\binom{m+s}{m}\binom{s}{s-l} \frac{1}{m+s-1}\\ &=\sum_{l=0}^{s}\binom{l}{m}\frac{1}{2l-1}\sum_{m=0}^{l}\binom{m+s}{l}\binom{s}{l} \frac{1}{m+s-1}\\ &=A_1(s) \end{align*}

We conclude:

\begin{align*} A(s)&=C_sA_1(s)\\ &=C_s\sum_{k=0}^{s}\binom{s}{k}\frac{1}{2k-1}\sum_{m=0}^{k}\binom{m+s}{k}\binom{k}{m}\frac{1}{m+s-1} \end{align*}

Step 3: We split the sum $A_1(s)$ and use a technique by Egorychev to transform the parts. We see, how powers of $2$ are involved in the formula and it enables a way to further simplify the formula.

We split $A_1(s)$ by using the identity:

$$\binom{m+s}{k}=\binom{m+s-1}{k-1}+\binom{m+s-1}{k}$$

The inner sum of $A_1(s)$ can therefore be written as: \begin{align*} \sum_{m=0}^{k}&\binom{m+s}{k}\binom{k}{m}\frac{1}{m+s-1}\\ &=\sum_{m=0}^{k}\left[\binom{m+s-1}{k-1}+\binom{m+s-1}{k}\right]\binom{k}{m}\frac{1}{m+s-1}\\ &=\sum_{m=0}^{k}\left[\frac{1}{k-1}\binom{m+s-2}{k-2}+\frac{1}{k}\binom{m+s-2}{k-1}\right]\binom{k}{m}\frac{1}{m+s-1}\\ &=\frac{1}{k-1}\sum_{m=0}^{k}\binom{m+s-2}{k-2}\binom{k}{m}+\frac{1}{k}\sum_{m=0}^{k}\binom{m+s-2}{k-1}\binom{k}{m}\tag{7} \end{align*}

Observe, that we use $\frac{1}{k}$ and $\frac{1}{k-1}$ in (7). To avoid conflicts, we state that: $A(s)$ gives integer values for $0\leq s \leq 1$

\begin{align*} A(0) &= 1\\ A(1) &= 0 \end{align*}

and consider from now on $A(s)$ with values $s \geq 2$ only. We further calculate the values of $k=0,1$ in $A_1(s)$ separately which results in $2(s+1)$ and so we can use (7) and get

\begin{align*} A_1(s)&=2(s+1)+\sum_{k=2}^{s}\binom{s}{k} \frac{1}{2k-1}\cdot\frac{1}{k-1}\sum_{m=0}^{k}\binom{m+s-2}{k-2}\binom{k}{m}\\ &\qquad\qquad+\sum_{k=2}^{s}\binom{s}{k} \frac{1}{2k-1}\cdot\frac{1}{k}\sum_{m=0}^{k}\binom{m+s-2}{k-1}\binom{k}{m} \end{align*}

Please note, that the fractions in $A_1(s)$ are already somewhat simplified with regard to the original formulation. We have no longer any fraction dependent by the index of the inner sum.

Next we show that following identity is valid for $k \geq 2$:

\begin{align*} \sum_{m=0}^{k}&\binom{m+s-2}{k-2}\binom{k}{m}=\sum_{m=2}^{k}\binom{k}{m}\binom{s-2}{m-2}2^m \end{align*}

In order to do so we use a powerful technique based upon Cauchys residue theorem and introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies.

\begin{align*} \sum_{m=0}^{k}&\binom{m+s-2}{k-2}\binom{k}{m}\\ &=\sum_{m=0}^{\infty}\binom{m+s-2}{k-2}\binom{k}{m}\tag{8}\\ &=\sum_{m=0}^{\infty}\mathop{res}_u\frac{(1+u)^{m+s-2}}{u^{k-1}} \mathop{res}_z\frac{(1+z)^{k}}{z^{m+1}}\tag{9}\\ &=\mathop{res}_u\frac{(1+u)^{s-2}}{u^{k-1}}\sum_{m=0}^{\infty}(1+u)^m \mathop{res}_z\frac{(1+z)^{k}}{z^{m+1}}\ \tag{10}\\ &=\mathop{res}_u\frac{(1+u)^{s-2}}{u^{k-1}}(2+u)^k\tag{11}\\ &=[u^{k-2}](2+u)^k(1+u)^{s-2}\tag{12}\\ &=[u^{k-2}]\sum_{m=0}^{k}\binom{k}{m}2^mu^{k-m}(1+u)^{s-2}\\ &=\sum_{m=0}^{k}\binom{k}{m}2^m[u^{m-2}](1+u)^{s-2}\\ &=\sum_{m=2}^{k}\binom{k}{m}\binom{s-2}{m-2}2^m \end{align*}

Comment:

• In (8) the limit is changed without affecting the sum, since only $0$ is added.

• In (9) the residual calculus of formal power series is applied for each binomial coefficient.

• In (10) there is some rearrangement to prepare the application of the substitution rule which is used in (11)

• In (12) we use the coefficient of operator $[u^n]$ to denote the coefficient of $u^n$ of the sum.

Note: My answer to this question contains a small introductory note to this technique.

Similarly we can show that for $k \geq 1$:

\begin{align*} \sum_{m=0}^{k}&\binom{m+s-2}{k-1}\binom{k}{m}=\sum_{m=1}^{k}\binom{k}{m}\binom{s-2}{m-1}2^m \end{align*}

We conclude:

\begin{align*} A_1(s)&=2(s+1)+B_1(s)+B_2(2)\\ &=2(s+1)+\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\cdot\frac{1}{k-1} \sum_{m=2}^{k}\binom{k}{m}\binom{s-2}{m-2}2^m\tag{13}\\ &\qquad+\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\cdot\frac{1}{k} \sum_{m=1}^{k}\binom{k}{m}\binom{s-2}{m-1}2^m\tag{14}\\ \end{align*}

with $B_1(s)$ the double sum in (13) and $B_2(s)$ the double sum in (14).

Besides the information about the power of $2$ within $A_1(s)$ we are now prepared for one more simplifiaction.

Step 4: We can now $B_1(s)$ and $B_2(s)$ simplify by exchanging the fraction $\frac{1}{k}$ resp. $\frac{1}{k-1}$ with $\frac{1}{s-1}$ and so removing a dependency of the summation index.

We observe:

\begin{align*} B_1(s)&=\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\frac{1}{k-1} \sum_{m=2}^{k}\binom{k}{m}\binom{s-2}{m-2}2^m\\ &=\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\frac{1}{k-1} \sum_{m=2}^{k}\frac{k(k-1)}{m(m-1)}\binom{k-2}{m-2}\binom{s-2}{m-2}2^m\\ &=\frac{1}{s(s-1)}\sum_{k=2}^{s}\binom{s}{k}\frac{k}{2k-1}\sum_{m=2}^{k}\binom{k-2}{m-2}\binom{s}{m}2^m\\ &=\frac{1}{s-1}\sum_{k=2}^{s}\binom{s-1}{k-1}\frac{1}{2k-1}\sum_{m=2}^{k}\binom{k-2}{m-2}\binom{s}{m}2^m\\ \end{align*}

Similarly we get

\begin{align*} B_2(s)&=\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\frac{1}{k} \sum_{m=1}^{k}\binom{k}{m}\binom{s-2}{m-1}2^m\\ &=\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\frac{1}{k} \sum_{m=1}^{k}\frac{k}{m}\binom{k-1}{m-1}\frac{s-1}{s-1}\binom{s-2}{m-2}2^m\\ &=\frac{1}{s-1}\sum_{k=2}^{s}\binom{s}{k}\frac{1}{2k-1}\sum_{m=1}^{k}\binom{k-1}{m-1}\binom{s-1}{m}2^m\\ \end{align*}

And we can finally conclude:

\begin{align*} A(s)&=C_s\left((s+1)+B_1(s)+B_2(s)\right)\\ &=\binom{2s}{s}+\frac{C_s}{s-1}\sum_{k=2}^{s}\binom{s-1}{k-1} \frac{1}{2k-1}\sum_{m=2}^{k}\binom{k-2}{m-2}\binom{s}{m}2^m\\ &\qquad\qquad+\frac{C_s}{s-1}\sum_{k=2}^{s}\binom{s}{k} \frac{1}{2k-1}\sum_{m=1}^{k}\binom{k-1}{m-1}\binom{s-1}{m}2^m\\ \end{align*}

Note: Further investigations (recurrence relation, simplifications) could put the focus e.g. on

\begin{align*} \sum_{k=2}^{s}\binom{s}{k} \frac{1}{2k-1}\sum_{m=1}^{k}\binom{k-1}{m-1}\binom{s-1}{m}2^m\\ \end{align*}

• Although not arrive at an answer, it is a good idea, helpful to solve the problem. – Ji-Cai Liu Dec 15 '14 at 8:33
• @mwm: Thanks :-) I'm not sure, but maybe you was asking how to show that a double sum is an integer - The first idea was, if it's too difficult to remove the double sum, we could instead rearrange it, so that we have only binomal coefficients and no more additional fractions. In this case the double sum is clearly an integer. If this is not feasible, the strategy is to simplify it as much as possible to be able to deduce a simple recurrence or an expression with generating functions which we could use for further studies. Regards, – Markus Scheuer Dec 15 '14 at 8:36
• finding a recurrence without Zeilberger algorithm for the double sum is very hard. I have tried all approach I know, but all failed, finally I solve this problem by zeilberger algorithm, in my proof I find a very complicate fifth-order recurrence.If you can prove it without software, it will be great! – Ji-Cai Liu Dec 15 '14 at 8:52
• @Kevin: Thanks for your friendly reply. Regrettably I've no supporting SW tool. What about trying it in two steps: If you look at the inner sum of my last note in my answer: Fixing $s$ or using small values for $s$ - is there a simple recurrence for $\sum_{m=1}^{k}\binom{k-1}{m-1}\binom{s-1}{m}2^m$? Maybe this could help to find a simpler recurrence for the whole expression. Regards, – Markus Scheuer Dec 15 '14 at 9:11