# Two lemmas on linear sequences of order two

Note: My English is so bad but don’t worry about that! 🙂

A sequence $(a_n)$ is called linear of order two if there are real numbers $p,q$ such that $a_{n+2}=pa_{n+1}+qa_n\;\forall n=1,2,3,...$

In this topic we’ll use ideas in proofs of two following lemmas to solve some Olympiad problems.

lemma 1. If $(a_n)_{n\geq 1}$ be sequence difined by $a_1=x,a_2=y,a_{n+2}=pa_{n+1}+qa_n(n=1,2,...)$ then $a_{n+2}a_n-a_{n+1}^2=(-q)^{n-1}(a_3a_1-a_2^2)(n=1,2,...).$

Proof. We need only prove $a_{n+2}a_n-a_{n+1}^2=-q(a_{n+1}a_{n-1}-a_n^2)(n=2,3,...)$.

For any $n\geq 2$, fixed $n$.

If $a_n=0$ then $a_{n+1}=qa_{n-1}$ and $a_{n+2}a_n-a_{n+1}^2=-a_{n+1}a_{n+1}=-qa_{n+1}a_{n-1}=-q(a_{n+1}a_{n-1}-a_n^2)$.

If $a_{n+1}=0$ then $a_{n+2}=qa_n$ and $a_{n+2}a_n-a_{n+1}^2=a_{n+2}a_n=qa_n^2=-q(a_{n+1}a_{n-1}-a_n^2).$

If $a_na_{n+1}\not = 0$ then $\dfrac{a_{n+2}-qa_n}{a_{n+1}}=p=\dfrac{a_{n+1}-qa_{n-1}}{a_n}$ therefore $a_{n+2}a_n-qa_n^2=a_{n+1}^2-qa_{n+1}a_{n-1}$ and $a_{n+2}a_n-a_{n+1}^2=-q(a_{n+1}a_{n-1}-a_n^2)\Box$.

Lemma 2. If a sequence of non-zero numbers $(a_n)_{n\geq 1}$ satisfying for some number $a$ : $a_1,a_2,\dfrac{a_1^2+a_2^2+a}{a_1a_2}\in\mathbb{Z},a_{n+2}=\dfrac{a_{n+1}^2+a}{a_n}(n=1,2,...)$ then $\{a_1,a_2,...\}\subseteq \mathbb{Z}.$

Proof. From hypothesis we have $a_{n+2}a_n-a_{n+1}^2=a_{n+1}a_{n-1}-a_n^2\forall n\geq 2$ (because they are equal to $a$), therefore $a_{n+2}a_n+ a_n^2= a_{n+1}a_{n-1}+ a_{n+1}^2\forall n\geq 2$ so $a_n(a_{n+2}+a_n)=a_{n+1}(a_{n+1}+a_{n-1})\forall n\geq 2$(*).

By (*) and $a_n\not =0\forall n\geq 1$ we have $\dfrac{a_{n+2}+a_n}{a_{n+1}}=\dfrac{a_{n+1}+a_{n-1}}{a_n}=...=\dfrac{a_3+a_1}{a_2}=\dfrac{a_1^2+a_2^2+a}{a_1a_2}:=p\in\mathbb{Z}\forall n\geq 1$, so $a_{n+2}=pa_{n+1}-a_n\forall n\geq 1$(**).

Final, by (**) and $a_1,a_2\in\mathbb{Z}$ we have $a_n\in\mathbb{Z}\forall n\geq 1\Box$.

Now, before try to solve following problems, please read again two proves of two those lemmas.

Problem 1.

Let $(a_n)_{n\geq 1}$ be sequence difined by $a_1=1,a_2=3,a_n^2=1+a_{n-1}a_{n+1}\forall n\geq 2$. Prove that $\{a_1,a_2,...\}\subseteq \mathbb{N}$.

Problem 2.

Let $(a_n)_{n\geq 1}$ be sequence difined by $a_1=20,a_2=30,a_{n+1}=3a_n-a_{n-1}\forall n\geq 2$. Find all positive integer numbers $n$ such that $5a_na_{n+1}+1$ be perfect square.

Problem 3.

Let $(a_n)_{n\geq 1}$ be sequence difined by $a_1=2,a_{n+1}=3a_n+\sqrt{8a_n^2+1}\forall n\geq 1.$ Prove that $\{a_1,a_2,...\}\subseteq \mathbb{N}$.

Problem 4.

Let $(a_n)_{n\geq 1}$ be sequence difined by $a_1=a_2=1,a_{n+1}=\dfrac{a_n^2+1}{a_{n-1}}\forall n\geq 2$. Prove that

$\{a_1,a_2,...\}\subseteq \mathbb{N}$.

Problem 5.

Let $(a_n)_{n\geq 0}$ be sequence difined by $a_0=1,a_1=45,a_{n+2}=45a_{n+1}-7a_n\forall n\geq 1.$

a)Find the number of positive integer divisors of $a_{n+1}^2-a_na_{n+2}$ for any $n$.

b)Prove that for every $n$ the number $1997a_n^2+4\cdot 7^{n+1}$ is a perfect square.

Problem 6.

The sequence of reals $(x_n)$ is difined by $x_1=1,x_{n+1}=\dfrac{3x_n+\sqrt{5x_n^2-4}}{2}\forall n\geq 1.$ Prove that $x_n\in\mathbb{Z}\forall n\geq 1.$

Problem 7.

$(a_n)_{n\geq 1}$ be sequence difined by $a_1=1,a_2=2,a_{n+2}=3a_{n+1}-a_n\forall n\geq 1$. Prove that $a_{n+2}+a_n\geq 2+\dfrac{a_{n+1}^2}{a_n}\forall n\geq 1.$

