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
    possible duplicate http://math.stackexchange.com/questions/236578/recurrence-relation-fibonacci-numbers?rq=12012-11-20
  • 0
    it is but i want someone to check what i have done,2012-11-21
  • 0
    Yes, I see that. That's why I didn't vote to close. I simply wanted to provide the link, in case it helps. =)2012-11-21
  • 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
    I put an answer with the bit about how the determinant condition implies a degree two linear recurrence.2012-11-21
  • 0
    for (a)(i), how do you prove this by induction? All i can see is going $n=k,\ k \rightarrow k+1$ and what happens from there? How can you prove $a_{n+2}$ is odd and not even?2012-11-21
  • 0
    @Matt: You’re assuming that $a_{n+1}$ is odd. That implies that $a_{n+1}^2+2$ is odd; why? If $a{n+2}$ were even, would $a_{n+2}a_n$ be even, or odd? And which must it be, if it’s equal to $a_{n+1}^2+2$?2012-11-21
  • 0
    Given that we are assuming $a_{n+1}$ is odd, then considering the square of an odd number is a odd number then +2 will still keep this odd. $a_{n+2}a_n$ would be odd also because if $a_{n+2}a_n$ = $a^2_{n+1} +2$ and $a^2_{n+1} +2$ is odd then its simply odd. Is that correct?2012-11-21
  • 0
    @Matt: Yes: $a_{n+2}a_n$ has to be odd, since it’s equal to an odd number, and that means that $a_{n+2}$ has to be odd.2012-11-21
  • 0
    Also, just a quick check for the coprime bit, is using the fact $a_n$ is odd mean that everything is odd therefore $d \mid a_{n+2}a_n - a^2_{n+1} \neq 2$ or any even number for that fact?2012-11-21
  • 0
    @Matt: It means that if $d$ divides $a_n$, $d$ must be odd. Thus, when we then discover that $d\mid 2$, we know that $d=1$ and conclude that $a_n$ and $a_{n+1}$ are coprime. **Note:** I had a typo in that bit, writing $a_{n-1}$ where I meant $a_{n+1}$, but I’ve fixed it now.2012-11-21
  • 0
    For (a)(ii) Why do you reduce the starting equations index's and why twice to make 3 equations? Also, where has the square gone from $a^2_{n+1}$? when you say that $a^2_{k+1} \mid a_{k+2}a_k -2$? otherwise the rest seems okay for now :P2012-11-21
  • 0
    @Matt: Looking back, I see that I didn’t actually need the third equation, so I’ve removed it. The two that I’ve kept are needed for the argument that shows that $a_{n+3}$ is an integer assuming that all of its predecessors are. I don’t understand your other question; I don’t believe that I do say that $a_{k+1}^2\mid a_{k+2}a_k-2$.2012-11-21
  • 0
    Ah that makes sense. As for my other question, you state that $a^2_{k+1} = a_{k+2}a_k -2$ and then go on to say $a_{k+1} \mid a_{k+2}a_k -2$ and thus my question, where did the square go?2012-11-21
  • 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
    For the starting point, where did the 2 go? or did you incorporate that into $K$? Also for the second bit, how did you get $x_3 = W x_2 - x_1$?2012-11-21
  • 0
    @Matt, for your first three problems $K=2.$ For your final problem $K=1.$ I published an article years ago, the relation $x_{n+2} = W x_{n+1} - x_n$ came up quite often. In particular, my comment at this problem, which is similar to yours: http://math.stackexchange.com/questions/241647/recurrence-and-fibonacci#comment533726_2416472012-11-21
  • 0
    @Matt, anyway, for your first three questions $x_{n+2} = 4 x_{n+1} - x_n. $ Compare your $1,1,3,11,41.$2012-11-21
  • 0
    @Matt, for your last part (b), $x_{n+2} = 3 x_{n+1} - x_n.$2012-11-21