15
$\begingroup$

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
    $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.2012-08-15
  • 0
    A quick computer test finds only $n\in\{1,2,3\}$ among $n\le100000$.2012-08-15
  • 0
    @ 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.2012-08-15
  • 0
    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\}$.2012-08-15
  • 0
    @Harald Hanche-Olsen: Perfect. Thanks!2012-08-15
  • 0
    I presume you've already seen [this OEIS entry](http://oeis.org/A000085).2012-08-15
  • 0
    As the sequence is defined now we have no $\,a_1\,$...2012-08-15
  • 0
    @DonAntonio: what do you mean?2012-08-15
  • 0
    As you wrote the definition of $\,a_{n+1}\,\,,\,\,n>0\,$ , we cannot calculate $\,a_1\,$...2012-08-15
  • 0
    @DonAntonio: first of all, this second form wasn't written by me, but still $a_{1}=1$ when $n=0$. I'm not sure I clearly understand your point.2012-08-15
  • 0
    Ok, everything's clear now. Thanks.2012-08-15
  • 0
    @DonAntonio: Ok. Welcome anytime.2012-08-15

1 Answers 1

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, then $$a_n(a_n-1) If $a_{n-1}, this gives us $$a_{n-1}(a_n-1)=n-1 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}.

Since $x_n(x_n-1)=n$ and $a_n(a_{n+1}-1)=n$, if $a_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}} 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, it follows by induction that $x_{n-1} for all $n\ge4$, hence, $a_n. For $n=3$ we have $x_2=a_3=2.

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.

  • 0
    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)2012-08-15
  • 0
    where did you get from $a_{0}=1$?2012-08-15
  • 0
    thank you for your brilliant and simple approach!2012-08-15
  • 0
    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.2012-08-15
  • 0
    Absolutely awesome this proof!2012-08-15