0
$\begingroup$

1.(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 $\left\{ a_n,\ a_{n+1},\ a_{n+2}\right\}$ 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.

I have no idea where to start with 1(ai) but with 1(aii) i have started with:

Given that $\left\{a_n,\ a_{n+1},\ a_{n+2}\right\}$ is pairwise coprime you get $gcd(a_n,a_{n+1})=1,\ gcd(a_n,a_{n+2})=1,\ gcd(a_{n+1},a_{n+2})=1$

Using the initial terms, you can do base induction on $a_{n+2} = \frac{a^2_{n+1}+2}{a_n}$ to prove whether the next terms will be integers.

$a_3 = \frac{1^2+2}{1}$ $a_4 = \frac{3^2+2}{1}$ $a_5 = \frac{11^2+2}{3}$

gives:

$a_1=1,\ a_2 = 1,\ a_3 = 3,\ a_4 = 11,\ a_5 = 41$

which are all integers. So the base induction is correct.

Now for the inductive step $n=k, k \rightarrow k+1$

$a_{k+3} = \frac{a^2_{k+2}+2}{a_{k+1}}$. I am not sure how to prove this for the inductive step.

Also for (b) how do you formulate a mathematical statement and prove it?

  • 0
    @amWhy, Okay, thank you :)2012-11-21

2 Answers 2

4

I’ve not seen an entirely straightforward approach to the induction step in (a)(ii). One way, adapted from this answer, is to start from the fact that

$\begin{align*} a_{k+2}a_k&=a_{k+1}^2+2\text{ and}\\ a_{k+1}a_{k-1}&=a_k^2+2\;. \end{align*}$

From the first equation we have $a_{k+1}^2=a_{k+2}a_k-2$, so $a_{k+1}\mid a_{k+2}a_k-2$. By the induction hypothesis $a_{k-1}$ is an integer, so the second equation implies that $a_{k+1}\mid a_k^2+2$. Thus,

$a_{k+1}\mid(a_{k+2}a_k-2)+(a_k^2+2)=a_k(a_{k+2}+a_k)\;,$ and hence, multiplying by $a_{k+2}$ and using the first equation to substitute for $a_{k+2}a_k$, $a_{k+1}\mid a_{k+2}a_k(a_{k+2}+a_k)=\left(a_{k+1}^2+2\right)(a_{k+2}+a_k)\;.$

But $a_{k+2}$ is coprime to $a_{k+1}^2+2$ (why?), so $a_{k+1}\mid a_{k+2}+a_k$.

We want to show that $a_{k+1}\mid a_{k+2}^2+2$, so that $a_{k+3}$ will be an integer, so let’s get that square in: since $a_{k+1}\mid a_{k+2}+a_k$, it’s certainly true that $a_{k+1}\mid(a_{k+2}+a_k)^2=a_{k+2}^2+2a_{k+2}a_k+a_k^2$. Using the first equation again, we have

$a_{k+1}\mid a_{k+2}^2+2\left(a_{k+1}^2+2\right)+a_k^2=\left(a_{k+2}^2+2\right)+2a_{k+1}^2+2+a_k^2\;.$

Now apply the second equation on the righthand side and conclude that $a_{k+1}\mid a_{k+2}^2+2$.


For (a)(i) you can use induction to show that the $a_k$ are all odd. You know that $a_1$ and $a_2$ are odd. Suppose that $n\ge 1$ and $a_k$ is odd for each $k\le n+1$. Then $a_{n+2}a_n=a_{n+1}^2+2$, where $a_n$ and $a_{n+1}$ are both odd; is this possible if $a_{n+2}$ is even? Once you’ve got that, you can deal with the coprimeness. Suppose that $d>0$ divides both $a_n$ and $a_{n+1}$; then $d\mid a_{n+2}a_n-a_{n+1}^2=2$. Now use the fact that $a_n$ is odd.


For (b) calculate at least $a_1,a_2,a_3,a_4$, and $a_5$; they’re all Fibonacci numbers, and you’ll find that they fit into the Fibonacci sequence in a regular fashion that can easily be described by a formula of the type $a_n=F_{g(n)}$, where $g$ is a very simple function. You’re being asked to find $g$ and prove that the formula does indeed hold. Once you’ve figured out what $g$ is, this answer may be helpful.

  • 0
    @Matt: I don’t need it. I don’t really care at that point that $a_{k+2}a_k-2$ is equal to $a_{k+1}^2$; all I need is the fact that it’s a multiple of $a_{k+1}$, which follows from the equality, since $a_{k+1}$ is by hypothesis an integer.2012-11-21
2

Today seems to be Fibonacci Day.

THEOREM. Suppose we have a sequence of numbers $x_n$ that always fulfils $ x_{n+2} x_n - x_{n+1}^2 = K $ for a constant $K,$ suppose that $x_n \neq 0$ ever, and suppose $ x_3 = W x_2 - x_1, $ where $W$ is an integer or possibly rational number. Then, for all $n,$ we get $ x_{n+2} = W x_{n+1} - x_n. $

First note: there is always such a $W$ if $x_2 \neq 0,$ just define $W = (x_1 + x_3) / x_2.$

Second note: we can be sure that the $x_n \neq 0$ if they start out positive and always increase. Now that I think of it, if $K > 0$ and $x_2 \geq x_1,$ the sequence does increase forever. So there. Or, if $K = 0$ and $x_2 > x_1.$

Third Note: Another simple possibility is when $x_1, x_2, W$ are all integers, while $W$ is divisible by some prime $p,$ but $x_1, x_2$ are not divisible by $p.$ By induction on the index in $x_n,$ it follows that $x_n$ is never divisible by $p,$ written $x_n \neq 0 \pmod p,$ and in particular $x_n \neq 0.$ In this situation we may have $x_n$ sometimes negative without penalty.

PROOF: We will do one induction step, just up to $x_4.$ We start with $ x_3 = W x_2 - x_1, $ $ x_3 x_1 = x_2^2 + K, $ $ x_4 x_2 = x_3^2 + K. $ From the first we switch to get $ x_1 = W x_2 - x_3. $ From $ x_3 x_1 = x_2^2 + K $ we substitute in the $x_1$ value to get $ x_3 (W x_2 - x_3) = x_2^2 + K, $ or $ W x_2 x_3 = x_2^2 + (x_3^2 + K). $ From $ x_3^2 + K = x_4 x_2 $ we substitute to get $ W x_2 x_3 = x_2^2 + x_4 x_2 = x_2 (x_2 + x_4). $ We invoke the clause $x_2 \neq 0$ to get $ W x_3 = x_2 + x_4. $ That is, $ x_4 = W x_3 - x_2. $

A repeat of the same proof gives $ x_5 = W x_4 - x_3. $ Repeating more gives $ x_{n+2} = W x_{n+1} - x_n $ for all $n.$

BACK to the future: the set of sequences with $ x_{n+2} = W x_{n+1} - x_n $ is a vector space over the field of rational numbers. The dimension is exactly two. That means, if we can identify two such sequences, maybe $S_n, T_n,$ such that neither one is a constant multiple of the other, then any sequence $ x_{n+2} = W x_{n+1} - x_n $ is guaranteed to satisfy $ x_n = A S_n + B T_n $ for constants $A,B.$

  • 0
    @Matt, for your last part (b), $x_{n+2} = 3 x_{n+1} - x_n.$2012-11-21