The infinite sequence $a_1,a_2,a_3,\ldots$ of positive integers is defined as follows: $a_1=1$, and for each $n \ge 2$, $a_n$ is the smallest positive integer, distinct from $a_1,a_2, \ldots , a_{n-1}$ such that: $$\sqrt{a_n+\sqrt{a_{n-1}+\ldots+\sqrt{a_2+\sqrt{a_1}}}}$$is an integer. Prove that all positive integers appear on the sequence $a_1,a_2,a_3,\ldots$
Problem
Source: Cono Sur Olympiad 2017, problem 6
Tags: cono sur, number theory
ThE-dArK-lOrD
21.08.2017 22:26
Let $b_n=\sqrt{a_n+\sqrt{a_{n-1}+\ldots+\sqrt{a_2+\sqrt{a_1}}}}$ for each positive integer $n$. We get that $b_{n+1}^2=b_n+a_{n+1}$ for every $n\in \mathbb{Z}^+$. We'll show that every positive integer appears at least once in the sequence $\{ b_n\}_{n\in \mathbb{Z}^+}$. Suppose to the contrary that there exists positive integer $l$ that doesn't appear in the sequence. Note that the sequence $\{ b_n\}$ is unbounded, so there exists (smallest) positive integer $m$ that $b_m<l$ and $b_{m+1}>l$. Says $b_m=l-e_1$ and $b_{m+1}=l+e_2$. We get $a_{m+1}=(l+e_2)^2-(l-e_1)$. By the definition of $a_{m+1}$, and the fact that $a_{m+1}\neq l^2-(l-e_1)$, which will lead to $b_{m+1}=l$, we get that there's a positive integer $p$ that $p\leq m$ and $a_p=l^2-(l-e_1)$. Since $l^2-(l-e_1)>(l-1)^2$, we get that $b_p=\sqrt{ b_{p-1}+a_p}>l-1\Rightarrow b_p\geq l$. So there's an integer $j\leq p-1$, smaller than $m$, that $b_j<l$ and $b_{j+1}>l$. Contradiction. Now, suppose there exists positive integer $h$ that doesn't appear in the sequence $\{ a_n\}_{n\in \mathbb{Z}^+}$. It's clear that there exist positive integer $N$ that $a_n\geq h$ for all $n>N$. Since $h$ doesn't appear in the sequence, we get that, for $n>N$, $b_n+h$ is not a perfect square. Contradiction to the claim proved above, done.
Vietnamisalwaysinmyheart
27.08.2017 19:25
Last spam in this summer, too bad that school will start tomorrow. My idea is exactly the same as @ThE-dArK-lOrD, but anyway
Consider the positive integer sequence: $x_n=\sqrt{a_n+\sqrt{a_{n-1}+\ldots+\sqrt{a_2+\sqrt{a_1}}}}$
We have that: $x_1=1,x_2=2,x_3=2,x_4=3$, for some easy computation.
The idea is to prove that $(x_n)$ contains all positive integer, here is my proof:
We prove by induction, that the value set of $x_1,x_2,...,x_n$ is $\{1,2,...,M\}$ for some $M$.
Since $(x_n)$ can't be bound, otherwise, there would be finitely value for $(a_n)$, which can't happen.
Hence, there must be an earliest index $n+1$, which turns the value set of $x_1,x_2,...,x_n$ is $\{1,2,...,M\}$ becomes: $\{1,2,...,M,M+k\}$.
If $k=1$, we have the inductive step.
If $k\geq 2$, this means the value: $(M+k-1)^2-N$, for some: $N\in \{1,2,..., M\}$ has appear in $a_1,a_2,...,a_n$, hence there exist: $i<n$ such that: $a_{i+1}^2=a_i+(M+k-1)^2-N> (M+1)^2-M=M^2+M+1>M^2$, hence: $a_{i+1}>M$, which is not true since the value set of $x_1,x_2,...,x_n$ is $\{1,2,...,M\}$.
Thus, we have that: $(x_n)$ contains all positive integer.
Now, suppose that $k$ is the smallest positive integer such that haven't been written in $(a_n)$.
Then: $x_n+k$ can only be square number for $n<N$, with some $N$, otherwise, there would be a suitable $(n,a)$ such that: $a^2-x_n=k$ and: $x_n+i$ can't be square anymore (if some are, $i$ will be written again in $(a_n)$), for $i=1,2,...,k-1$, and since $k$ is the smallest number that haven't written, now it's written in $(a_n)$, which is absurd.
But since: $(x_n)$ contains all positive integer, so the above can't happen! $\blacksquare$