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.

  • 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 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 at 19:59
  • 1
    $\begingroup$ @JulesLamers: I learned something. Thanks. $\endgroup$ Feb 4 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 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 at 0:16

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 $(*)$.


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

  • 1
    $\begingroup$ I was always interested: is there an automatic way to find such an identity? $\endgroup$ Feb 4 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 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 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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