3
$\begingroup$

I have a question about the sequence $a_0=a_1=1$, and for all $n\geq 2$ : $a_{n}=2a_{n-1}-3a_{n-2}$. (https://oeis.org/A087455)

How to prove that $|a_n|\to+\infty $ ?

I know that there are other formulas, like $$a_n=\frac{(1+i\sqrt{2})^n+(1-i\sqrt{2})^n}{2}$$ or $$a_n= (\sqrt{3})^n\cdot \cos\left(n\cdot \tan^{-1}(\sqrt2)\right)$$

Here are the first terms of the sequence :

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

$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

I think that I have a solution, but not elementary. I put $A=1+i\sqrt{2}$, $b=1-i\sqrt{2}$. Note that $a_n\in \mathbb{Z}$ for all $n$. Now suppose that $|a_n|$ does not go to $\infty$. There exists then $M>0$ such that the set $\{n; |a_n|\leq M\}$ is infinite, and as a consequence, there exist $L\in \mathbb{Z}$ such that $a_n=L$ for an infinity of $n$. This means that the recurrent sequence $a_n-L$ take the value $0$ for an infinity of $n$.

Now the non elementary fact: The Skolem-Mahler-Lerch Theorem: see https://en.wikipedia.org/wiki/Skolem%E2%80%93Mahler%E2%80%93Lech_theorem

This theorem say that there exist an arithmetic progression of such $n$: there exist $d\geq 1$, and $r$, such that $a_{kd+r}-L=0$, or $A^{kd+r}+B^{kd+r}-2L=0$ for all $k$. Now take $k=0,1,2$. The linear system with $3$ unknown $x_1,x_2,x_3$ given by $A^{kd}x_1+B^{kd}x_2+x_3=0$, $k=0,1,2$ admit then a non zero solution $(A^{r},B^{r}, -2L)$. Hence the determinant of this system (this is a Van der Monde determinant) is zero. As $d\geq 1$, $A^d\not =1$, and $B^d\not =1$, this gives that we must have
$A^d=B^d$. And to finish, Let $R=\mathbb{Z}[i\sqrt{2}]$. This is an Euclidean ring for the norm, and in $R$, $A$ and $B$ are two non associated primes. And we have unicity of the decomposition in prime, hence $A^d=B^d$ is the final contradiction.

$\endgroup$
2
  • $\begingroup$ I wonder if this applies more generally to a much wider class of recursive sequences of similar form...? $\endgroup$
    – user357980
    Jun 19, 2017 at 22:03
  • $\begingroup$ @user357980 You are correct. If you have a linear recurrent sequence $u_n$ with $u_n\in \mathbb{Z}$ for all $n$, (so the first part of the proof works) and if $P(x)$ is the characteristic polynomial of the recurrence, then $u_n-L$ has characteristic polynomial $Q(x)=(x-1)P(x)$ (say for simplicity with simple roots), and if no quotient of distinct roots of $Q$ is a root of unity, then $|u_n|\to +\infty$. The proof is almost the same. $\endgroup$
    – Kelenner
    Jun 20, 2017 at 6:15
0
$\begingroup$

This only gives unboundedness. It may be possible to show it along these methods with different tricks.

If we calculate the generating function: $$f(x) = \sum_{n=0}^{\infty}a_nx^n,$$ we get: $$f(x) = \sum_{n=0}^{\infty}a_nx^n = 1 + x + 2\sum_{n=2}^{\infty}a_{n-1}x^n - 3\sum_{n=2}^{\infty}a_{n-2}x^n = 1 + x + 2x\sum_{n=1}^{\infty}a_{n}x^{n} - 3x^2\sum_{n=0}^{\infty}a_{n}x^{n} = 1 + x + 2x(f(x) - 1) - 3x^2f(x),$$ so solving we get: $$f(x) = \frac{1-x}{-3x^2 + 2x - 1} = \frac{3(x-1)}{(-3ix + \sqrt{2} + i)(-3ix + \sqrt{2} - i)}, $$Ref where we recover $a_n$ with repeated differentiation: $$a_n = \frac{f^{(n)}(0)}{n!}.$$

So, we see that $f$ is analytic at $0$ with radius of convergence $1/\sqrt{3}$ since that is the magnitude of the roots of the denominator of the closed form of $f$. This means that by the root test: $$\limsup_{n \to \infty}\sqrt[n]{|a_n|} = \sqrt{3},$$ so this means that there is a subsequence $a_{n_k}$ such that $\sqrt[n]{|a_{n_k}|} = \sqrt{3} + \epsilon_k$, where $\epsilon_k$ (the error) is is not-necessarily positive but is converging to zero. So, $$|a_{n_k}| = (\sqrt{3} + \epsilon_k)^{n_k},$$ which implies converging to infinity on that subsequence.

$\endgroup$
0
$\begingroup$

The characteristic equation is $$x^2-2x+3=0$$ the roots are

$x_1=1-i\sqrt {2} $ and $x_2=1+i\sqrt {2} $. or $\sqrt {3}e^{\pm i \theta} $ with $$\cos (\theta)=\frac{1} {\sqrt {3}}$$ and $$\sin (\theta)=\frac {\sqrt {2}}{\sqrt {3}} $$.

finally $$a_n=(\sqrt {3})^n\Bigl (A\cos (n\theta)+B\sin (n\theta)\Bigr) $$

with $$a_0=A=1$$ and $$a_1=1 \implies B=0$$ and $$a_n=(\sqrt {3})^n\cos (n\theta) .$$

$\endgroup$
1
  • 4
    $\begingroup$ The OP has such a formula. The problem is that $|\cos(n\theta)|$ can be very small, so the fact that $(\sqrt{3})^n\to +\infty$ is not sufficient to conclude. $\endgroup$
    – Kelenner
    Jun 19, 2017 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .