Let $p$ and $q$ be integers.


Let $f(n)$ be [A007814](https://oeis.org/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?



Generating function for partial sums of the sequence
As proved in [this answer](https://mathoverflow.net/q/405996), 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](https://mathoverflow.net/q/405210)), 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.


