# 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$.

• I don't understand the question. What about $a(n) = b^n$ where $b$ is a $d^{th}$ power? – Qiaochu Yuan Jan 22 '14 at 4:42
• @QiaochuYuan I tried to disallow your example by not allowing fixed factor ($b$ in your case). – joro Jan 22 '14 at 7:30
• I'm sure that there is a result, but you may not have the conditions right. What about $a(n)=n2^n+\frac{(-1)^n-1^n}{2}$ which satisfies a $4$th order recurrence. This is a $2d$th power infinitely often but not for an arithmetic progression ( I think.) – Aaron Meyerowitz Jan 22 '14 at 7:31
• @AaronMeyerowitz Thanks, this answers the OP. Indeed the conditions are not right. Ideas to improve the question? For a start I suppose I want no proper subset sum of the coefficient and powers of roots of characteristic polynomial to vanish. – joro Jan 22 '14 at 8:45
• @joro: I don't understand what you mean by a fixed factor. $a(0) = 1$ here. – Qiaochu Yuan Jan 22 '14 at 9:00

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.
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.
• Thanks. So Q2 is not clear too? If $a(n)=0$ infinitely often, $a(n)+ C^n$ will be linear recurrence too and will be a power $C^n$ inf. often. So this construction might imply subset sum of $a(n)$ vanishes. – joro Jan 23 '14 at 8:21
• Q2: How about $a(n) = n$? [Apart from such obvious examples, however, it is expected that infinitely many $d$-th powers would yield an identity $a(qn+r)= g(n)^d$ with $g$ a linear recurrence, whence a fortiori $d \leq r$.] – Vesselin Dimitrov Jan 23 '14 at 15:15
• I think your first sentence is missing hypothesis because of the recurrence $2^n+1^n+(-1)^n$. – joro Mar 30 '15 at 11:31
• @joro: This is not a counterexample, as $2^n+1^n+(-1)^n$ is not a square for any $n$. – Vesselin Dimitrov Mar 30 '15 at 16:32
• Why do insist on square? $1^n+(-1)^n$ cancel for odd $n$, leaving $2^{2m+1}$. Appears to me these are all perfect odd powers. – joro Mar 30 '15 at 17:21