Problem 8.

The sequence $a_1,a_2,...$ is defined by $a_1=1, a_2 = 2, a_{n+2}= 3a_{n+1} - a_n\forall n\geq 1$. The sequence $b_1,b_2,...$ is defined by $b_1=1,b_2=4, b_{n+2} = 3b_{n+1}-b_n\forall n\geq 1$.

a)Prove that $5a_n^2-b_n^2=4\forall n\geq 1$.

b)Show that the positive integers $a, b$ satisfy $5a^2 - b^2 = 4$ iff $a=a_n,b=b_n$ for some $n$.

Problem 9.

The sequence $a_1,a_2,...$ is defined by $a_1=1, a_2 = 7, a_{n+2}= 14a_{n+1} - a_n\forall n\geq 1$. The sequence $b_1,b_2,...$ is defined by $b_1=0,b_2=1, b_{n+2} = 14b_{n+1}-b_n\forall n\geq 1$. Show that the non-negative integers $a, b$ satisfy $a^2 - 48b^2 = 1$ iff $a=a_n,b=b_n$ for some $n$.

Problem 10.

The sequence $a_1,a_2,...$ is defined by $a_1=a_2=a_3=1, a_{n+3}= \dfrac{a_{n+2}a_{n+1}+2}{a_n}\forall n\geq 1$. Prove that $a_n\in\mathbb{N}\forall n\geq 1$.

Problem 11.

The sequence $a_0,a_1,a_2,...$ is defined by $a_0=3,a_1=17, a_{n+2}= 6a_{n+1} - a_n\forall n\geq 0$. Prove that $\dfrac{a_n^2-1}{2}$ is a perfect square for every $n$.

Problem 12.

The sequence of integers $a_1,a_2,...$ is defined by $a_1=2, a_2 = 7, -\dfrac{1}{2}. Prove that for every $n$ , $a_n$ is odd.

Problem 13.

Find the number of positive integer sequences $u_1,u_2,...$ such that $u_1=1$ and $u_nu_{n+2}=u_{n+1}^2+2003\forall n\geq 1.$

Problem 14.

Consider the sequence $(a_n)_{n\geq 1}$ difined by $a_1=a_2=1,a_3=199$ and $a_{n+1}=\dfrac{1989+a_na_{n-1}}{a_{n-2}}\forall n\geq 3.$ Prove that $a_n\in\mathbb{N}\forall n$.

Problem 15.

Let $a,b,c$ be positive reals. The sequence $a_1,a_2,...$ is difined by $a_1=a,a_2=b$ and $a_{n+1}=\dfrac{a_n^2+c}{a_{n-1}}\forall n\geq 2.$ Prove that $\{a_n|n\in\mathbb{N}\}\subseteq\mathbb{N}$ iff $a,b,\dfrac{a^2+b^2+c}{ab}\in\mathbb{N}.$

Problem 16.

Define $a_1=1,a_2=7,a_{n+2}=\dfrac{a_{n+1}^2-1}{a_n}\forall n\geq 1$. Prove that $9a_na_{n+1}+1$ is a perfect square for every positive integer $n$.

## 8 thoughts on “Two lemmas on linear sequences of order two”

1. psquang says:

P.1 By lemma 2 , we have $a_{n+1}=3a_n-a_{n-1}$.
Alternatively ,$a_1,a_2\in\mathbb{Z}$, so we have $a_n\in\mathbb{Z}\forall n\in\mathbb{N^*}$.

2. psquang says:

P.2
By inductive we can prove that $5a_{n}.a_{n+1}+1=(a_n+a_{n+1})^2+501$ .
Now , by some easy arguments, we have iff $n>250$ then $n^2+1$ can’t be a perfect square .Follow the condition, easily to realize that $a_{n+1}>a_n \forall n\in \mathbb{N^*}$, and with $n\ge 4$ then $a_n+a_{n+1} >250$.
So $n\le 3$.
Test for $n\le 3$ we get $n=3$ .
done

3. psquang says:

The general problem.for $k\in\mathbb{N^*}$
We have $a_{n+1}-ka_n=\sqrt{(k^2-1)a_n^2+l}$(*)

Squared two sides of (*), we get :

$a_{n+1}^2+k^2.a_n^2-2k.a_n.a_{n+1}=(k^2-).a_n^2+l$

Or:$a_{n+1}^2+.a_n^2-2k.a_n.a_{n+1}=l$
Similary:
$a_n^2+a_{n-1}^2-2.a_{n-1}.a_n=l$
So :
$a_{n+1}^2-a_{n-1}^2=2k.a_n.(a_{n+1}-a_{n-1}$.
Alternatively, $a_{n+1}>a_n>a_{n-1}$, so

$a_{n+1}=ka_n-a_{n-1}$

4. psquang says:

Edit for P.2’solution :
On third line , move $n^2+1$ by $n^2+501$.
Sorry ,Tuan.

5. trungtuan says:

to Quang: Not necessary use induction.

As lemma 1, we have $a_{n+2}a_n-a_{n+1}^2=500\forall n=1,2,...$, or $(3a_{n+1}-a_n)a_n-a_{n+1}^2=500\forall n=1,2,...$ therefore we have that identity!

6. Tuan says:

Problem 17.
Let $\{a_n\}_{n\geq 1}$ be a sequence with $a_1 = 1$, $a_2 = 4$ and for all $n > 1$,$a_{n} = \sqrt{ a_{n-1}a_{n+1} + 1 } .$
a) Prove that all the terms of the sequence are positive integers.

b) Prove that $2a_na_{n + 1} + 1$ is a perfect square for all positive integers $n$.