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?

  • 4
    $\begingroup$ Given any polynomial, the sequence of values of that polynomial satisfies a constant-coefficient linear recurrence. $\endgroup$ Nov 6 '13 at 23:12
  • $\begingroup$ That isn't the general form of a sequence satisfying a linear recurrence. In general there are polynomial factors. $\endgroup$ Nov 6 '13 at 23:58
  • $\begingroup$ Why exclude the defining polynomial? The sequence $0,1,5,19,65,\cdots$ with general term $3^n-2^n$ has recurrence $a_{n+2}-5a_{n+1}+6a_n=0$ so defining polynomial $f(x)=x^2-5x+6=(x-2)(x-3)$ but we won't have $a_n=f(m)$ for positive $n$ since one side is odd and the other even. $\endgroup$ Nov 8 '13 at 10:16

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.


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.

  • 4
    $\begingroup$ Doesn't the sequence $2^n$ satisfy all those conditions? It is, say, a square for infinitely many $n$. $\endgroup$ Nov 6 '13 at 23:21
  • $\begingroup$ @Gerry: I didn't want to impose that $L_n'$ consists of integers, so in that case we can take $f(x) = x^2, L_n' = \sqrt{2}^n$. $\endgroup$ Nov 6 '13 at 23:23
  • $\begingroup$ Maybe: there is no sequence $L_{an+b}'$, not necessarily of integers, satisfying a linear recurrence such that $L_{an+b} = f(L_{an+b}')$ for fixed $a,b$ and all $n$. So not on an arithmetic progression. $\endgroup$ Nov 7 '13 at 3:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.