Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = a_2 = 1$.

$(i)$ Assume that all $a_n$ are integers. Prove that they are all odd and the integers $a_n$ and $a_{n+1}$ are coprime for $n \in \mathbb N$

$(ii)$ Assume that the set $\{a_n , a_{n+1} , a_{n+2}\}$ is pairwise coprime for $n \in \mathbb N$. Prove that all $a_n$ are integers by induction.

$(b)$ Consider the recurrence relation $a_{n+2}a_n = a^2_{n+1} + 1$ with $a_1 = 1, a_2 = 2$ and compare this sequence to the Fibonacci numbers. What do you find? Formulate it as a mathematical statement and prove it.

share|cite|improve this question
(ii) is kind of strange : the notion of coprimality doesn't really make sense for non-integers, so in some sense it's making the statement: 'assume $\{a_n, a_{n+1}, a_{n+2}\}$ are integers for all $n\in\mathbb{N}$; prove that all $a_n$ are integers.' – Steven Stadnicki Nov 13 '12 at 19:10
I noticed that in part (b) the $a_6 = 121/2$ is not an integer. – sperners lemma Nov 13 '12 at 19:42
@spernerslemma It's subtle but the recurrence is changed in part b. (+2 becomes +1) – EuYu Nov 13 '12 at 19:52
@EuYu, so it's going odd, even, odd, even, .. and so we get odd/even! thanks. – sperners lemma Nov 13 '12 at 19:55
@spernerslemma Yea. From a brief inspection, it seems like the sequence of odd Fibonacci numbers $F_{2n+1}$ – EuYu Nov 13 '12 at 19:56

Here is a hint how to solve (i).

We are given the recurrence $$a_1 = 1,\, a_2 = 1,\, a_{n-1} a_{n+1} = a_n^2 + 2$$

Lemma When $n > 1$, $a_{n} < a_{n+1}$. proof: By induction assume $a_{n-1} < a_n$. $$a_{n+1} = \frac{a_n^2+2}{a_{n-1}} > \frac{a_n^2+2}{a_{n}} = a_n+\frac{2}{a_{n}} > a_n.$$

Corollary When $n > 2$, $a_n > 2$.

Theorem $a_n$ are all integers. proof: We have

  • $a_{n-1} a_{n+1} = a_{n}^2 + 2$
  • $a_{n-2} a_{n} = a_{n-1}^2 + 2$
  • $a_{n-3} a_{n-1} = a_{n-2}^2 + 2$

thus $a_{n-1}$ divides $a_{n-2}a_n - 2$ and $a_{n-2}^2+2$ thus it divides their sum: $a_{n-1}|a_{n-2}(a_{n-2}+a_n)$ multiply by $a_n$ to get $a_{n-1}|(a_{n-1}^2+2)(a_{n-2}+a_n)$ but $a_{n-1}\not|(a_{n-1}^2+2)$ [if it did then we would have $a_{n-1}|2$ which is a contradiction] so we deduce $a_{n-1}|a_{n-2}+a_n$. Squaring gives $a_{n-1}|a_{n-2}^2+2a_{n-2}a_n+a_n^2$ which we can rewrite to $a_{n-1}|a_{n-2}^2+2a_{n-1}^2+4+a_n^2$ but we already know $a_{n-1}|a_{n-2}^2+2+2a_{n-1}^2$ [since both $a_{n-2}^2+2$ and $2a_{n-1}^2$ are multiples of $a_{n-1}$] so we conclude that $a_{n-1}|a_{n}^2+2$.

Lemma $a_n$ are odd. proof: Let $o_i \equiv a_i \pmod 2$ this definition is valid due to $a_i$ being integers) then assume by induction $o_i = 1$ for all $i \le n$. Then clearly $o_{n+1} \equiv o_{n-1}^{-1}(o_{n}^2+2) \equiv 1^{-1} (1^2+0) \equiv 1 \pmod 2$.

Lemma For $n > 1$, $a_{n-1}$ and $a_{n}$ are coprime. proof: Suppose they were not, since the sequence is strictly increasing we have $a_{n-1}|a_{n}$ thus $a_{n-1}|a_{n-2}a_{n} = a_{n-1}^2+2$ thus $a_{n-1}|2$ contradiction.

share|cite|improve this answer
im confused where did a_{n-1} a_{n+1} = a_n^2 + 2$$ come into this? – simon Nov 13 '12 at 19:52
@simon, I don't understand what you are asking. That formula is the definition of the recurrence. – sperners lemma Nov 13 '12 at 19:54
the formula from the question is a_{n+2}a_n = a^2_{n+1} +2 – simon Nov 13 '12 at 19:55
@simon The index is just shifted if that's where your confusion is from. Replace $n$ by $n+1$ and you recover your recurrence. – EuYu Nov 13 '12 at 20:00
@EuYu ohhhh okay thankyouu :) makes sense now! – simon Nov 13 '12 at 20:09

Your Answer


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.