Does $a_0=0, a_1=1, a_{n+2}=2a_{n+1}-3a_n$ ever return to 1 or -1 for $n>3$?

Question

The sequence in question is the Lucas or Generalized Fibonacci sequence A088137. It's easy to write down its generating function $\frac{x}{1-2x+3x^2}$ and an explicit formula

$a_n = \frac{\sqrt{2}}{2}\mbox{Im}\left( (1+\sqrt{-2})^n\right)$.

The absolute values $|a_n|$ seem to grow quite rapidly, but I'm unable to rule out the possibility that a high power of $1+\sqrt{-2}$ will conspire to have an incredibly small argument.

Is it true that $|a_n|=1$ only for $n=1,3$?

EDIT: $a_n=-1$ never occurs and this can easily be verified by reducing mod 11.

Answer 1

Method 1 - Bilu-Hanrot-Voutier theorem on Lucas sequences.

First some definitions,

• Lucas pair - A Lucas pair is a pair $(\alpha,\beta)$ of algebraic integers such that $\alpha + \beta$ and $\alpha\beta$ are non-zero coprime rational integers and $\frac{\alpha}{\beta}$ is not a root of unity.

• Lucas numbers - Given a Lucas pair, the corresponding sequence of Lucas numbers is the sequence defined by $$u_n = u_n(\alpha,\beta) = \frac{\alpha^n - \beta^n}{\alpha - \beta}, \quad \text{ for } n = 0, 1, 2, \ldots$$

• Primitive divisor - Given a Lucas pair $(\alpha, \beta)$ and corresponding Lucas numbers $(u_n)$, a primitive divisor for $u_n$ is a prime divisor $p$ of $u_n$ such that $$p | u_n \quad\text{ and }\quad p \not| (\alpha-\beta)^2 u_1 u_2\dots u_{n-1}$$

In 2001, Bilu, Hanrot and Voutier has proved$\color{blue}{^{[1]}}$ in general, for any sequence of Lucas numbers $(u_n)$ and any $n > 30$, $u_n$ has a primitive divisor. As a consequence, $|u_n| > 1$ for $n > 30$.

For our sequence at hand, we have

$$a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}\quad\text{ with }\quad \begin{cases} \alpha &= 1 + \sqrt{-2}\\ \beta &= 1 - \sqrt{-2} \end{cases} $$ and it is easy to check this pair of $(\alpha,\beta)$ is a Lucas pair. This implies $|a_n| \ne 1$ for $n > 30$.

By brute force, one can verify for the remaining $n \le 30$, $|a_n| = 1$ when and only when $n = 1,3$. From this, wee can conclude $|a_n| \ne 1$ except for $n = 1, 3$.

Method 2 - Modular arithmetic.

Since OP asks for an easier approach, here is an elementary one. The idea is extracted from a paper by B.Sury$\color{blue}{^{[2]}}$ on a related equation $x^2 + 2 = y^n \color{blue}{^{[3]}}$.

The OP has handled the case $a_n = -1$ already and it is simple to check $a_n \ne \pm 1$ for small $n$ other than $n = 1,3$. We will limit our proof to the case $n > 5$ and $a_n = 1$.

Let's say there is a $n > 5$ such that

$$a_n = \sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} (-2)^k \binom{n}{2k+1} = 1$$

Compare the parity of both sides, we get $1 = n \pmod 2$. This implies $n$ is an odd number.

Rewrite $n$ as $2^a b + 1$ where $a > 0$, $b$ odd. We will first look at everything modulo $2^{a+1}$.

Let $\nu_2 : \mathbb{Q} \to \mathbb{Z}$ be the 2-adic order of rational numbers. Notice for $k \ge 3$,
$$\nu_2(k) \le \lfloor\log_2 k \rfloor < k - 1 \quad\implies\quad \nu_2\left(\frac{2^k}{2k}\right) > 0$$ This leads to $$\nu_2\left((-2)^k \binom{n}{2k+1}\right) =\nu_2\left(\frac{(-2)^k n(n-1)}{(2k+1)(2k)}\binom{n-2}{2k-1}\right) > \nu_2(n-1) = a$$ whenever $k \ge 3$. As a result,

