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}


I conjecture that $a(\frac{4^n-1}{3})$ is always a cube of an integer
for any $p,q \in \mathbb{Z}$, $n\in \left\lbrace0, \mathbb{N}\right\rbrace$.


Is there a way to prove it?



Subsequence of the cubes
Experimenting with a CAS suggests an induction. In order to handle the induction, we need to consider the forms of the numbers involved. $\frac{4^m-1}{3} = 1 + 2^2 + 2^4 + \cdots + 2^{2m-2}$ alternates $1$ and $0$ bits. The map $2n + 1 \to n - 2^{f(n)}$ drops the rightmost bit (which is $1$) and clears the next least significant bit. The map $2n \to n$ drops the rightmost bit (which is $0$). And the map $2n \to 2n - 2^{f(n)}$ moves the least significant bit right one place. So the numbers which occur in the evaluation tree of $\frac{4^m-1}{3}$ are of the form $2^i + 2^j + 2^{j+2} + \cdots + 2^{j+2k}$ where $i \le j - 2$ and $k \ge 0$; and (when we get down to one bit) the form $2^i$.


Starting with the simplest case, when $i > 0$, $a(2^i) = pa(2^{i-1}) + qa(2^{i-1})$ so by induction $a(2^i) = (p+q)^i$.


For the more general case, let $A(i,j,k) = a(2^i + 2^j + 2^{j+2} + \cdots + 2^{j+2k})$ subject to the aforementioned constraints on $i,j,k$.


For $i > 0$, we have an even argument and use the second case of the recursion:
\begin{eqnarray\*}
A(i,j,k) &=& a(2^i + 2^j + 2^{j+2} + \cdots + 2^{j+2k}) \\
 &=& pa(2^{i-1} + 2^{j-1} + 2^{j+1} + \cdots + 2^{j+2k-1}) + qa(2^{i-1} + 2^j + 2^{j+2} + \cdots + 2^{j+2k}) \\
 &=& pA(i-1, j-1, k) + qA(i-1, j, k)
\end{eqnarray\*}


Then it's a trivial proof by induction that $$A(i,j,k) = \sum\_{u=0}^i \binom{i}{u} p^u q^{i-u} A(0, j-u, k)$$


For $i = 0$, we have an odd argument and use the third case of the recursion:
\begin{eqnarray\*}
A(0,j,k) &=& a(1 + 2^j + 2^{j+2} + \cdots + 2^{j+2k}) \\
 &=& a(2^{j+1} + \cdots + 2^{j+1+2(k-1)}) \\
 &=& \begin{cases}
 a(0) & \textrm{if } k=0 \\
 a(2^{j+1}) & \textrm{if } k=1 \\
 A(j+1, j+3, k-2) & \textrm{otherwise}
 \end{cases} \\
 &=& \begin{cases}
 1 & \textrm{if } k=0 \\
 (p+q)^{j+1} & \textrm{if } k=1 \\
 \sum\_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} A(0, j+3-u, k-2) & \textrm{otherwise}
 \end{cases}
\end{eqnarray\*}


Further CAS experimentation suggests that the theorem we need to prove is $$A(0, j, 2v-1) = A(0, j, 2v) = \left(p\frac{q^v-1}{q-1} + q^v\right)^{j+1} A(0, 2, 2v-2)$$


The first of those equalities is easy: $$A(0,j,2) = \sum\_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} A(0, j+3-u, 0) = \sum\_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} = (p+q)^{j+1}$$ so $A(0,j,1) = A(0,j,2)$ and since the only occurrence of $k$ in the third case is in the parameter $k-2$ the rest follows by induction on $v$.


The second equality is the interesting one. Again, by induction on $v$:


\begin{eqnarray\*}
A(0,j,2v) &=& \sum\_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} A(0, j+3-u, 2v-2) \\
 &=& \sum\_{u=0}^{j+1} \binom{j+1}{u} p^u q^{j+1-u} \left(p\frac{q^{v-1}-1}{q-1} + q^{v-1}\right)^{j+4-u} A(0, 2, 2v-4) \\
 &=& \left[ \sum\_{u=0}^{j+1} \binom{j+1}{u} p^u \left(pq\frac{q^{v-1}-1}{q-1} + q^v\right)^{j+1-u} \right] \color{Blue}{\left(p\frac{q^{v-1}-1}{q-1} + q^{v-1}\right)^3 A(0, 2, 2v-4)} \\
 &=& \left( p + pq\frac{q^{v-1}-1}{q-1} + q^v \right)^{j+1} \color{Blue}{A(0, 2, 2v-2)} \\
 &=& \left(p\frac{q^v-1}{q-1} + q^v\right)^{j+1} A(0, 2, 2v-2)
\end{eqnarray\*}
as desired.


The answer to the original question now drops out: $a\left(\tfrac{4^m-1}{3}\right) = A(0, 2, m-2)$, but $A(0, 2, k)$ has the form of a cube times $A(0, 2, k-2)$ so by induction it's always a cube.


