# An exotic sequence

Let $a=\frac{1+i\sqrt 7}{2}$ and $u_n=\Re(a^n)$
show that $(|u_n|)\to +\infty$

I think basics method does not works here.

Any ideas ?

This isn’t really a calculus problem because it amounts to a subtle
question about how close a multiple of $\tan^{-1} \sqrt 7$ can get
to an odd multiple of $\pi/2$. Robert Israel already explained
why one expects that $|u_n|$ should grow faster than $n^{-\mu} 2^{n/2}$
for some constant $\mu$, which is much more than enough to prove
the desired $|u_n| \rightarrow \infty$; and achille lui applied the
“heavy sledgehammer” of Baker and Wüstholz to prove this for some
explicit $\mu$. Here we give a much simpler approach that yields
a result that, though much weaker than the sledgehammer,
is still sufficient to prove that $|u_n| \rightarrow \infty$.

It was already noted that $u_n = (a^n + b^n) / 2$ where
$b = 1-a$ is the complex conjugate of $a$, and thus that
the $u_n$ are half-integers satisfying the recurrence
$u_{n+2} = u_{n+1} – 2 u_n$. (The odd integers $2u_n$
are OEIS sequence A002249.)
Thus $|u_n| \rightarrow \infty$ if and only if for every integer $m$
there are only finitely many solutions $n$ of $2u_n = m$.
We shall show that every $m$ occurs at most once except for
$1 = u_1 = u_4$ and $-5 = u_3 = u_9$.

The technique is basically what’s known as “Skolem’s $p$-adic method”,
which immediately gives a uniform upper bound on the number of
solutions of $2u_n = m$; after some experimentation I was able to
reduce this bound to $1$ (with the exception of the two solutions
for each of $m=1$ and $m=-5$).

We start with some elementary observations. First, $2u_n \bmod 7$
has period $3$ with remainders $1,4,2,1,4,2,\ldots$, so if
$u_n = u_{n’}$ then $n’ \equiv n \bmod 3$. (This happened for
$\{n,n’\} = \{1,4\}$ and $\{3,9\}$.) Likewise, $2u_n \bmod 16$
becomes periodic of period $4$ after the first three terms:
$1, -3, -5$, and then then $1, -5, -7, 3, 1, -5, -7, 3,\ldots$.
Thus $2u_2=-3$ never recurs, and if $u_n=u_{n’}$ with neither $n$ or $n’$
equal $1$ or $3$ then $n’ \equiv n \bmod 4$, whence
$n’ \equiv n \bmod 12$ because we already knew the congruence mod $3$.

Assume henceforth that $n,n’ \geq 4$, so $n’ \equiv n \bmod 12$.
Then we claim $n’ \equiv n \bmod 84$. Indeed for each of the primes
$p=29$ and $p=43$ we have $2u_{n+84} \equiv 2u_n \bmod p$ for all $n$,
because in each case $-7$ is a square mod $p$ (so $a,b \bmod p$
can be identified with elements of $({\bf Z}/p{\bf Z})^*$)
and $p-1$ is a factor of $84$. So it is enough to check that
none of the $12$ subsequences
$$\{ 2u_n,\, 2u_{n+12},\, 2u_{n+24},\, 2u_{n+36},\, 2u_{n+48},\, 2u_{n+60},\, 2u_{n+72} \} \bmod 29 \cdot 43$$
with $1 \leq n \leq 12$
contains a repeat, and this turns out to be the case.
(The odds were in our favor: for $12$ random septuplets mod $29 \cdot 43$
the probability of success is over $90\%$, and by using $n \bmod 12$
we removed the known coincidences $u_1=u_4$ and $u_3=u_9$.)

Now for $p=29$ or $p=43$ each of $a^{84} \bmod p$ and $b^{84} \bmod p$
can be written as $1+pc$, $1+pd$ for some algebraic integers $c,d$.
It follows by induction on $k$ that $a^{84p^k}$ and $b^{84p^k}$
are congruent to $1 + p^{k+1} c$ and $1 + p^{k+1} d \bmod p^{k+2}$.
We thus find, for each $n_0 = 1, 2, \ldots, 84$, some $e_{n_0} \bmod p$
such that $$2u_{n_0+84p^k t} \equiv 2u_{n_0} + p^{k+1} e_{n_0} t \bmod p^{k+2}$$
for all integers $t$. So if $e_{n_0}$ is not zero mod $p$ then there are
no repeats in the sequence $\{u_n \mid n \equiv n_0 \bmod 84\}$:
if $n \neq n’$ then $n-n’$ has some finite $p$-valuation $k$,
and $2u_n$ is congruent to $2u_{n’} \bmod p^{k+1}$ but not mod $p^{k+2}$.
If some $e_{n_0}$ does vanish mod $p$ then we can try congruences mod
$p^{k+3}$, $p^{k+4}$, etc. But it turns out that this is not necessary:
we have two choices of $p$, and while there are some $n_0 \leq 84$
for which $e_{n_0} \equiv 0 \bmod p$ for one of $p=29$ and $p=43$,
there is none for which both $e_{n_0} \bmod p$ vanish.
(Again the odds were in our favor: a random $84$-tuple mod $29\cdot 43$
has no zero entries with probability $>93\%$.)

This completes the proof that the sequence $\{u_n \mid n \geq 4\}$
has no repeats, and thus establishes our claim that
$|u_n| \rightarrow \infty$ as $n \rightarrow \infty$, QED.