20
$\begingroup$

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.

Note:- The problem has also been posted here.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Let $a_s$ denote your sum. Any sum like this has to satisfy a linear recurrence relation with polynomial coefficients. Some experimentation suggests that we have $$(7s+8)(s+4)(s+3)a_{s+3} - 4(56s^2+127s+57)(s+3)(s+2)a_{s+2} - 16(7s^4-6s^3-121s^2-210s-90)a_{s+1} + 128(7s+15)(2s+3)(2s+1)(s-1)a_s = 0$$ for all $s \ge 0$. There are quite algorithmic ways to prove such a relation. The question is if it can actually help with the problem. $\endgroup$
    – Michael Stoll
    Commented Dec 12, 2014 at 11:08
  • 2
    $\begingroup$ Also posted to m.se --- you should put a link at each site to the question at the other site. $\endgroup$
    – Gerry Myerson
    Commented Dec 12, 2014 at 11:15
  • $\begingroup$ Never mind; math.stackexchange.com/questions/1042332/… $\endgroup$
    – Gerry Myerson
    Commented Dec 12, 2014 at 11:35
  • 3
    $\begingroup$ Is there any background? $\endgroup$
    – Alex Degtyarev
    Commented Dec 12, 2014 at 11:45
  • 1
    $\begingroup$ Since the Catalan numbers are involved and we always (presumably) get an integer value, it looks like this sum denumerates specific portions of e.g. trees. So, it would be nice to find some combinatorial arguments which might be helpful to considerably simplify this double sum and answer OPs question as side-effect. In fact, I'm first of all interested in simplifying this double sum. $\endgroup$
    – Markus Scheuer
    Commented Dec 12, 2014 at 18:25

1 Answer 1

Reset to default
17
$\begingroup$

Here is an attempt at an answer. We assume that the recurrence from my comment above holds [with a small correction] (a proof was obtained by Kevin using Zeilberger's algorithm, see the comment below): $$ (7s+8)(s+4)(s+3)^2 a_{s+3} - 4(56s^2+127s+57)(s+3)(s+2) a_{s+2} $$ $$ - 16(7s^4-6s^3-121s^2-210s-90) a_{s+1} + 128(7s+15)(2s+3)(2s+1)(s-1) a_s = 0 $$ Write $a_s = b_s/(s+1)$. According to Kevin's claim (1), $b_s \in \mathbb Z$. Now the sequence $(b_s)$ satisfies the recurrence $$ (7s+8)(s+3)^2(s+2)(s+1) b_{s+3} - 4(56s^2+127s+57)(s+2)^2(s+1) b_{s+2} $$ $$ - 16(7s^4-6s^3-121s^2-210s-90)(s+1) b_{s+1} + 128(7s+15)(2s+3)(2s+1)(s+2)(s-1) b_s = 0 .$$ We want to show that $s+1$ divides $b_s$. By the recurrence, we have that $$ (s+1) \mid 128(7s+15)(2s+3)(2s+1)(s+2)(s-1) b_s . $$ Since the gcd of $s+1$ with the factor in front of $b_s$ is a power of 2, we can conclude that the odd part of $s+1$ divides $b_s$. On the other hand, it is easy to see that each term in the sum for $a_s$ is 2-adically integral (it is a Catalan number times some binomial coefficients times a fraction with odd denominator), so there is no need to consider the 2-power part of $s+1$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I verify the recurrence via maple, and find $a_s$ don't satisfy the recurrence. Could you tell me how you find this third-order recurrence? If the right recurrence is found, it is helpful to solve this problem. Thanks! $\endgroup$
    – Chitsai Liu
    Commented Dec 12, 2014 at 12:32
  • $\begingroup$ Did you use the corrected version (with $(s+3)^2$ in the coefficient of $a_{s+3}$)? Just to check that I did compute the $a_s$ correctly: my sequence starts with $1, 0, 16, 96, 832, 9728, 140288, 2327552, \ldots$ (and is not in the OEIS). $\endgroup$
    – Michael Stoll
    Commented Dec 12, 2014 at 12:40
  • $\begingroup$ I use the corrected version and verify it via maple, it is correct recurrence, you are right! The sequence is not in OEIS. I can't find the recurrence by zeilberger algorithm. How do you find the recurrence?Thank you very much! $\endgroup$
    – Chitsai Liu
    Commented Dec 12, 2014 at 13:23
  • $\begingroup$ I found the (likely) recurrence by looking for a linear dependence between the sequences $(s^j a_{s+k})$ for small values of $j$ and $k$. I'll try to produce a proof later. $\endgroup$
    – Michael Stoll
    Commented Dec 12, 2014 at 13:50
  • 2
    $\begingroup$ Thank you for your good ideas and suggestions for this question. I have proved the third-order recurrence by Multi-Varible Zeilberger algorithm. In my proof, I obtain a very complicated fifth-order recurrence. What I have done is that: $M(s),N(s)$ denote the third recurrence and fifth-order recurrence respectively. Then I prove $c_0(s)N(s)+d_0(s)M(s)+d_1(s)M(s+1)+d_2(s)M(s+2)=0$ where $c_0(s),d_0(s),d_1(s),d_2(s)$ are polynomials with integer coefficients, from this fact, I prove the third-order recurrence by induction. If proof without software is found, it will be better. $\endgroup$
    – Chitsai Liu
    Commented Dec 13, 2014 at 14:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .