Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
possible duplicate math.stackexchange.com/questions/236578/… –  amWhy Nov 20 '12 at 23:57
    
it is but i want someone to check what i have done, –  Matt Nov 21 '12 at 0:10
    
Yes, I see that. That's why I didn't vote to close. I simply wanted to provide the link, in case it helps. =) –  amWhy Nov 21 '12 at 0:18
    
@amWhy, Okay, thank you :) –  Matt Nov 21 '12 at 6:37
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
I put an answer with the bit about how the determinant condition implies a degree two linear recurrence. –  Will Jagy Nov 21 '12 at 2:52
    
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? –  Matt Nov 21 '12 at 5:52
    
@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$? –  Brian M. Scott Nov 21 '12 at 6:12
    
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? –  Matt Nov 21 '12 at 6:35
    
@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. –  Brian M. Scott Nov 21 '12 at 6:40
show 6 more comments

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

share|improve this answer
    
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$? –  Matt Nov 21 '12 at 2:59
    
@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: math.stackexchange.com/questions/241647/… –  Will Jagy Nov 21 '12 at 3:04
    
@Matt, anyway, for your first three questions $x_{n+2} = 4 x_{n+1} - x_n. $ Compare your $1,1,3,11,41.$ –  Will Jagy Nov 21 '12 at 3:07
    
@Matt, for your last part (b), $x_{n+2} = 3 x_{n+1} - x_n.$ –  Will Jagy Nov 21 '12 at 5:18
add comment

Your Answer

 
discard

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.