2
$\begingroup$

$(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.

  • 1
    (_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.'2012-11-13
  • 0
    I noticed that in part (b) the $a_6 = 121/2$ is not an integer.2012-11-13
  • 0
    @spernerslemma It's subtle but the recurrence is changed in part b. (+2 becomes +1)2012-11-13
  • 0
    @EuYu, so it's going odd, even, odd, even, .. and so we get odd/even! thanks.2012-11-13
  • 0
    @spernerslemma Yea. From a brief inspection, it seems like the sequence of odd Fibonacci numbers $F_{2n+1}$2012-11-13

1 Answers 1

3

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.

  • 0
    im confused where did a_{n-1} a_{n+1} = a_n^2 + 2$$ come into this?2012-11-13
  • 0
    @simon, I don't understand what you are asking. That formula is the definition of the recurrence.2012-11-13
  • 0
    the formula from the question is a_{n+2}a_n = a^2_{n+1} +22012-11-13
  • 0
    @simon, what's the problem?2012-11-13
  • 1
    @simon The index is just shifted if that's where your confusion is from. Replace $n$ by $n+1$ and you recover your recurrence.2012-11-13
  • 0
    the formula from the question is a_{n+2}a_n = a^2_{n+1} +2 whereas you have written a_{n-1} a_{n+1} = a_n^2 + 2 ... so wondering where you got this second formula from?2012-11-13
  • 0
    @simon, sorry I don't think my answer will be much use to you, hopefully someone else will give something more useful.2012-11-13
  • 1
    @EuYu ohhhh okay thankyouu :) makes sense now!2012-11-13