Does this recurrence always hit a power of 2?

First, we establish that $a_k = 3^kn + (3^k - 1)/2$ . This clearly holds for $k = 0$ , and assuming it holds for $k$ , $a_{k + 1} = 3a_k + 1 = 3 \left(3^kn + \frac{3^k - 1}{2} \right) + 1 = 3^{k + 1}n + \frac{3^{k + 1} - 3 + 2}{2} = 3^{k + 1}n + \frac{3^{k + 1} - 1}{2},$ so by induction, it holds for all $k \geq 0$ .

Take any integer $x > 2$ and consider $n = (3^x - 1)/2$ ; suppose there exist integers $j,k \geq 0$ such that $2^j = a_k = 3^kn + (3^k - 1)/2 = 3^k(n + 1/2) - 1/2$ , or $2^{j + 1} + 1 = 3^k(2n + 1)$ . Substituting $n$ , we have $2^{j + 1} + 1 = 3^{k + x}$ . By Mihăilescu's theorem, the only solution is $j + 1 = 3$ and $k + x = 2$ . Thus as $k \geq 0$ , this forces $x \leq 2$ , a contradiction. Hence, there exist $n$ for which the sequence never hits a power of 2.