Consider the sequence defined by $a\_0=a\_1=1$ and $a\_n=2a\_{n-1}-3a\_{n-2}$ for $n\geq 2$. This is the sequence <https://oeis.org/A087455>.


I would like to prove that $|a\_n|>100$ when $n>10$. How can we do it? (Also, is there an explicit non-trivial lower bound for the sequence $|a\_n|$?)


The first few terms:


1, 1, -1, -5, -7, 1, 23, 43, 17, -95, -241, -197, 329, 1249, 1511, -725, -5983, -9791, -1633, 26107, 57113, 35905, -99529, -306773, -314959, 290401, 1525679, 2180155, -216727, -6973919, -13297657, -5673557, 28545857, 74112385, 62587199, -97162757, -382087111, -472685951, 200889431, 1819836715, 3037005137, 614500129, -7882015153, -17607530693, -11569015927, 29684560225, 94076168231, 99098655787, -84031193119, -465358353599, -678623127841, 38828805115, 2113526993753, 4110567572161, 1880554163063, -8570594390357, -22782851269903, -19853919368735, 28640715072239, 116843188250683, 147764231284649, -55001102182751, -553294898219449, -941586489890645, -223288285122943, 2378182899426049, 5426230654220927, 3717912610163707, -8842866742335367, -28839471315161855, -31150342403317609, 24217729138850347


Explicit formulas:


$$\begin{align\*}a\_n&=\frac{(1+i\sqrt2)^n+(1-i\sqrt2)^n}{2}\\&=(\sqrt{3})^n\cdot \cos (n\cdot \theta)\end{align\*}$$


where $\theta=\tan^{−1}(\sqrt2)$.


Thank you.



Growth of a linear recurrent sequence
First note that $\frac{1+i\sqrt{2}}{1-i\sqrt{2}}\in\mathbb{Q}(\sqrt{-2})$ is not a root of unity, because it does not equal $\pm 1$. Therefore Baker's famous theorem shows that, for some effectively computable constant $c>0$,
$$\left|\left(\frac{1+i\sqrt{2}}{1-i\sqrt{2}}\right)^m-1\right|>m^{-c},\qquad m\geq 2.\tag{$\*$}$$
(The variables $m$ and $n$ are integers in this post.)
Applying this for $m=2n$, we get
$$\left|\left(\frac{1+i\sqrt{2}}{1-i\sqrt{2}}\right)^n-1\right|\cdot\left|\left(\frac{1+i\sqrt{2}}{1-i\sqrt{2}}\right)^n+1\right|>(2n)^{-c},\qquad n\geq 1.$$
The first factor is less than $2$, hence multiplying both sides by the absolute value of $(1-i\sqrt{2})^n$, we infer
$$\Bigl|(1+i\sqrt{2})^n+(1-i\sqrt{2})^n\Bigr|>\frac{1}{2}\cdot\frac{3^{n/2}}{(2n)^c},\qquad n\geq 1.$$
This means that the sequence $(a\_n)$ grows exponentially:
$$ |a\_n|>\frac{1}{4}\cdot\frac{3^{n/2}}{(2n)^c},\qquad n\geq 1.$$
In particular, there are only finitely many $n$'s with $|a\_n|\leq 100$, and these can be effectively bounded. Then, up to that bound, one can check with a computer (at least in theory) which $n$'s satisfy $|a\_n|\leq 100$.


**Added.** In ($\*$), the exponent $c=5\times 10^9$ is admissible by Corollary 2.3 in Matveev: An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II (Izv. Math. 64 (2000), 1217-1269). This means that $|a\_n|\leq 100$ implies $n<3\times 10^{11}$.


