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

\begin{document}
\title{ELMO 2010/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 59}
\maketitle

\section*{Problem}
Let $r$ and $s$ be positive integers.
Define $a_0 = 0$, $a_1 = 1$, and $a_n = ra_{n-1} + sa_{n-2}$ for $n \geq 2$.
Let $f_n = a_1a_2\dots a_n$.
Prove that $\frac{f_n}{f_kf_{n-k}}$ is an integer
for all integers $n$ and $k$ such that $0 < k < n$.

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

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

\newpage

\section*{Solution}
It's equivalent to show that for integers $k$, $m$ we have
\[ a_1 \dots a_{k} \mid a_m \dots a_{m+k-1}. \qquad(\spadesuit) \]

From the theory of linear  recurrences,
we know there are algebraic integers $\alpha$ and $\beta$
such that $a_n$ has a closed form
\[ a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}. \]
(Namely, $\alpha$ and $\beta$ are the roots
of the polynomial $T^2 - rT - s = 0$.
Note that since $s > 0$ it follows $\alpha \neq \beta$.)

Then, $(\spadesuit)$ rewrites as
\[
  \frac{(\alpha^m-\beta^m)(\alpha^{m+1}-\beta^{m+1})\dots(\alpha^{m+k-1}-\beta^{m+k-1})}%
  {(\alpha-\beta)(\alpha^2-\beta^2) \dots (\alpha^k-\beta^k)}.
\]

\begin{claim*}
  We get a divisibility as polynomials in $\alpha$ and $\beta$.
\end{claim*}
\begin{proof}
  Since this is homogeneous, it suffices to show for $\beta = 1$,
  $\alpha = X$:
  \[
    \frac{(X^m-1^m)(X^{m+1}-1^{m+1})\dots(X^{m+k-1}-1^{m+k-1})}%
    {(X-1)(X^2-1^2) \dots (X^k-1^k)}
    \]
  If $\zeta$ is a primitive $r$th root of unity,
  it appears at least as many times on top as on bottom.
\end{proof}

Hence, the number in $(\spadesuit)$ is a rational algebraic integer,
so it is an integer.

\end{document}
