Correctness of the algorithm for the A329369, A347205 and related sequences

Question

• Let $a(n)$ be A347205. It is enough for us to know that

$$ a(2^m(2k+1)) = \sum\limits_{j=0}^{m}a(2^jk), \\ a(0) = 1 $$

• Let $b(n)$ be A329369. It is enough for us to know that

$$ b(2^m(2k+1)) = \sum\limits_{j=0}^{m}\binom{m+1}{j} b(2^jk), \\ b(0) = 1 $$

• Let $T(n,k)$ be A101211 (i.e, triangle read by rows: $n$-th row is length of run of leftmost $1$'s, followed by length of run of $0$'s, followed by length of run of $1$'s, etc., in the binary representation of $n$).

• Let $c(n)$ be A005811 (i.e., number of runs in binary expansion of $n$ ($n>0$); number of $1$'s in Gray code for $n$).

• Suppose that we want to compute $b(n)$ without recursion. Is there a way to do it? Presumably, there should be at least one way. So here it is:

• Start with the vector $s$ of ones with the length $L=\sum\limits_{i=1}^{\frac{c(2n)}{2}}T(2n,2i)$. Also, let $t$ be an identical vector. After that for $i$ from $1$ to $\frac{c(2n)}{2}$ apply $A=\sum\limits_{q=1}^{i-1}T(2n,2q)$ and then (staying into the first cycle) for $j$ from $1$ to $T(2n,2i-1)$ and for $k$ from $A+2$ to $L$ apply $$ t_k = \sum\limits_{q=1}^{k-A}\binom{k-A}{q-1}s_{q+A}. $$

• After ending the last cycle and while we stay at the second cycle, we also need to apply $s = t$.

I conjecture that $s_L$ after the whole transformation is equals to $b(n)$.

Here is the PARI/GP program to check it numerically:

a(n) = if(n == 0, 1, my(A = valuation(n, 2), B = n\2^(A+1)); sum(j=0, A, a(2^j*B)))
b(n) = if(n == 0, 1, my(A = valuation(n, 2), B = n\2^(A+1)); sum(j=0, A, binomial(A+1, j)*b(2^j*B)))
a1(n) = {my(n = 2*n, A = 1, v1, v2, v3); v1 = [];
for(i=0, logint(n, 2), 
if(bittest(n, i) == bittest(n, i+1), A++,
v1 = concat(v1, A); A = 1));
v1 = Vecrev(v1);
for(i=2, #v1/2, v1[2*i] += v1[2*(i-1)]);
v2 = vector(v1[#v1], i, 1); v3 = v2;
for(i=1, #v1/2, 
A = if(i==1, 0, v1[2*(i-1)]);
for(j=1, v1[2*i-1],
for(k=A+1, #v2,
v3[k] = sum(q=1, k-A, v2[q+A]));
v2 = v3));
v2[#v2]}
b1(n) = {my(n = 2*n, A = 1, v1, v2, v3); v1 = [];
for(i=0, logint(n, 2), 
if(bittest(n, i) == bittest(n, i+1), A++,
v1 = concat(v1, A); A = 1));
v1 = Vecrev(v1);
for(i=2, #v1/2, v1[2*i] += v1[2*(i-1)]);
v2 = vector(v1[#v1], i, 1); v3 = v2;
v4 = vector(#v2+1, i,
vector(i, j, j == 1 || j == i));
for(i=3, #v4, for(j=2, i-1, 
v4[i][j] = v4[i-1][j] + v4[i-1][j-1]));
for(i=1, #v1/2, 
A = if(i == 1, 0, v1[2*(i-1)]);
for(j=1, v1[2*i-1],
for(k=A+1, #v2,
v3[k] = sum(q=1, k-A, v4[k - A + 1][q]*v2[q+A]));
v2 = v3));
v2[#v2]}
test1(n) = a1(n) == a(n)
test2(n) = b1(n) == b(n)

Is there a way to prove it?

Answer 1

Generalise to $$b(2^m(2k+1)) = \sum\limits_{j=0}^{m}C_{m+1,j} \, b(2^jk), \\ b(0) = 1$$

Consider the infinite matrices: $$M_0 = \begin{pmatrix} 0 & 1 & 0 & 0 & \cdots \\ 0 & 0 & 1 & 0 & \cdots \\ 0 & 0 & 0 & 1 & \ddots \\ \vdots & \vdots & \vdots & \ddots & \ddots \end{pmatrix} \hspace{2em} M_1 = \begin{pmatrix} C_{1,0} & 0 & 0 & 0 & \cdots \\ C_{2,0} & C_{2,1} & 0 & 0 & \cdots \\ C_{3,0} & C_{3,1} & C_{3,2} & 0 & \ddots \\ \vdots & \vdots & \vdots & \ddots & \ddots \end{pmatrix} \hspace{2em} t = \begin{pmatrix} 1 \\ 1 \\ 1 \\ \vdots \end{pmatrix}$$

I claim that if $n = 2^s + c_{s-1}2^{s-1} + c_{s-2}2^{s-2} + \cdots c_0$ then $$M_{c_0} M_{c_1} \cdots M_{c_{s-1}} M_1 t = \begin{pmatrix} b(n) \\ b(2n) \\ b(4n) \\ \vdots \end{pmatrix}$$

By induction on the bit length of $n$. We can take $n=0$ as a trivial base case even though it's not strictly covered by the claim, and the induction step from $n$ to $2n$ is trivial, so that leaves only the inductive step from $n$ to $2n+1$: i.e. that $$M_1 \begin{pmatrix} b(n) \\ b(2n) \\ b(4n) \\ \vdots \end{pmatrix} = \begin{pmatrix} b(2n+1) \\ b(2(2n+1)) \\ b(4(2n+1)) \\ \vdots \end{pmatrix}$$

Indexing from $0$ and substituting $n=k$, row $m$ of the LHS is $\sum_{j=0}^m C_{m+1,j} \, b(2^m k)$ and row $m$ of the RHS is $b(2^m (2k+1))$ so we reproduce exactly the recurrence.

I further claim that this matrix process is equivalent to your triple-looped algorithm, but I will not address that claim in detail.

In answer to the additional question about $d(2n+1)=kd(n)$, note that $d(2n+1) = C_{1,0} \, d(n)$ and nothing in the process or proof above requires $C_{1,0}$ to be $1$.