Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  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. –  Chris's sis 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! –  Chris's sis Aug 15 '12 at 8:10

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
    
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) –  Chris's sis Aug 15 '12 at 14:46
    
where did you get from $a_{0}=1$? –  Chris's sis Aug 15 '12 at 14:47
    
thank you for your brilliant and simple approach! –  Chris's sis 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! –  Chris's sis Aug 15 '12 at 15:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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