# Recurrence relation, induction and Fibonacci numbers

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?

• possible duplicate math.stackexchange.com/questions/236578/… Nov 20, 2012 at 23:57
• it is but i want someone to check what i have done,
– Matt
Nov 21, 2012 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. =) Nov 21, 2012 at 0:18
• @amWhy, Okay, thank you :)
– Matt
Nov 21, 2012 at 6:37

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.

• I put an answer with the bit about how the determinant condition implies a degree two linear recurrence. Nov 21, 2012 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, 2012 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$? Nov 21, 2012 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, 2012 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. Nov 21, 2012 at 6:40

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

• 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, 2012 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/… Nov 21, 2012 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.$ Nov 21, 2012 at 3:07
• @Matt, for your last part (b), $x_{n+2} = 3 x_{n+1} - x_n.$ Nov 21, 2012 at 5:18