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 VMO training 2017 – Part …
	Lê Minh Nhật on VMO training 2017 – Part …
	Đề thi chọn đội IMO… on Đề thi chọn đội IMO 2017 của I…
	AnhTú on Đề thi tuyển sinh vào lớp 10 t…
	Tien on Thặng dư bậc k
	Đề thi chọn đội IMO… on Đề thi chọn đội IMO 2017 của I…
	Tien on USA JMO 2017
	Tien on USA JMO 2017
	toicodongiuamotbienn… on Môđun của số phức
	Nguyen Trung Tuan on International Zhautykov Olympi…

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