Let $a_1, a_2, \dots$ and $b_1, b_2, \dots$ be sequences of real numbers for which $a_1 > b_1$ and \begin{align*} a_{n+1} &= a_n^2 - 2b_n\\ b_{n+1} &= b_n^2 - 2a_n \end{align*}for all positive integers $n$. Prove that $a_1, a_2, \dots$ is eventually increasing (that is, there exists a positive integer $N$ for which $a_k < a_{k+1}$ for all $k > N$). Holden Mui
Problem
Source: USA TST 2025
Tags: algebra
john0512
15.12.2024 02:22
Let $P(x)=x^3-ax^2+bx-1$ with roots $p,q,r$.
Claim: We have $a_n=p^{2^{n-1}}+q^{2^{n-1}}+r^{2^{n-1}}$.
Note that
$$P(\sqrt{x})P(-\sqrt{x})=(x\sqrt{x}+b\sqrt{x})^2-(ax+1)^2$$$$=x^3-(a^2-2b)x^2+(b^2-2a)x-1.$$This transformation squares all of the roots, so the claim follows by induction.
Because $P(1)<0$, by IVT $P$ has a real root $r>1$. Then, if all roots of $P$ are real, we are clearly already done. Otherwise, the other two roots are complex conjugates that have magnitude less than $1$ (since the product of roots is $1$). In this case, $p^{2^{n-1}}+q^{2^{n-1}}+r^{2^{n-1}}$ will be eventually increasing anyways since one term has magnitude greater than $1$ and the other two become negligible.
Ziyadel
15.12.2024 02:30
When the TST December was ?
DottedCaculator
15.12.2024 03:19
Here is a solution for the case $a_1+b_1<-2$. Note that the conditions give $a_2,b_2>3$, and subtracting gives $a_i<b_i$ for $i\geq2$. Suppose $a_2=t^2+\frac2t$ for $0<t<1$. Then, we claim $b_2\leq2t+\frac1{t^2}$. We have $$a_1^2-2b_1=t^2+\frac2t,$$so $$b_1=\frac{a_1^2-t^2-\frac2t}2.$$Since $a_1+b_1<-2$, we get $a_1^2-t^2-\frac2t+2a_1<-4$, so $a_1$ is between $-1\pm\sqrt{t^2+\frac2t-3}$. We need to show $$2t+\frac1{t^2}\geq\left(\frac{a_1^2-t^2-\frac2t}2\right)^2-2a_1,$$or \begin{align*} a_1^4-2a_1^2\left(t^2+\frac2t\right)+t^4-4t-8a_1&\leq0\\ \left(a_1^2-2a_1t+t^2-\frac4t\right)\left(a_1^2+2a_1t+t^2\right)&\leq0\\ \left((a_1-t)^2-\frac4t\right)(a_1+t)^2&\leq0. \end{align*} This is true when $a_1$ is between $t\pm\frac2{\sqrt t}$, so it suffices to show $-1-\sqrt{t^2+\frac2t-3}>t-\frac2{\sqrt t}$ when $0<t<1$. Rearranging and squaring, this is equivalent to $$t^2+\frac2t-3<t^2+\frac4t+1-4\sqrt t-\frac4{\sqrt t}+2t$$or $$\frac{2(t+1)}{\sqrt t}<\frac{(t+1)^2}t,$$which is true. Now, if $a_2=t^2+\frac2t$ and $b_2\leq2t+\frac1{t^2}$, then $a_3\geq t^4+\frac2{t^2}$ and $b_3\leq2t^2+\frac1{t^4}$. Therefore, we can get that $a_n\geq t^{2^{n-1}}+\frac2{t^{2^{n-2}}}$, so $a_n$ is increasing.
The_Turtle
15.12.2024 03:37
My problem oops
Let $r$, $s$, and $t$ be the complex roots of the polynomial $p(\lambda)=\lambda^3 - a_1 \lambda^2 + b_1 \lambda - 1$. By Vieta's formulas,
\begin{align*}
a_1 &= r+s+t \\
b_1 &= 1/r + 1/s + 1/t \\
1 &= rst.
\end{align*}
Claim. For every positive integer $n$,
\[a_n = r^{2^{n-1}} + s^{2^{n-1}} + t^{2^{n-1}}\]and
\[b_n = (1/r)^{2^{n-1}} + (1/s)^{2^{n-1}} + (1/t)^{2^{n-1}}.\]
Proof. The base case follows from Vieta's formulas above. For the inductive step, observe that $rst=1$, so
\begin{align*}
a_{n+1} &= a_n^2 - 2b_n \\
&= \left(r^{2^{n-1}} + s^{2^{n-1}} + t^{2^{n-1}}\right)^2 - 2\left((1/r)^{2^{n-1}} + (1/s)^{2^{n-1}} + (1/t)^{2^{n-1}}\right) \\
&= \left(r^{2^{n-1}} + s^{2^{n-1}} + t^{2^{n-1}}\right)^2 - 2\left((st)^{2^{n-1}} + (tr)^{2^{n-1}} + (rs)^{2^{n-1}}\right) \\
&= r^{2^{n}} + s^{2^{n}} + t^{2^{n}}
\end{align*}and similarly for $b_{n+1}$. $\blacksquare$
Since $p(1) = b_1 - a_1 < 0$, $p$ has a real root greater than 1; let $r$ be the largest such root.
If all roots are real, then \[a_n = r^{2^{n-1}}+s^{2^{n-1}}+t^{2^{n-1}} = \Theta\left( \max(\lvert r\rvert, \lvert s\rvert, \lvert t\rvert)^{2^{n-1}}\right)\]is eventually increasing.
If $r$ is real and $s, t$ are not real, they must be complex conjugates of each other, each with magnitude $\frac{1}{\sqrt{r}} < 1$. Therefore
\[r^{2^{n-1}} - 2 < a_n < r^{2^{n-1}}+2,\]so $a_n$ is eventually increasing.
asbodke
15.12.2024 05:18
Here's a solution for the case $a_1+b_1\ge -2$. Let $d_n=a_n-b_n$ and $s_n=a_n+b_n+2$. We have $d_1,\,s_1>0$ and the equations \begin{align*} d_{n+1} &= d_ns_n\\ s_{n+1} &= \frac 12[(s_n-4)^2+d_n^2]. \end{align*}Now, note that if $s_k>8$ for any $k$, we have $s_{i+1}>s_i$ and $d_{i+1}>d_i$ for $i\ge k$. So $2a_i=s_i+d_i-2$ is increasing. We will show that as long as $s_i$ is stuck between $0$ and $8$, $d_i$ grows arbitrarily large. This is sufficient to prove that there exists $k$ with $s_k>8$. There are indices $c_1,c_2,\dots$ when $s_{c_i}<3/2$. If this list is finite, we're done as $d_i$ multiplies by at least $3/2$ each iteration. Otherwise, we'll show that there exists $C>1$ such that $d_{c_{i+1}-1}>Cd_{c_i-1}$ for all $i$, or \[\prod_{j=c_i}^{c_{i+1}-1}s_j>C.\] Let $s_{c_i}=\varepsilon$. We have \begin{align*} s_{c_i+1}&\ge \frac 12(4-\varepsilon)^2\ge 8-4\varepsilon\\ s_{c_i+2}&\ge \frac 12(4-4\varepsilon)^2\ge 8-16\varepsilon\\ &\vdots\\ s_{c_i+j}&\ge8-4^j\varepsilon\\ &\vdots \end{align*}as long as $s_{c_i+j}>4$. Thus, we must have $4^j\varepsilon<4\implies j<1-\log_4(\varepsilon)$. In particular, \[P=\prod_{j=c_i+1}^{c_{i+1}-1}s_j>(8-4\epsilon)\cdots(8-4^{c_{i+1}-c_i-1}\varepsilon)> 4^{-\log_4(\varepsilon)}=\frac 1\varepsilon.\]However, if $\varepsilon>1/3$ then $\varepsilon P>4(1/3)=4/3$, and if $\varepsilon<1/3$ then $8-4\varepsilon>6$ so $\varepsilon P>\varepsilon(3/2\varepsilon)=3/2$. Thus, $d_{c_{i+1}-1}>4/3d_{c_i-1}$ and we're done!
peace09
15.12.2024 05:30
Let $(a_0,b_0):=(x+y+z,\tfrac{1}{x}+\tfrac{1}{y}+\tfrac{1}{z})$ where $xyz=1$; inductively \begin{align*} a_n&=x^{2^n}+y^{2^n}+z^{2^n}\\ b_n&=x^{-2^n}+y^{-2^n}+z^{-2^n}. \end{align*}Observe $\max(|x|,|y|,|z|)>1$, as $a_0>b_0$ prevents equality; and so if $x,y,z\in\mathbb{R}$ we are clearly done. Otherwise, as $a_0,b_0$ are real, we may substitute $(x,y,z):=(re^{\theta i},re^{-\theta i},\tfrac{1}{r^2})$ where $r>0$ to find \[a_n=2r^{2^n}\cos(2^n\theta)+r^{-2^{n+1}}.\]If $r<1$ we are again done; if $r>1$, here $a_0>b_0$ translates as $\cos\theta>\tfrac{1}{2}(r+\tfrac{1}{r})$, bad. $\square$
navid
27.12.2024 01:34
Well, many years ago-- indeed, 2006-- the following problem proposed in the Belarussian math olympiad. Let $(a_n), (b_n)$ be two sequences of real numbers such that $4a_1-2b_1=7$ and $(a_{n+1}, b_{n+1})=( a_n^2-2b_n, b_n^2-2a_n)$. Evaluate $2^{512}a_{10}-b_{10}$. In the following link, and in the page 44 of the PDF file, Michel Bataille, provided a solution that was really pointed the substantial part of the some of the above solutions. https://cms.math.ca/wp-content/uploads/crux-pdfs/CRUXv36n4.pdf