2

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

Cameron Buie
  • 102,994
simon
  • 37
  • 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.' – 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

1 Answers1

4

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.

sperners lemma
  • 2,219