Infinitely many sufficiently large powers in linear recurrences 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$.
 A: If your recurrence has a unique (simple) dominant root at some place (meaning one of strictly maximal absolute value; the $2$ in A.M.'s example does not count because of the multiplicity), then P. Corvaja and U. Zannier have shown that infinitely many $d$-th powers imply an identity of the form $a(qn+r) = g(n)^d$ for all $n$. See their paper "Some new applications of the Subspace theorem," Compositio Math., 2002. I can also refer you to Zannier's survey "Diophantine equations with linear recurrences: an overview of some recent progress," where this is stated as Theorem G.
In the general case, when there is no dominant root, your Q1 is still a wide open problem for all I know. 
PS: I looked at your previous edits, and was surprised to see a link included to Zannier's survey. The result which you had stated in your original question would have answered everything you could ask for here, but it has only been proved under the dominant root assumption. It is surely expected to hold in greater generality - for instance, if there is some simple root $\alpha$ such that $\beta/\alpha$ is not a root of unity for any other root $\beta$; - but not in full generality, as the example $a(n) = n$ shows already. Incidentally, as you can see from this example, your addendum does not give the right condition.
