How to prove a double sum is always an integer?

Question

I have verified 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

Answer 1

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*}