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


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

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

2 Answers 2


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.

  • $\begingroup$ I put an answer with the bit about how the determinant condition implies a degree two linear recurrence. $\endgroup$
    – Will Jagy
    Nov 21, 2012 at 2:52
  • $\begingroup$ 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? $\endgroup$
    – Matt
    Nov 21, 2012 at 5:52
  • $\begingroup$ @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$? $\endgroup$ Nov 21, 2012 at 6:12
  • $\begingroup$ 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? $\endgroup$
    – Matt
    Nov 21, 2012 at 6:35
  • $\begingroup$ @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. $\endgroup$ 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.$

  • $\begingroup$ 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$? $\endgroup$
    – Matt
    Nov 21, 2012 at 2:59
  • $\begingroup$ @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/… $\endgroup$
    – Will Jagy
    Nov 21, 2012 at 3:04
  • $\begingroup$ @Matt, anyway, for your first three questions $x_{n+2} = 4 x_{n+1} - x_n. $ Compare your $1,1,3,11,41.$ $\endgroup$
    – Will Jagy
    Nov 21, 2012 at 3:07
  • $\begingroup$ @Matt, for your last part (b), $x_{n+2} = 3 x_{n+1} - x_n.$ $\endgroup$
    – Will Jagy
    Nov 21, 2012 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.