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}<a_{n+1}-\dfrac{a_n^2}{a_{n-1}}\leq \dfrac{1}{2}\forall n\geq 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”

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^*}$ .

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

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

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

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!

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

Pingback: Dãy tuyến tính cấp hai | Sharing

Pingback: Bài tập về dãy tuyến tính cấp hai | Sharing

	Nguyen Trung Tuan on Đề thi chọn HSG Quốc gia của M…
	Cao Yến Anh on Đề thi chọn HSG Quốc gia của M…
	Cao Yến Anh on Đề thi chọn HSG Quốc gia của N…
	Nguyen Trung Tuan on VMO 2019 Online
	Đào Trọng Toàn on VMO 2019 Online
	Hà Minh Hiếu on VMO 2019 Online
	Chiến Thang on IMO 2018 training (1)
	Duy on VMO 2019 Online
	Phan Nhật Huy on VMO 2019 Online
	Rena on VMO 2019 Online

August 2007
M	T	W	T	F	S	S
				Sep »
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Share this:

Like this:

Related

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

Leave a Reply Cancel reply