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.

  • 2
    $\begingroup$ $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. $\endgroup$ – Cocopuffs Aug 15 '12 at 7:55
  • $\begingroup$ A quick computer test finds only $n\in\{1,2,3\}$ among $n\le100000$. $\endgroup$ – Harald Hanche-Olsen Aug 15 '12 at 7:55
  • $\begingroup$ @ 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. $\endgroup$ – user 1357113 Aug 15 '12 at 8:01
  • $\begingroup$ 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\}$. $\endgroup$ – Harald Hanche-Olsen Aug 15 '12 at 8:09
  • $\begingroup$ @Harald Hanche-Olsen: Perfect. Thanks! $\endgroup$ – 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.

  • $\begingroup$ 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) $\endgroup$ – user 1357113 Aug 15 '12 at 14:46
  • $\begingroup$ where did you get from $a_{0}=1$? $\endgroup$ – user 1357113 Aug 15 '12 at 14:47
  • $\begingroup$ thank you for your brilliant and simple approach! $\endgroup$ – user 1357113 Aug 15 '12 at 14:51
  • $\begingroup$ 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. $\endgroup$ – Einar Rødland Aug 15 '12 at 15:16
  • $\begingroup$ Absolutely awesome this proof! $\endgroup$ – user 1357113 Aug 15 '12 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.