**Edit** Aaron solved the original question with the
fourth order $$ a(n)=n2^n+\frac{(-1)^n-1^n}{2} $$
trying to make the question harder.

Let $a(n)$ be a linear recurrence with constant coefficients, of exponential growth and without fixed prime factor after the initial terms (to avoid $b^n$). The order of $a(n)$ is $r$.

Let the roots of the characteristic polynomial of $a(n)$ be $\alpha_1,\alpha_2 \ldots \alpha_k$.

Then $a(n) = \sum_{i=1}^k c_i \alpha_i^n$ where $c_i$ is algebraic number or polynomial in $n$ with algebraic coefficients.

**Added** Suppose no subset sum $\sum_i c_i \alpha_i^n$ vanishes.

Suppose $a(n)$ contains infinitely many $d$-th powers (I believe this is impossible for binary recurrences).

Q1 Is $d$ bounded by $O(r)$?

Q2 Is there an explicit example of $a(n)$ with $r$ small and $ d \ge 2 r$?

It is possible for all $n$, $a(n)=g(n)^d$, but in this case I believe $ d < r$.