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_n$ is given by $\frac{b_n}{b_{n-1}}$ where $b_n$ is the number of Young tableaux on $n$ elements. Don't know if this helps. – Cocopuffs Aug 15 '12 at 7:55
• A quick computer test finds only $n\in\{1,2,3\}$ among $n\le100000$. – Harald Hanche-Olsen Aug 15 '12 at 7:55
• @ Cocopuffs: noticed that in OEIS, but I don't see yet how it helps. If one may prove that $b_{n}$ is not an integer multiple of $b_{n-1}$ then it's helpful. – user 1357113 Aug 15 '12 at 8:01
• Sorry if I wasn't clear enough. I meant to say that for $n\le100000$, $a_n$ is an integer if and only if $n\in\{1,2,3\}$. – Harald Hanche-Olsen Aug 15 '12 at 8:09
• @Harald Hanche-Olsen: Perfect. Thanks! – user 1357113 Aug 15 '12 at 8:10

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.

• it's funny to see that the main core of the approach isn't that hard as I initially thought. I just missed that part! (+1) – user 1357113 Aug 15 '12 at 14:46
• where did you get from $a_{0}=1$? – user 1357113 Aug 15 '12 at 14:47
• thank you for your brilliant and simple approach! – user 1357113 Aug 15 '12 at 14:51
• The $a_0=1$ was purely a figment of my imagination as $a_0$ is not defined in the original problem desciption. Anyway, I don't use this anywhere. – Einar Rødland Aug 15 '12 at 15:16
• Absolutely awesome this proof! – user 1357113 Aug 15 '12 at 15:17