8
$\begingroup$

Among the families of sequences studied by Nicolaas de Bruijn (Asymptotic Methods in Analysis, 1958), let's focus on the (modified) $$\hat{S}(4,n)=\frac1{n+1}\sum_{k=0}^{2n}(-1)^{n+k}\binom{2n}k^4.$$ An all-familiar fact states: the Catalan number $C_n=\frac1{n+1}\binom{2n}n$ is odd iff $n=2^m-1$. In the same tradition, I ask:

QUESTION. Is this true? $\hat{S}(4,n)$ is odd iff $n=2^m-1$ for some $m\in\mathbb{Z_{\geq0}}$.

POSTSCRIPT. This question has been extended to my other MO question.

$\endgroup$
7
  • 1
    $\begingroup$ for what it worth, $(-1)^n(n+1)\hat{S}(4,n)$ is a constant term of $(1+b/a)^{2n}(1+c/b)^{2n}(1+d/c)^{2n}(1-a/d)^{2n}$ $\endgroup$ Feb 3, 2021 at 23:49
  • 4
    $\begingroup$ As an aside, in Dutch, all particles (like 'de') in a surname are capitalised unless a given name or initial precedes it. So: "Nicolaas de Bruijn" but "De Bruijn sequence". $\endgroup$ Feb 4, 2021 at 19:59
  • 1
    $\begingroup$ @JulesLamers: I learned something. Thanks. $\endgroup$ Feb 4, 2021 at 20:13
  • $\begingroup$ @JulesLamers it's interesting, but should such rules be extrapolated from Dutch to other languages? I am not sure, in Russian I would still write "последовательность де Брёйна". $\endgroup$ Feb 4, 2021 at 20:56
  • 1
    $\begingroup$ I think the body of this question and of the other question you have asked on De Bruijn sequences should contain links to each other. $\endgroup$ Feb 7, 2021 at 0:16

2 Answers 2

9
$\begingroup$

That's true. This follows easily from the formula $$ \hat{S}(4,n)=\frac1{n+1}\binom{2n}n\sum_{k=0}^n (-1)^k\binom{2n+k}k^2\binom{2n}{n+k}.\quad\quad\quad\quad\quad(*) $$

First of all, I prove your parity claim using $(*)$, and next prove $(*)$. If $n+1$ is not a power of 2, then $C_n=\frac1{n+1}\binom{2n}n$ is even and so is RHS of $(*)$. If $n=2^m-1$, then $C_n$ is odd, the summand with $k=1$ in RHS of $(*)$ is odd and other summands are even: $\binom{2n+k}k=\frac{(2n+1)(2n+2)}{k(k-1)}\binom{2n+k}{k-2}$ is even for $k=2,3,\ldots,n$ since $k(k-1)$ is not divisible by $2^{m+1}=2n+2$.

Now the proof of $(*)$. For $C:=(-1)^n (n+1)\hat{S}(4,n)$ we have $$C=[x^{2n}y^{2n}z^{2n}t^{2n}](x-y)^{2n}(y-z)^{2n}(z-t)^{2n}(x+t)^{2n}=[x^{2n}y^{2n}z^{2n}t^{2n}]F,$$ where $$F=\prod_{j=-(n-1)}^{n}(x-y-j)(z-y-j)(z-t-j)(x+t-2n-j).$$ Denote $A=\{0,1,\ldots,2n\}$ and express the coefficient $[x^{2n}y^{2n}z^{2n}t^{2n}]F$ via the values of $F$ on $A^4$ using this formula.

Look how $F(x,y,z,t)\ne 0$ may be possible when $x,y,z,t\in A$. We must have $|x-y|\geqslant n, |y-z|\geqslant n, |z-t|\geqslant n$ and $x-y\ne n$, $z-y\ne n$, $z-t\ne n$. If $y$ lies between $x$ and $z$, the conditions $|x-y|\geqslant n, |z-y|\geqslant n$ yield $y=n$, $\{x,z\}=\{0,n\}$, but then either $x-y$ or $z-y$ equals $n$; a contradiction. Analogously if $z$ lies between $y$ and $t$. Thus $x-y,z-y,z-t$ have equal sign. If they are positive, we get $2n\geqslant x\geqslant y+n+1\geqslant n+1$ and $n-1\geqslant z-n-1\geqslant t\geqslant 0$, thus $x+t\in [n+1,3n-1]$ and therefore $F(x,y,z,t)=0$; a contradiction. So we must have $n\geqslant y-n\geqslant x\geqslant 0$, $2n\geqslant t\geqslant z+n\geqslant n$ and $x+t\in [n,3n]$. Since $F(x,y,z,t)\ne 0$, we conclude that $x+t=n$, $x=0$, $t=n$, thus $z=0$ and $y\in [n,2n]$. Then the cited formula allows to rewrite $C$ as a sum over $y$ which simplifies as $(*)$.

$\endgroup$
1
5
$\begingroup$

I just wished to suggest an alternative (mechanical) proof whose details can be provided (using the WZ-method) for the identity $$\sum_{k=0}^{2n}(-1)^{n+k}\binom{2n}k^4=\binom{2n}n\sum_{k=0}^n(-1)^k\binom{2n+k}k^2\binom{2n}{n+k}.\qquad \qquad (*)$$ The idea is: verify that both sides of $(*)$ satisfy the 2nd-order recurrence \begin{align*} A(n)a(n+2)- B(b)a(n+1) +C(n)a(n)=0 \end{align*} with initial conditions $a(0)=1$ and $a(1)=14$; where \begin{align*} A(n)&=(2n + 3)(48n^2 + 66n + 23)(n + 2)^3 \\ B(n)&=13056n^6+ 96288n^5+ 289600n^4+ 453428n^3 + 388698n^2 + 172598n+31030 \\ C(n)&=4(n + 1)(48n^2 + 162n + 137)(2n + 1)^3. \end{align*}

$\endgroup$
3
  • 1
    $\begingroup$ I was always interested: is there an automatic way to find such an identity? $\endgroup$ Feb 4, 2021 at 20:53
  • $\begingroup$ The story is: you can prove A=B, if you know both. But, knowing A alone does not offer (mechanically) what B is. Of course, on many occasions, there could be more than one such B. Is that what you ask? $\endgroup$ Feb 4, 2021 at 20:57
  • $\begingroup$ Yes, but possibly under certain pattern of possible forms for B there is an algorithm which finds whether the identity with some B in this patter exists? Say, is there an algorithm to decide whether a certain binomial sum is a finite ratio of products of factorials of expressions $a_in+b_i$? $\endgroup$ Feb 4, 2021 at 22:03

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.