Determine whether there exist two reals $x,y$ and a sequence $\{a_n\}_{n=0}^{\infty}$ of nonzero reals such that $a_{n+2}=xa_{n+1}+ya_n$ for all $n\ge0$ and for every positive real number $r$, there exist positive integers $i,j$ such that $|a_i|<r<|a_j|$. Alex Zhu.
Problem
Source: ELMO Shortlist 2011, A7; also ELMO #3
Tags: quadratics, search, trigonometry, algebra proposed, algebra
11.07.2012 12:56
Characterisic equation of this sequence is $z^2 - xz-y=0$, and if $z_1, z_2$ are two roots of it (suppose different) then $a_n= c_1 z_1^n + c_2 z_2^n$, where $c_1,c_2$ are some constants. Complying the problem's requirement means: 1) there are $a_i$ as close to $0$ as we want. 2) there are $a_i$ with $|a_i|$ as big as we want. If $z_1$ and $z_2$ are reals it is impossible 1) and 2) to hold in the same time. Nevertheless in the general case it is possible to find an example of such sequence. An example: Search for such sequence in the form $a_n = z_1^n + \bar{z_1}^n = 2 Re \, z_1^n$, where $z_1$ is a complex number $z_1= 2(\cos \varphi + i \sin \varphi)$. Then $a_n = 2^{n+1} \cos n\varphi$. The point is to choose $\varphi$ in such a way that for some sequence of $n$, $\cos n\varphi$ is very small and can compensate for big $2^n$. Define sequence $b_n,\, b_1=3, b_{n+1} = b_n^{(b_n+2)}.3^{n+4}$. Choose now $\varphi = \frac{\pi}{2} + \frac{2\pi}{b_1} +\ldots + \frac{2\pi}{b_n} +\ldots $. Then $b_n\varphi = b_n\frac{\pi}{2} + 2k\pi + \frac{2\pi}{b_n^{b_n+1}.3^{n+4}} + \ldots \, \Rightarrow $ ${ |(2\ell+1)\frac{\pi}{2}-b_n \varphi}| < \frac{1}{b_n^{b_n+1}}(\frac{1}{3^2}+\frac{1}{3^3}+\ldots) < \frac{1}{3.2^{b_n} b_n} \, \Rightarrow$ (3) $|a_{b_n}|= |2.2^{b_n} \cos b_n \varphi| = 2.2^{b_n}|\sin((2\ell+1)\frac{\pi}{2}-b_n \varphi)| <$ $< 2.2^{b_n}|(2\ell+1)\frac{\pi}{2}-b_n \varphi| < \frac{1}{b_n}$. (3) means that there are $a_i$ as close to $0$ as we want. The existance of sufficiently big $|a_i|$ is clear, so the problem's requirement holds.
12.01.2019 05:43
The answer is $\boxed{\text{yes}}$. Here is a construction: Let $\lambda=1.5e^{\pi i \alpha}$ where \[\alpha:=\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^{2^2}}+\frac{1}{2^{2^{2^2}}}+\cdots.\]We see that $\alpha$ is irrational since if it was rational, its binary expansion would be periodic, which is clearly not true. Now, let $x=\lambda+\bar{\lambda}$ and $y=-\lambda\bar{\lambda}$, which are real numbers. Also, let $a_n=\Im(\lambda^n)$. First, lets verify the recurrence. Note that \[\lambda^n=(\lambda+\bar{\lambda})\lambda^{n-1}+(-\lambda\bar{\lambda})\lambda^{n-2}=x\lambda^{n-1}+y\lambda^{n-2},\]so taking the imaginary part of both sides yields the desired result (this works because $x,y\in\mathbb{R}$). Note since $\alpha$ is irrational, $a_n$ is never $0$. We will first show the existence of $i$ such that $|a_i|<r$. This is equivalent to showing that $|a_i|$ can grow arbitrarily small. Let $f(n)=2^{f(n-1)}$ where $f(1)=2$, so we have $\alpha=f(1)^{-1}+f(2)^{-1}+\cdots$. Note that \[\chi(n):=f(n)^{-1}+f(n+1)^{-1}+\cdots\le \frac{1}{f(n)}+\frac{1}{2f(n)}+\frac{1}{4f(n)}+\cdots=\frac{2}{f(n)},\]so by combining the first $n$ terms of $\alpha$, we see that there is a positive integer $g(n)$ such that \[\alpha=\frac{g(n)}{f(n)}+\chi(n+1).\]Thus, \[a_{f(n)}=\Im(1.5^{f(n)} e^{\pi i (g(n)+\chi(n+1)f(n))})=\pm 1.5^{f(n)}\sin(\pi\chi(n+1)f(n)).\]Note that\[\theta(n):=\pi\chi(n+1)f(n)\le 2\pi\frac{f(n)}{f(n+1)}=2\pi\frac{f(n)}{2^{f(n)}}.\]For large enough $n$, $\theta(n)$ grows very small, so $\sin(\theta(n))\le\theta(n)$ by the Taylor expansion for $\sin$. Therefore, \[0<|a_{f(n)}|\le 1.5^{f(n)}\cdot\left(2\pi\frac{f(n)}{2^{f(n)}}\right).\]The right hand side becomes arbitrarily small as $f(n)$ grows larger (as $n$ grows larger), so this part of the bound is shown. Now, we'll show the existence of $j$ such that $|a_j|>r$, so we want to show that $|a_j|$ can grow arbitrarily large as well. Since $\alpha$ is irrational, $\{\{j\alpha:j\in\mathbb{N}\}\}$ is dense in $[0,1)$, so in particular, there are infinitely many $j$ with $\frac{1}{6}\le\{j\alpha\}\le\frac{5}{6}$. If we choose such $j$, then \[|a_j|=|\Im(1.5^j e^{\pi i j\alpha})|=|1.5^j\sin(\pi\alpha)|\ge\frac{1}{2}1.5^j\sin(\pi\alpha).\]The right side grows arbitrarily large, so we are done.
07.04.2020 09:25
The answer is yes. Define \[t_n:=\underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}}_{n\text{ twos}}\quad\text{and}\quad\nu:=\frac1{t_1}+\frac1{t_2}+\frac1{t_3}+\cdots,\]which is irrational since its binary representation is not periodic. Select a real number $r\in(1,16)$, and let $z:=re^{2\pi i\cdot\nu}$. I claim the sequence $a_n:=z^n+z^{-n}$ works. It is easy to check $(a_n)_{n\ge0}$ satisfies a linear recurrence and is always real. Furthermore $a_n=\operatorname{Re}(z^n)$, which is clearly unbounded. It suffices to show $|a_n|$ can be arbitrarily small. Consider $n=t_k/4$ for sufficiently large $k$. We have \begin{align*} |a_n|&=\left\lvert r^{t_k/4}\operatorname{Re}\exp\left(2\pi i\sum_{j\ge1}\frac{t_k}{4t_j}\right)\right\rvert\\ &=\left\lvert r^{t_k/4}\cos\left(2\pi\left(\frac14+\frac{t_k}{4t_{k+1}}+\cdots\right)\right)\right\rvert\\ &=\left\lvert r^{t_k/4}\cos\left(\frac{\pi}2+\frac\pi2\cdot\frac{t_k}{t_{k+1}}+\cdots\right)\right\rvert\\ &<\left\lvert r^{t_k/4}\cos\left(\frac{\pi}2+\frac\pi2\cdot\frac{t_k}{t_{k+1}}\right)\right\rvert\\ &=r^{t_k/4}\sin\left(\frac\pi2\cdot\frac{t_k}{2^{t_k}}\right)\\ &<r^{t_k/4}\left(\frac\pi2\cdot\frac{t_k}{2^{t_k}}\right). \end{align*}which can be arbitrarily small.
12.05.2022 20:34
The answer is yes. Let's have $a_n=2c^n \cos(n\pi \alpha)=z^n+\overline{z}^n$ where $z=ce^{i\pi \alpha}$ and $c=1.01$. We want to have $ \cos(n\pi \alpha)$ extremely small. Observe $\cos(n\pi \alpha)=\sin (\frac{\pi}{2}+n\pi\alpha) < \pi \{|\frac 12 - n\alpha|\}$. Therefore, we make $\alpha>\frac 12$, $n$ odd, and we have $|a_n|\le 2\pi c^n \{n\alpha-\frac 12\} = 2\pi c^n \{n\beta\}$ where $\beta=\alpha-\frac 12$. Let $b_n=2\pi c^n \{n\beta\}$ We basically need to construct an infinite chain $n_1,n_2,\cdots$ such that $b_{n_j}$ become arbitrarily small. To do this, one way is to note if $\{n\beta\}=\epsilon$, we can have $\{mn\beta\}=m\{n\beta\}-1=\epsilon'<<\epsilon$. Using this idea, we are motivated to construct the following (any construction with $\beta=\sum x_j^{-1}$ where $x_j>t^{x_{j-1}}$ and $x_{j-1}|x_j$ should be able to take out the "leading terms", but here is a construction for concreteness) Let $x_1=3, x_j=3^{x_{j-1}}$ and $\beta=\sum\limits_{j\ge 1} x_j^{-1}$. Then notice $a_{x_j} \le b_{x_j} = 2\pi (1.01)^{x_j} \sum\limits_{k\ge j+1} x_k^{-1} < 4\pi (1.01)^{x_j}x_j 3^{-x_j} = 4\pi (\frac{1.01}{3})^{-x_j} x_j$, which grows arbitrarily small. Finally $a_n$ can obviously grow large, the end.
04.03.2024 20:38
Note that the recurrence $a_{n+2} = xa_{n+1} + ya_n$ can be written as $a_n = c_1z_1^n + c_2z_2^n$. Notice that if $z_1$ and $z_2$ are reals then clearly the second condition will not be achievable(we won't be able to reach arbitrarily small numbers). So then $z_1$ and $z_2$ must be complex conjugates and $c_1 = c_2 = c = 1.0434$. Let $b_n = b_{n-1} + \frac{1}{{^{n}1434}}$ and $b_1 = \frac{1}{1434}$ and $z_1 = c \cdot e^{2\pi i \cdot b_{\infty}}$, $z_2 = c \cdot e^{-2\pi i \cdot b_{\infty}}$. Then $a_n = |2c^n \cdot \cos(2\pi(n\cdot b_\infty))|$. Letting $n = \frac{^{m}1434}{4}$ for arbitrarily large $m$ implies \[a_n = |2c^n \cdot \cos(\frac{\pi}{2}(1 + \sum_{m}^{\infty} \frac{^{m}1434}{^{k+1}1434})| <\]\[|2c^n \cdot \cos(\frac{\pi}{2}(1 + \frac{^{m}1434}{^{m+1}1434}))| = \]\[|2c^n \cdot \sin(\frac{\pi}{2}(\frac{^{m}1434}{^{m+1}1434}))|\]and since $\theta > \sin(\theta)$ for small enough values of $\theta$ we have \[|2c^n \cdot \sin(\frac{\pi}{2}(\frac{^{m}1434}{^{m+1}1434}))| < \]\[|2c^n \cdot (\frac{\pi}{2}(\frac{^{m}1434}{^{m+1}1434}))|\]Note that this expression can get arbitrarily small and arbitrarily large so we are done.
19.03.2024 20:48
Why being constructive when u can be nonconstructive or something. We define $a_n = (2^n) (e^{n\lambda} + e^{-n\lambda})$ for some $\lambda$ to be chosen. Define $n_1 = 10^{1434}, n_2 = 10^{n_1}, \dots$. For each $n_i$, we take $\lambda_i$ such that \[ n_i\lambda_i \in \left[\cos^{-1}(1434^{(-1)^{n_i}}), \frac{\pi}{2}\right] \pmod{2\pi}. \]and all earlier conditions hold as follows. Add a very small rational of the form $\frac{n}{2^{k_i}}$ to $\lambda_{i-1}$ where $k_i$ is superlinear. $\lambda$ then exists by convergence and is irrational by being aperiodic. It then follows that $a_{n_i}$ gets arbitrary close to both $0$ and unbounded by virtue of not being periodic $\pmod{2pi}$.