Let $p$ and $q$ be integers. 

Let  $f(n)$ be [A007814][1], 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?

  [1]: https://oeis.org/A007814