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.

  • 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
    Absolutely awesome this proof!2012-08-15