$$1 = a_n \equiv \sum_{k=0}^2 (-2)^k \binom{n}{2k+1} = n - 2\binom{n}{3} + 4\binom{n}{5} \pmod{2^{a+1}}\tag{*1}$$ It is not hard to see $$n \equiv 2^a + 1 \pmod {2^{a+1}}\quad\text{ and }\quad 2\binom{n}{3} = \frac{n(n-1)(n-2)}{3}\equiv 2^a \pmod {2^{a+1}}$$ For the third term, $$\begin{align} \nu_2\left(4\binom{n}{5}\right) &= \nu_2\left(\frac{n(n-1)(n-2)(n-3)(n-4)}{30}\right) = \nu_2\left(\frac{(n-1)(n-3)}{2}\right)\\ &= \nu_2\left(2^a b(2^{a-1}b - 1)\right) \quad\rightarrow\quad \begin{cases} = a,& a > 1\\ > a, &a = 1\end{cases} \end{align}\\ {\Large\Downarrow}\\ 4\binom{n}{5} \equiv \begin{cases} 2^a,& a > 1\\ 0,& a = 1\end{cases} \pmod {2^{a+1}} $$ Combine these three terms, $(*1)$ becomes

$$1 \equiv 1 + 2^a + 2^a + \begin{cases}2^a,& a > 1\\0, & a = 1\end{cases} \equiv \begin{cases} 1 + 2^a, & a > 1\\1, & a = 1\end{cases} \pmod {2^{a+1}} $$ This forces $a = 1$. As a result, $n$ has the form $2^c d + 3$ for some $c > 1$ and $d$ odd.

Next, let us look at everything modulo $2^{c+1}$. Once again, we can show that for $k \ge 3$, $$\nu_2(k(k-1)) < k - 1\quad\implies\quad \nu_2\left(\frac{2^k}{2k(k-1)}\right) > 0$$ For such $k$, we have $$\begin{align}\nu_2\left((-2)^k\binom{n}{2k+1}\right) &= \nu_2\left(\frac{(-2)^k n (n-1)(n-2)(n-3)}{(2k+1)(2k)(2k-1)(2k-2)}\binom{n-4}{2k-3}\right)\\ &= \nu_2\left(\left(\frac{2^k}{2k(k-1)}\right)\left(\frac{(2^c d + 2)(2^c d)}{2}\right) \binom{n-4}{2k-3}\right) > c \end{align} $$ As a consequence,

$$1 = a_n \equiv \sum_{k=0}^2 (-2)^k \binom{n}{2k+1} = n - 2\binom{n}{3} + 4\binom{n}{5} \pmod{2^{c+1}}\tag{*2}$$

With a little bit of algebra, one can check that

$$\begin{array}{rclcl} n &=& 2^c d + 3 &\equiv& 2^c + 3 & \pmod {2^{c+1}}\\ 2\binom{n}{3} &=& \frac13 (2^c d + 3)(2^c d + 2)(2^c d + 1) &\equiv& 2^c + 2 & \pmod {2^{c+1}}\\ 4\binom{n}{5} &=& \frac{1}{30}(2^c d + 3)(2^c d + 2)(2^c d + 1)(2^c d)(2^c d -1) &\equiv& 2^c & \pmod {2^{c+1}} \end{array}$$ This leads to a contradiction that $$1 \equiv (2^c + 3 ) - (2^c + 2) + 2^c \equiv 2^c + 1 \pmod {2^{c+1}}$$

As a result, there is no $n > 5$ such that $a_n = 1$.

Notes

• $\color{blue}{[1]}$ Y. Bilu, G. Hanrot, P.M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75-122. (a copy for an earlier version can be found here)

• $\color{blue}{[2]}$ B. Sury, On the Diophantine equation $x^2 + 2 = y^n$, Arch. Math. (Basel) 74 (2000), 350–355.

• $\color{blue}{[3]}$ Equation of the form $x^2 + C = y^n$ is a special case of something known as Lebesgue-Nagell equation. Notice $$a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} = \pm 1 \quad\implies\quad \begin{cases} \alpha^n &= x \pm \sqrt{-2}\\ \beta^n &= x \mp \sqrt{-2} \end{cases} \quad\text{ for some } x \in \mathbb{Z}\\ {\Large\Downarrow}\\ x^2 + 2 = (x \pm \sqrt{-2})(x \mp \sqrt{-2}) = \alpha^n\beta^n = 3^n$$ Every solution of $a_n = \pm 1$ corresponds to a solution for the equation $x^2 + 2 = y^n$.