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$.

  • $\begingroup$ @FedorPetrov: the sum run through $0$ to $2n$. Why do you expect it to drop to $n$? $\endgroup$ Feb 7 at 14:22
  • $\begingroup$ Because I am confused: the sum in RHS in the main identity for $a=2$ was for $k$ from 0 to $n$. $\endgroup$ Feb 7 at 14:43
  • $\begingroup$ @FedorPetrov: no, it was up to $2n$. $\endgroup$ Feb 7 at 15:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vlad Matei
    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$.


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.