\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Brazil 2021/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 142}
\maketitle

\section*{Problem}
Find all positive integers $k$ for which there is an irrational $\alpha > 1$
and a positive integer $N$ such that $\left\lfloor\alpha^n\right\rfloor + k$
is a perfect square for every integer $n > N$.

\section*{Video}
\href{https://www.youtube.com/watch?v=7wmIb_Byghc&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/7wmIb\_Byghc}}

\section*{External Link}
\url{https://aops.com/community/p24349942}

\newpage

\section*{Solution}
The answer is $k=3$ only.

\paragraph{Construction.}
Consider the integer sequence
\[ x_n \coloneqq \left( \frac{3 + \sqrt 5}{2} \right)^n
  + \left( \frac{3 - \sqrt 5}{2} \right)^n \]
defined by $x_0 = 2$, $x_1 = 3$, $x_2 = 7$, $x_{n+2} = 3x_{n+1} - x_n$, and so on.
Then we have
\[ x_n^2 \coloneqq \left( \frac{14 + 6\sqrt 5}{4} \right)^n
  + \left( \frac{14 - 6\sqrt 5}{4} \right)^n + 2. \]
so
\[ \left\lfloor \left( \frac{14+6\sqrt5}{4} \right)^n \right\rfloor = x_n^2 - 3 \]
holds for every $n$ (since $0 < \frac{14-6\sqrt5}{4} < 1$).
This provides $\alpha = \frac{14+6\sqrt5}{4}$ as an example.

\paragraph{Proof that $k=3$ is the only one possible.}
Throughout this solution, the big $O$ notation treats $\alpha$ and $k$ as $O(1)$.

For each $n > N$, we introduce the notation
\[ \alpha^n = x_n^2 - k + \eps_n \qquad x_n \in \NN, 0 < \eps_n < 1. \]
In particular, $x_n = \sqrt{\alpha^n + O(1)} = \alpha^{n/2} + O(\alpha^{-n/2})$.

We make the following assertion.
\begin{claim*}
  We have $1 - \eps_n = O(\alpha^{-n})$ and $x_n^2 = x_{2n} + (k-1)$.
\end{claim*}
\begin{proof}
  Note that
  \begin{align*}
    \alpha^{2n} &= x_{2n}^2 - k + \eps_{2n} \\
    \implies \left( \alpha^n - x_{2n} \right) \left( \alpha^n + x_{2n} \right) &= -k + \eps_{2n} \\
    \implies \left( x_n^2 - x_{2n} - k + \eps_n \right) (\alpha+x_{2n})
    &= \eps_{2n} - k
  \end{align*}
  Rearrange this to
  \[ x_n^2 - x_{2n} - k = -\eps_n - \frac{k-\eps_{2n}}{\alpha^n + x_{2n}}. \]
  The right-hand side is an integer strictly between $-2$ and $0$,
  so it's $-1$. So we get both the equality of the main terms
  \[ x_n^2 = x_{2n} + (k-1) \]
  and the estimate on the error term
  \[ 1 - \eps_n = \frac{k - \eps_{2n}}{\alpha^n+ x_{2n}}
    = \frac{O(1)}{2\alpha^n + O(\alpha^{-n})} = O(\alpha^{-n}). \qedhere \]
\end{proof}

In the main equation, replacing $x_n^2$ with $x_{2n} + (k-1)$ gives
\[ \alpha^n = x_{2n} - (1 - \eps_n) = x_{2n}
  - \frac{k-\eps_{2n}}{\alpha^n+x_{2n}}. \]
The fraction equals $\frac{k-1 + O(\alpha^{-n})}{2\alpha^n + O(\alpha^{-n})}$
and so we get
\[
  x_{2n} = \alpha^n + \frac{\frac{k-1}{2}}{\alpha^n} + O(\alpha^{-2n}).
\]
Multiplying both sides by $\alpha + \frac{1}{\alpha}$ gives
\begin{align*}
  \left( \alpha + \frac{1}{\alpha} \right) x_{2n}
  &= \alpha^{n+1} + \frac{\frac{k-1}{2}}{\alpha^{n+1}}
  + \alpha^{n-1} + \frac{\frac{k-1}{2}}{\alpha^{n-1}}
  + O(\alpha^{-2n}) \\
  &= x_{2n+2} + x_{2n-2} + O(\alpha^{-2n}).
\end{align*}
Hence
\[ \frac{x_{2n+2}+x_{2n-2}}{x_{2n}} = \alpha + \frac{1}{\alpha} + O(\alpha^{-3n}). \]
The critical claim is that the error term is actually zero exactly:
\begin{claim*}
  The equation
  \[ \frac{x_{2n+2}+x_{2n-2}}{x_{2n}} = \alpha + \frac{1}{\alpha} \]
  holds for large enough $n$.
\end{claim*}
\begin{proof}
  Notice that $\frac{x_{2n+2}+x_{2n-2}}{x_{2n}} - \frac{x_{2n}+x_{2n-4}}{x_{2n-2}}$
  is the difference of two terms which are $O(\alpha^{-3n})$.
  However, it's the difference of two rational numbers
  whose denominators are each $\Theta(\alpha^n)$, ergo their difference
  is at least $1/O(\alpha^{2n})$.
  This is too large, so the error terms between consecutive fractions must be constant.
  Since it also decays to zero, it must be eventually zero.
\end{proof}
From this, we have a bona fide linear recurrence with exact equalities
\[ x_{2n} = \lambda_+ \cdot \alpha^n + \lambda_- \cdot \alpha^{-n} \]
for some constants $\lambda_+$ and $\lambda_-$;
but actually $\lambda_+ = 1$ and $\lambda_- = \frac{k-1}{2}$
to match our earlier equation for $x_{2n}$; that is, we have exactly
\[ x_{2n} = \alpha^n + \frac{\frac{k-1}{2}}{\alpha^n}. \]
On the other hand, we are supposed to have $x_{2n}^2 = x_{4n} + (k-1)$
and comparing these two forces $\frac{k-1}{2} = 1$, so $k = 3$.

\end{document}
