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
$\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$
  • $\begingroup$ I wonder if this applies more generally to a much wider class of recursive sequences of similar form...? $\endgroup$ – user357980 Jun 19 '17 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 '17 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$
  • 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 '17 at 21:34

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.