The signed A005811 Hankel transform for $x+1/r(x^2)$

Proof and exact sign formula for the binary-run Hankel conjecture

Let

$$r(x)=\sum_{j\geq0}x^{2^j-1}, \qquad G(x)=x+\frac1{r(x^2)}=\sum_{j\geq0}g_jx^j,$$

and define

$$T_n=\det(g_{i+j})_{0\leq i,j\leq n}.$$

Write $\rho(N)$ for the number of runs in the ordinary binary expansion of the positive integer $N$, and put

$$J_N=\det(r_{i+j+1})_{0\leq i,j<N}, \qquad J_0=1. \tag{1}$$

We prove the stronger signed identity

$$\boxed{ T_n=(-1)^nJ_{n+1}\rho(n+1) \qquad(n\geq0). } \tag{2}$$

Since $J_N\in\{-1,1\}$, this gives

$$|T_n|=\rho(n+1)=\operatorname{A005811}(n+1), \tag{3}$$

which proves Conjecture 13 of Paul Barry, Conjectures and results on some generalized Rueppel sequences.

The proof uses the established determinant and sign theorems of J.-P. Allouche, G.-N. Han, and J. Shallit, On some conjectures of P. Barry, Journal of Number Theory 228 (2021), 108--132, Lemma 20 and Theorem 22 for the different series $1-xr(x)$; their preprint is also available. Their earlier results concern conjectures from Barry's 2020 paper. The key additional step here is an exact determinant transformation connecting their series to the distinct Conjecture 13 in Barry's later 2021 paper.

Two reciprocal Hankel transformations

Let

$$Q(x)=\frac1{r(x)}=\sum_{j\geq0}q_jx^j.$$

Because

$$r(x)=1+xr(x^2), \tag{4}$$

we have

$$G(x)=x+\frac{x}{r(x)-1} =\frac{xr(x)}{r(x)-1}. \tag{5}$$

Consequently,

$$\frac1{G(x)}=\frac{1-Q(x)}x. \tag{6}$$

Since $q_0=1$, $q_1=-1$, and $q_2=1$, this becomes

$$\frac1{G(x)}=1-x-x^2V(x), \qquad V(x)=\sum_{j\geq0}q_{j+3}x^j. \tag{7}$$

The standard reciprocal Hankel identity states that, whenever

$$P(x)=\frac1{1+cx-x^2W(x)},$$

one has

$$\det([x^{i+j}]P(x))_{0\leq i,j<N} =\det([x^{i+j}]W(x))_{0\leq i,j<N-1}. \tag{8}$$

This follows immediately from the reciprocal-series determinant identity

$$\det(b_{i+j+2})_{0\leq i,j<t} =(-1)^t\det(a_{i+j})_{0\leq i,j\leq t}, \tag{9}$$

where $\sum a_jx^j$ and $\sum b_jx^j$ are reciprocal series with constant coefficient $1$.

Taking $P=G$ and $W=V$ therefore gives

$$\det(g_{i+j})_{0\leq i,j<N} =\det(q_{i+j+3})_{0\leq i,j<N-1}. \tag{10}$$

We also need the following universal complementary-minor identity:

$$\det(q_{i+j+3})_{0\leq i,j<t} =(-1)^{t+1} \det(r_{i+j-1})_{0\leq i,j<t+2}, \qquad r_{-1}=0. \tag{11}$$

For completeness, set

$$h_j=r_j, \qquad e_j=(-1)^jq_j, \qquad h_j=e_j=0\quad(j<0).$$

The reciprocal relation $r(x)Q(x)=1$ is precisely

$$\left(\sum_{j\geq0}h_jx^j\right) \left(\sum_{j\geq0}e_j(-x)^j\right)=1. \tag{12}$$

Applying the dual Jacobi--Trudi identity to the rectangular partition $(t^{\,t+2})$ gives

$$\det(e_{t+2-i+j})_{0\leq i,j<t} =\det(h_{t-i+j})_{0\leq i,j<t+2}. \tag{13}$$

Reversing the rows on both sides and substituting $q_j=(-1)^je_j$ yields exactly (11).

Define

$$S_M=\det(r_{i+j-1})_{0\leq i,j<M} =\det([x^{i+j}]\,xr(x))_{0\leq i,j<M}. \tag{14}$$

Combining (10) and (11), with $t=N-1$, gives the new exact bridge

$$\boxed{ \det(g_{i+j})_{0\leq i,j<N}=(-1)^NS_{N+1}. } \tag{15}$$

Reduction to the proved Rueppel determinant theorem

Let

$$B(x)=1-xr(x), \qquad D_M=\det([x^{i+j}]B(x))_{0\leq i,j<M}. \tag{16}$$

The Hankel matrix of $B$ differs from the negative Hankel matrix of $xr$ only in its upper-left entry. Expanding in that entry gives

$$D_M=(-1)^MS_M+(-1)^{M-1}J_{M-1}. \tag{17}$$

Allouche, Han, and Shallit prove in their Lemma 20 that

$$\operatorname{sgn}(D_M)=(-1)^{M-1}J_{M-1} \qquad(M\geq1). \tag{18}$$

Their Theorem 22, together with their identification of the auxiliary sequence in Theorem 2, gives

$$|D_M|=1+\rho(M-1) \qquad(M\geq1), \tag{19}$$

where $\rho(0)=0$.

Substituting (18)--(19) into (17), we obtain

$$\begin{aligned} (-1)^{M-1}J_{M-1}\bigl(1+\rho(M-1)\bigr) &=(-1)^MS_M+(-1)^{M-1}J_{M-1},\\ S_M&=-J_{M-1}\rho(M-1). \end{aligned} \tag{20}$$

Taking $M=N+1$ in (15) now yields

$$\det(g_{i+j})_{0\leq i,j<N} =(-1)^{N+1}J_N\rho(N). \tag{21}$$

With $N=n+1$, this is precisely the signed formula (2).

The sign is explicit at every index

The Rueppel coefficients satisfy

$$r_{2j}=\begin{cases}1,&j=0,\\0,&j\geq1, \end{cases} \qquad r_{2j+1}=r_j. \tag{22}$$

The ordinary Rueppel Hankel determinant has the classical evaluation

$$R_t=\det(r_{i+j})_{0\leq i,j<t} =(-1)^{\binom t2}. \tag{23}$$

Separating even and odd indices in the matrix defining $J_N$ gives

$$\begin{aligned} J_0&=1,\\ J_{2t}&=R_tJ_t,\\ J_{2t+1}&=R_{t+1}J_t. \end{aligned} \tag{24}$$

In particular, $J_N\in\{-1,1\}$ for every $N$, and (24) computes the exact sign in (2) directly from the binary expansion of $n+1$. Thus the first values are

$$(T_n)_{n\geq0} =1,-2,-1,2,-3,-2,-1,2,-3,4,3,2,-3,\ldots,$$

and their absolute values are exactly the binary-run sequence predicted in Conjecture 13.