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

	Hoàng Anh on Đề chọn đội VMO 2018
	Nguyen Trung Tuan on Một số sách nên đọc đối với họ…
	Nam on Một số sách nên đọc đối với họ…
	IMO 2016 Shortlist –… on IMO 2016 Shortlist – Comb…
	IMO 2016 Shortlist –… on IMO 2016 Shortlist –…
	IMO 2016 Shortlist –… on IMO 2016 Shortlist – Number…
	IMO 2016 Shortlist –… on IMO 2016 Shortlist –…
	IMO 2016 Shortlist –… on IMO 2016 Shortlist – Number…
	Khánh Huyền on IMO 2017 – Day 2
	IMO 2016 Shortlist –… on IMO 2016 Shortlist –…

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