Find the terms of the sequence $a_{n+1}=1+n/a_n$ that are natural numbers Let's consider the sequence $(a_n)_{n\in\mathbb{N}}$, defined by the following recurrence relation: 
$$
a_{n+1} =
\begin{cases}
1 + \frac{n}{a_{n}}\quad&n\gt0\\
1&n=0
\end{cases}
$$
Find all terms of the sequence that are natural numbers. 
Two things to mention here: 


*

*first one is that $a_{n}$ goes to $\infty$ when $n$ goes to $\infty$, 

*and the second point is that the product of the first $k$ terms of the sequence is an integer number.  


This is all I have so far.
 A: Obvious integer values are $a_1=1$, $a_2=a_3=2$. I'll show that these are the only ones.
First, we note that if $a_n<a_{n+1}$, then
$$a_n(a_n-1)<a_n(a_{n+1}-1)=n<a_{n+1}(a_{n+1}-1).$$
If $a_{n-1}<a_n<a_{n+1}$, this gives us
$$a_{n-1}(a_n-1)=n-1<a_n(a_n-1)<a_n(a_{n+1}-1)=n;$$
if $a_n$ was an integer, then so would $a_n(a_n-1)$, hence, $a_n$ cannot be an integer in this case. Thus, all we need to show is that $a_n$ is strictly increasing for $n\ge3$.
I'm sure there are numerous ways to prove that $a_n$ is strictly increasing for $n\ge3$, many of which will be purely technical. So far, my ideas have all centered around $a_n(a_n-1)\approx n-1/2$, which would in itself have sufficed to prove $a_n$ integral, and have gotten rather messy. I'll see if I can come up with a nice one.
Edit: I think I have a proof now that $a_n$ is strictly increasing for $n\ge3$.
Let $p_n(x)=x(x-1)-n$. This is increasing for $x\ge1/2$ and has positive root $x_n=1/2+\sqrt{n+1/4}$. We can then do induction on $x_{n-1}<a_n<x_n$.
Since $x_n(x_n-1)=n$ and $a_n(a_{n+1}-1)=n$, if $a_n<x_n$, then $a_{n+1}>x_n$.
if $a_n>x_{n-1}$, we get
$$a_{n+1}-1=\frac{n}{a_n}<\frac{n}{x_{n-1}}<x_{n+1}-1\Rightarrow a_{n+1}<x_{n+1}$$
where the last step relies on $x_{n-1}(x_{n+1}-1)>n$ which can be shown for $n>1$ by plugging in the values.
Since $x_n$ are increasing and $x_3<a_4<x_4$, it follows by induction that $x_{n-1}<a_n<x_n$ for all $n\ge4$, hence, $a_n<x_n<a_{n+1}$. For $n=3$ we have $x_2=a_3=2<x_3$.
How I got the idea in the first place?
I computed $a_n$ numerically (using Maple), and quickly found that $a_n(a_n-1)\approx n-1/2$. This lead me to think of proving that $a_n(a_n-1)$ was not an integer since this seemed to be true by a large margin. The brute force approach, which is what I started out trying, would have been to show this by proving the approximation was sufficiently accurate. However, since I had already observed that $a_n$ was increasing, comparing $x_n(x_n-1)$ to $x_n(x_{n+1}-1)=n$ the way I did was quite apparent.
