Generating function for partial sums of the sequence

Question

Let $p$ and $q$ be integers.

Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.

Then we have an integer sequence given by \begin{align} a(0)=a(1)&=1\\ a(2n)& = pa(n)+qa(2n-2^{f(n)})\\ a(2n+1) &= a(n-2^{f(n)}) \end{align}

Let $$s(n) = \sum\limits_{k=2^{n-1}}^{2^{n}-1}a(k), s(0)=1$$ then I conjecture that $$\sum\limits_{k=0}^{\infty}s(k)x^k=\frac{1}{1-x}+\sum\limits_{k=2}^{\infty}\left(\prod\limits_{j=2}^{k}(q^{j-1}+p\sum\limits_{r=0}^{j-2}q^r)\right)\frac{x^{2(k-1)}\left(1-(-1+q^{k-1}+p\sum\limits_{s=0}^{k-2}q^s)x\right)}{(1-x)\prod\limits_{i=2}^{k}\left(1-(q^{i-1}+p\sum\limits_{t=0}^{i-2}q^t)x\right)^2}$$ There also exist finite variant: $$\sum\limits_{k=0}^{n}s(k)x^k=\frac{1}{1-x}+\sum\limits_{k=2}^{\left\lfloor\frac{n}{2}\right\rfloor+1}\left(\prod\limits_{j=2}^{k}(q^{j-1}+p\sum\limits_{r=0}^{j-2}q^r)\right)\frac{x^{2(k-1)}\left(1-(-1+q^{k-1}+p\sum\limits_{s=0}^{k-2}q^s)x\right)}{(1-x)\prod\limits_{i=2}^{k}\left(1-(q^{i-1}+p\sum\limits_{t=0}^{i-2}q^t)x\right)^2}$$

Is there a way to prove it?

Answer 1

As proved in this answer, if we represent $n$ as $n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_m+1}))\dots)$ with $t_j\geq 0$, then \begin{split} a(n) = P(\ell)^{t_1}\prod_{j=1}^{\ell-1} P(\ell-j)^{t_{2j}+t_{2j+1}+1}, \end{split} where $\ell:=\left\lfloor\frac{m+1}2\right\rfloor$ and $$P(k) := q^k+p\frac{q^k-1}{q-1}.$$ Notice that this does not depend on $t_m$ when $m$ is even.

Grouping the summands in $s(n)$ by the number of unit bits (very much like in this other answer), for $n\geq 1$ we have \begin{split} s(n) &= \sum_{m=1}^n\ \sum_{t_1+t_2+\dots+t_{m}=n-m}\ P(\lfloor(m+1)/2\rfloor)^{t_1} \prod_{j=1}^{\lfloor(m-1)/2\rfloor} P(\lfloor(m+1)/2\rfloor-j)^{t_{2j}+t_{2j+1}+1}\\ &= \sum_{m=1}^n\ [x^{n-m}]\ \frac1{1-P(\lfloor(m+1)/2\rfloor)x}\cdot\prod_{j=1}^{\lfloor(m-1)/2\rfloor} \frac{P(j)}{(1-P(j)x)^2}\cdot\frac{1+\frac{(-1)^m-1}2x}{1-x}\\ &= [x^n]\ \sum_{m=1}^\infty\ \frac{x^m}{1-P(\lfloor(m+1)/2\rfloor)x}\cdot\prod_{j=1}^{\lfloor(m-1)/2\rfloor} \frac{P(j)}{(1-P(j)x)^2}\cdot\frac{1+\frac{(-1)^m-1}2x}{1-x}. \end{split} That is, the generating function for $s(n)$ is $$\sum_{n\geq 0} s(n)x^n = 1+\frac1{1-x}\sum_{m=1}^\infty\ \frac{x^m(1+\frac{(-1)^m-1}2x)}{1-P(\lfloor(m+1)/2\rfloor)x}\cdot\prod_{j=1}^{\lfloor(m-1)/2\rfloor} \frac{P(j)}{(1-P(j)x)^2}.$$

Combining terms for $m=2k-1$ and $m=2k$, we can rewrite it as $$\sum_{n\geq 0} s(n)x^n = 1+\frac{1}{1-x}\sum_{k=1}^\infty\ \frac{x^{2k-1}}{1-P(k)x}\cdot\prod_{j=1}^{k-1} \frac{P(j)}{(1-P(j)x)^2},$$ which is quite close to the conjectured formula.