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

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

Encouraged by a positive response of Fedor Petrov to my earlier MO question regarding the case $$a=2$$, I decided to beef-up the quest into a generalization.

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

Remark. Notice that in the case $$a=1$$, we have $$\hat{S}(2,n)=C_n$$.

• @FedorPetrov: the sum run through $0$ to $2n$. Why do you expect it to drop to $n$? Feb 7 at 14:22
• Because I am confused: the sum in RHS in the main identity for $a=2$ was for $k$ from 0 to $n$. Feb 7 at 14:43
• @FedorPetrov: no, it was up to $2n$. Feb 7 at 15:22
• Calkin showed (see theorem 1 here matwbn.icm.edu.pl/ksiazki/aa/aa86/aa8612.pdf) that $C_n|\hat{S}(2a,n)$ so it only remains to check indeed that for $n=2^m-1$ the sum is odd. Feb 7 at 19:25

I think, yes and it may be proved by the same way as for $$a=2$$. We note that $$C:=\sum_{k=0}^{2n}(-1)^k\binom{2n}k^{2a}=\left[x_1^{2n}\ldots x_{2a}^{2n}\right] (x_1-x_2)^{2n}(x_2-x_3)^{2n}\ldots (x_{2a-1}-x_{2a})^{2a}(x_{2a}+x_1)^{2n}\\= \left[x_1^{2n}\ldots x_{2a}^{2n}\right]F(x_1,\ldots,x_{2a}),$$ where $$F(x_1,\ldots,x_{2a})=\prod_{j=-(n-1)}^n(x_1-x_2-j)(x_3-x_2-j)(x_3-x_4-j)\ldots(x_{2a-1}-x_{2a}-j)(x_{2a}+x_1-2n-j).$$ We denote $$A=\{0,1,\ldots,2n\}$$ and express the above coefficient via the values of $$F$$ on $$A\times A\times \ldots \times A$$ applying the Combinatorial Nullstellensatz formula. It is not hard to see (pretty analogous to $$a=2$$ case which was considered in details in my answer to the previous question) that if $$F(x_1,\ldots,x_{2a})\ne 0$$ for $$x_i\in A$$ then we must have $$x_1=x_{2a-1}=0$$, $$x_{2a}=n$$. Then $$F(x_1,\ldots,x_{2n})$$ is divisible by $$((2n)!)^{2a}$$ and the denominator in the CN formula equals $$(-1)^{\sum x_i}\prod_{i=1}^{2a}x_i!(2n-x_i)!=((2n)!)^2 (n!)^2(-1)^{n+\sum_{i=2}^{2a-1}x_i}\prod_{i=2}^{2a-1}x_i!(2n-x_i)!$$. It is immediately seen that $$C$$ is divisible by $${2n\choose n}$$ (that already implies that $$\hat{S}(2a,n)$$ is divisible by $$C_n$$, as was earlier proved by Calkin by a different argument, see Vlad's reference). When $$n=2^m-1$$, using the fact that the product of $$2n$$ consecutive integers like $$\prod_{j=-(n-1)}^n(x_1-x_2-j)$$ is divisible by $$2\cdot (2n)!$$ unless $$x_1-x_2\in \{n,n+1\}$$ (again, see the explanation in the previous answer) and that $$(2n)!/(x_i!(2n-x_i)!)$$ is even when $$x_i$$ is odd, we see that the unique odd summand in our sum corresponds to $$x_1=x_3=\ldots=x_{2a-3}=0$$, $$x_2=x_4=\ldots=x_{2a-2}=n+1$$.