Subsequences of odd powers

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} which can also be expressed with a product $$a(n) = [t(n) = 0] + [t(n) > 0]\prod\limits_{k=0}^{t(n)-1} (q^{k+1} + p\sum\limits_{j=0}^{k} q^{j})^{g(n, k)}$$ where $$t(n)=\begin{cases} [n=2],&\text{if $n<4$;}\\ t(2^{m-1} + k),&\text{if $0 \leqslant k < 2^{m-1}, m > 1$ where $n = 2^m + k$;}\\ t(k) + A010060(k - 2^{m-1}),&\text{if $2^{m-1} \leqslant k < 2^m, m > 1$ where $n = 2^m + k$.} \end{cases}$$ $$g(n,0)=\begin{cases} [n=2]+2\cdot [n=4]+[n=6]+[n=7],&\text{if $n<8$;}\\ g(2^{m-1} + k,0) - A010060(k) + 1,&\text{if $0 \leqslant k < 2^{m-1}, m > 2$ where $n = 2^m + k$;}\\ g(2^{m-2} + k,0) + 1,&\text{if $2^{m-1} \leqslant k < 3\cdot 2^{m-2}, m > 2$ where $n = 2^m + k$;}\\ g(2^{m-3} + k,0) + A010060(k - 3\cdot 2^{m-2}) ,&\text{if $3\cdot 2^{m-2} \leqslant k < 7\cdot 2^{m-3}, m > 2$ where $n = 2^m + k$;}\\ 1,&\text{if $7\cdot 2^{m-3} \leqslant k < 2^m, m > 2$.} \end{cases}$$ $$g(n, k) = g(h(n, k), 0), n \geqslant 0, k > 0,$$ $$h(n, k) = h(h(n, 1), k - 1), n \geqslant 0, k > 1,$$ $$h(n , 1) = s(s(n)), n \geqslant 0,$$ $$s(n) = A053645(n), n > 0, s(0) = 0.$$ Here are the links to the sequences: A010060, A053645.

I conjecture that $a(\frac{2^{kn}-1}{2^k-1})=(a(2^n-1))^{2k-1}$ for $n \geqslant 0$, $k>0$. This question generalizes the following: Subsequence of the cubes.

Is there a way to prove it using expression with a product?

Answer 1

Quite similarly to my answer to the previous question, we have that for $n=2^tk$ with odd $k$, $$ a(n)=\sum_{i=0}^t \binom{t}{i}p^{t-i}q^i a(2^i(k-1)+1). $$

It further follows that for $n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_s+1}))\dots)$ with $t_j\geq 0$, we have \begin{split} a(n) &= \sum_{i_1=0}^{t_1} \binom{t_1}{i_1} p^{t_1-i_1}q^{i_1} \sum_{i_2=0}^{t_2+t_3+1+i_1} \binom{t_2+t_3+1+i_1}{i_2}p^{t_2+t_3+1+i_1-i_2}q^{i_2} \sum_{i_3=0}^{t_4+t_5+1+i_2} \\ &\qquad\dots \sum_{i_\ell=0}^{t_{2\ell-2}+t_{2\ell-1}+1+i_{\ell-1}} \binom{t_{2\ell-2}+t_{2\ell-1}+1+i_{\ell-1}}{i_\ell}p^{t_{2\ell-2}+t_{2\ell-1}+1-i_\ell}q^{i_\ell} \\ &=\prod_{j=0}^{\ell-1} \bigg(q^{\ell-j}+p\frac{q^{\ell-j}-1}{q-1}\bigg)^{t_{2j}+t_{2j+1}+1}, \end{split} where we conveniently define $\ell:=\left\lfloor\frac{s+1}2\right\rfloor$ and $t_0:=-1$.

---

Now, for $n=\frac{2^{kn}-1}{2^k-1}$ we have $s=n$, $\ell=\left\lfloor\frac{n+1}2\right\rfloor$, $t_1=0$ and $t_j=k-1$ for all $j\in\{2,3,\dots,s\}$, implying that $$a(\tfrac{2^{kn}-1}{2^k-1}) = \prod_{j=1}^{\lfloor (n-1)/2\rfloor} \bigg(q^{\lfloor (n+1)/2\rfloor-j}+p\frac{q^{\lfloor (n+1)/2\rfloor-j}-1}{q-1}\bigg)^{2k-1}.$$ In particular, setting $k=1$, we get $$a(2^{n}-1) = \prod_{j=1}^{\lfloor (n-1)/2\rfloor} \bigg(q^{\lfloor (n+1)/2\rfloor-j}+p\frac{q^{\lfloor (n+1)/2\rfloor-j}-1}{q-1}\bigg),$$ and thus $$a(\tfrac{2^{kn}-1}{2^k-1}) = a(2^{n}-1)^{2k-1}.$$