Let $a_0$ be a fixed positive integer. We define an infinite sequence of positive integers $\{a_n\}_{n\ge 1}$ in an inductive way as follows: if we are given the terms $a_0,a_1,...a_{n-1}$ , then $a_n$ is the smallest positive integer such that $\sqrt[n]{a_0\cdot a_1\cdot ...\cdot a_n}$ is a positive integer. Show that the sequence $\{a_n\}_{n\ge 1}$ is eventually constant. Note: The sequence $\{a_n\}_{n\ge 1}$ is eventually constant if there exists a positive integer $k$ such that $a_n=c$, for every $n\ge k$.
Problem
Source: Kosovo MO 2020 Grade 12, Problem 4
Tags: national olympiad, Olympiad, Kosovo, algebra, number theory, Sequence
kaede
02.02.2020 21:36
If $a_{0}=1$, then $a_{n}=1$ for all $\in \mathbb{N}$.
So suppose that $a_{0}>1$
Let $p$ be an arbitrary prime divisor of $a_{0}$.
From the definition of the sequence, $n\mid \nu _{p}( a_{0} a_{1} ,..,a_{n})$ for all $n\in \mathbb{N}$.
Let $e_{n} =\nu _{p}( a_{n})$, $s_{n} =\sum ^{n}_{i=0} e_{i}$, and $f( n) =s_{n} /n$.
Since the minimality condition of $a_{n}$ , we have $e_{n}<n$
It is sufficient to show that $e_{n}$ is eventually constant.
Since $n\mid \nu _{p}( a_{0} a_{1} ,..,a_{n}$), we have $n\mid s_{n}$, i.e. $f( n) \in \mathbb{N}$.
We will prove that $f( n+1) \leq f( n)$ for any $n\in \mathbb{N}\ \cdots ( \heartsuit )$.
Assume, for the sake of contradiction, that $f( n+1) \geq f( n) +1$.
Then we have $e_{n+1} \geq f( n) +n+1$.
This is clearly impossible because $e_{n+1} < n+1$ and $f( n) >0$.
So we must have $f( n+1) \leq f( n) $.
Since $f( n) \in \mathbb{N}$ and $( \heartsuit )$, $f( n)$ is eventually constant, say $k\in \mathbb{N}$.
Let $C >0$ be a constant such that for any $n >C$, $f( n) =k$.
Let $n$ be an arbitrary integer larger than $C$.
Then $s_{n} =kn$ and $e_{n+j} =s_{n+j} -s_{n+j-1} =k( n+j) -k( n+j-1) =k$ for any $j\in \mathbb{N}$
$\blacksquare $
dangerousliri
02.02.2020 21:51
Circumcircle wrote: Let $a_0$ be a fixed positive integer. We define an infinite sequence of positive integers $\{a_n\}_{n\ge 1}$ in an inductive way as follows: if we are given the terms $a_0,a_1,...a_{n-1}$ , then $a_n$ is the smallest positive integer such that $\sqrt[n]{a_0\cdot a_1\cdot ...\cdot a_n}$ is a positive integer. Show that the sequence $\{a_n\}_{n\ge 1}$ is eventually constant. Note: The sequence $\{a_n\}_{n\ge 1}$ is eventually constant if there exists a positive integer $k$ such that $a_n=c$, for every $n\ge k$. Here it is my solution: Define $b_n=\sqrt[n]{a_0\cdot a_1\cdot ...\cdot a_n}$. From definition $b_n\in\mathbb{N}$. So we have $\sqrt[n+1]{a_0\cdot a_1\cdot ...\cdot a_n\cdot b_n}=\sqrt[n]{a_0\cdot a_1\cdot ...\cdot a_n}=b_n\in\mathbb{N}$. Then since $a_{n+1}$ is the smallest positive integer such that $\sqrt[n+1]{a_0\cdot a_1\cdot ...\cdot a_n\cdot a_{n+1}}\in\mathbb{N}$, hence $a_{n+1}\leq b_n$. So we have $b_{n+1}=\sqrt[n+1]{a_0\cdot a_1\cdot ...\cdot a_n\cdot a_{n+1}}\leq \sqrt[n+1]{a_0\cdot a_1\cdot ...\cdot a_n\cdot b_n}=b_n$. Hence $b_n$ is non-increasing sequence of positive integers which means is eventually constant so exist constants positive integers $c,M$ such that $b_n=c$ for all $n\geq M$. So for all $n\geq M$ we have $\sqrt[n]{a_0\cdot a_1\cdot ...\cdot a_n}=c\Rightarrow \sqrt[n+1]{a_0\cdot a_1\cdot ...\cdot a_n\cdot a_{n+1}}=c\Rightarrow \sqrt[n+1]{c^n\cdot a_{n+1}}=c\Rightarrow a_{n+1}=c$, so taking $N=M+1$ we have $a_n=c$ for all $n\geq N$ which meas that the sequence is eventually constant.
TheUltimate123
17.10.2020 01:21
Solved with nukelauncher. Observe that \(a_1=1\) always, so instead start our indexing at \(a_1\), \(a_2\), \(\ldots\). For all primes \(p\), note that \(\nu_p(a_n)\) is the unique integer in the range \(0\le a_n\le n-1\) for which \[n\quad\text{divides}\quad a_1+\cdots+a_n.\]By USAMO 2007/1, the sequence \(\nu_p(a_1)\), \(\nu_p(a_2)\), \(\ldots\) is eventually constant. Hence \(a_1\), \(a_2\), \(\ldots\) is eventually constant, which is what we needed to show.
ThisNameIsNotAvailable
02.01.2023 12:45
Circumcircle wrote: Let $a_0$ be a fixed positive integer. We define an infinite sequence of positive integers $\{a_n\}_{n\ge 1}$ in an inductive way as follows: if we are given the terms $a_0,a_1,...a_{n-1}$ , then $a_n$ is the smallest positive integer such that $\sqrt[n]{a_0\cdot a_1\cdot ...\cdot a_n}$ is a positive integer. Show that the sequence $\{a_n\}_{n\ge 1}$ is eventually constant. Note: The sequence $\{a_n\}_{n\ge 1}$ is eventually constant if there exists a positive integer $k$ such that $a_n=c$, for every $n\ge k$. My solution. If $a_0=1$, then $a_n=1$ for all $n$. Otherwise, let $p$ be a prime divisor of $a_0$ and $b_n=\nu_p(a_0\cdot a_1\cdots a_n)$. We claim the sequence $\left( \frac{b_n}{n} \right)_{n\geq 1}$ is decreasing. Then it will eventually be constant since $n\mid b_n\implies b_n\geq n$ and the conclusion follows. From the definition, $n\mid b_n$ and $n+1\mid b_{n+1}$. Let $b_n=kn$, then $n+1\mid kn+\nu_p(a_{n+1})\implies n+1\mid \nu_p(a_{n+1})-k$. Notice $\nu_p(a_{n+1})\leq n$ since its smallestnest, we have $\nu_p(a_{n+1})\leq k\implies \frac{b_{n+1}}{n+1}=\frac{b_n+\nu_p(a_{n+1})}{n+1}\leq\frac{b_n}{n}$.