Linear recurrences and polynomial 'hits'

Question

It is an established fact that the only Fibonacci numbers that are squares are $F_1 = F_2 = 1$ and $F_{12} = 144$, and many other similar results can be found here: http://math.la.asu.edu/~checkman/SquareFibonacci.html#ref2

The results above are of the form "if $f(x)$ is a fixed polynomial of degree 2 in $\mathbb{Z}[x]$, then there are only finitely many terms of a linear recurrence that are of that form". However, I am interested in a 'positive result': is there any known linear recurrence $L_n$ defined by say $L_n = a_k L_{n-1} + \cdots + a_1 L_{n-k-1}$, with a fixed initial condition, and a polynomial $f(x) \in \mathbb{Z}[x]$ of degree at least 2 (distinct from the polynomial defining the linear recurrence, that is, if we write $L_n$ explicitly as $b_k \beta_k^n + \cdots + b_1 \beta_1^n$, then we exclude $f(x) = (x - \beta_1) \cdots (x - \beta_k)$) such that there are infinitely many terms $L_n = f(m)$, for $m \in \mathbb{Z}$?

Edit: it has been noted in an answer below that there are examples. Are there any necessary or sufficient conditions that can be imposed to ensure infinitely many solutions?

Answer 1

Since the Fibonacci numbers seem an acceptable recurrence, consider these identities:

• For $m$ even $F_{3m}=5F_{m}^3+3F_{m}$
• For $m$ odd $\ F_{3m}=5F_{m}^3-3F_{m}$

So a sixth are of the form $5x^3+3x $ and another sixth are of the form $5x^3-3x.$ There are similar results of every odd degree but I don't know about even degree. The same would be true (I think) for any sequence given by a recurrence with initial values $0,1$ and rule $a_{n+1}=ca_n+a_{n-1}$

---

For another kind of example, the initial values $a_0=\alpha,$ $a_1=2\alpha+2$

and rule $a_{n+1}=4(a_n-a_{n-1}).$

yield $a_n=(n+\alpha)2^n$ so, with $\alpha=6$, it would seem that $a_n$ is a square exactly for $n=4m^2-6.$

Using $5^n$ in place of $2^n$ would be even more exotic, then one also has $n=5(2m+1)^2-6$.

---

Looking at the the most simple cases, in terms of the order $k$ of the recurrence $L_n = a_k L_{n-1} + \cdots + a_1 L_{n-k-1}$ and/or the degree $d$ of the polynomial $f(x)$ allows some speculation on what can happen in general.

• For $d=0$ we have a constant polynomial $f(x)=c.$ An integer sequence $L_n$ (given by a linear homogeneous recurrence with constant coefficients) can be periodic with in which case $L_n=c$ happens, if at all, when $n$ belongs to one or more congruence classes modulo the period $p.$ Otherwise it happens finitely often. $L_{n+6}-L_n=0$ gives period $6$ as does $L_{n+2}-L{n+1}+L_n$ (since $x^6-1=(x^2-x+1)(x^4+x^2-x-1)$). But if $L_n$ is not periodic then $L_n=c$ happens only finitely often (perhaps $k$ times at most?)

• For $d=1$ we have a linear polynomial $f(x)=kx+c$. The values $L_n \bmod k$ are (eventually) periodic with a period $p \le k^d$ so $L_n \bmod k=c$ happens either finitely often or else exactly when $n$ belongs to certain congruence classes $\bmod p$ (with small exceptions, for example $2\ 3^n$ has the form $9x+0$ except when $n=0,1$.

• For $k=1$ the sequence is $L_n=A\ b^n.$ What can be said then? For $f(x)=cx^s$ things are fairly clear.

• With $k=2$ there is already much to think about but special cases include arithmetic progressions $An+B$ which satisfy $L_{n+2}-2L_{n+1}+L_n=0$, and more generally $(An+B)b^n$ from $L_{n+2}-2bL_{n+1}+b^2L_n=0$ Here the condition may be that the index $n$ itself is of a certain form of degree $d$ or less.

---

Any polynomial satisfies a recurrence, so consider $L_n=n^2(2n^2-1)$ or $L_n=n^2(2n^2-1)2^{n+1}$ either is a square for the alternate values of the Pell sequence $1,2,5,12,29,70,\cdots$

So I would wildly speculate that given two sequences $L,M$ ( given by LHRCC) we have that $L_n=M_m$ happens (with finitely many exceptions), either never or else whenever the index $n$ itself is a member of a sequence ( or one of a few sequences) given by such a recurrence.

Answer 2

The space of sequences satisfying a linear recurrence is closed under multiplication (exercise). In particular, $F_n^2$ is such a sequence. Or, more simply: every polynomial sequence itself satisfies a linear recurrence (exercise).

I think you want to impose the condition that $L_n$ is not itself of the form $f(L_n')$ where $L_n'$ satisfies a linear recurrence. But even then there are examples, e.g. $L_n = 1 - dn^2$ is a square infinitely often for, say, $d \ge 2$ because we can find infinitely many solutions to the corresponding Pell's equation.

Okay, one extra condition: $L_n$ should grow faster than a polynomial. Now I don't have an example. More precisely, I don't know an example of an integer sequence $L_n$ and a polynomial $f(x) \in \mathbb{Z}[x]$ such that

• $L_n$ satisfies a linear recurrence,
• there are infinitely many $n$ for which $L_n = f(m)$ for some $m$,
• there is no sequence $L_n'$, not necessarily of integers, satisfying a linear recurrence such that $L_n = f(L_n')$,
• $L_n$ grows faster than a polynomial.

Now we're trying to solve some potentially quite difficult exponential Diophantine equations.

Answer 3

First more examples for Lucas numbers:

$$ L_{4n} = L_{2n}^2 - 2 $$

More polynomials identities for Lucas numbers from OEIS:

 The first six multiplication formulae are:

 L(2n) = (L(n))^2 - 2*(-1)^n
 L(3n) = (L(n))^3 - 3*((-1)^n)*L(n)
 L(4n) = (L(n))^4 - 4*((-1)^n)*(L(n))^2 + 2
 L(5n) = (L(n))^5 - 5*((-1)^n)*(L(n))^3 + 5*L(n)
 L(6n) = (L(n))^6 - 6*((-1)^n)*(L(n))^4 + 9*(L(n))^2 - 2*(-1)^n 

These are closely related to Chebyshev polynomials at $i$.

For the question about infinitely many solutions, On integral points on biquadratic curves and near multiples of squares in Lucas sequences ,Max A. Alekseyev, Szabolcs Tengely solves the degree 2 case for Lucas sequences - check p. 10 for examples.

Basically Lucas sequences are integral points on a genus $0$ curve. After substituting $x = f(x)$ you increase the degree and if you increase the genus this is sufficient condition for finitely many solutions.