8
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ For any non-degenerate binary linear recurrent sequence, you can solve this with Gelfond's or Baker's theorems on logarithmic linear forms. A good reference is the book 'Recurrence Sequences' by Everest, van der Poorten, Shparlinski and Ward. $\endgroup$ – Vesselin Dimitrov Jun 27 '17 at 12:00
10
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ @Friedrich: You are welcome! See also my "Added" section. $\endgroup$ – GH from MO Jun 27 '17 at 22:29
8
$\begingroup$

Besides the archimedean technique from Baker's theorem in another answer, this type of question can be handled both qualitatively and quantitatively using $p$-adic methods. This was illustrated, for the sequence you asked about, on https://math.stackexchange.com/questions/873147/finding-non-negative-integers-m-such-that-1-sqrt-2m-has-real-part/873529 with the task being a determination of when $a_n = \pm 1$. I wrote up an account of this in another $p$-adic field at http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/strassmannapplication.pdf.

$\endgroup$

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.