# De Bruijn's sequence is odd iff $n=2^m-1$: Part I

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.

• 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}$ Feb 3 at 23:49
• 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". Feb 4 at 19:59
• @JulesLamers: I learned something. Thanks. Feb 4 at 20:13
• @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 "последовательность де Брёйна". Feb 4 at 20:56
• 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. 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*}

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