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”

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s