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.

Solution 1:

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.