Sequences of integers

Sequences of integers are a favourite of olympiad problem writers since such sequences involve several different mathematical concepts, including for example, algebraic techniques, recursive relations, divisibility and primality.

Problem:

Consider the sequence (a_{n})_{n \geq 1} defined by a_{1}=a_{2}=1a_{3}=199 and

a_{n+1}=\frac{1989+a_{n}a_{n-1}}{a_{n-2}} for all n \geq 3. Prove that all the terms of the sequence are positive integers.

Solution:

There is no magic or sure shot or short cut formula to such problems. All I say is the more you read, the more rich your imagination, the more you try to solve on your own.

We have a_{n+1}a_{n-2}=1989+a_{n}a_{n-1}

Replacing n by n-1 yields, a_{n}a_{n-3}=1989+a_{n-1}a_{n-2} and we obtain

a_{n+1}a_{n-2} - a_{n}a_{n-1}=a_{n}a_{n-3}-a_{n-1}a_{n-2}

This is equivalent to

a_{n-2}(a_{n+1}+a_{n-1})=a_{n}(a_{n-1}+a_{n-3})

or \frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}} for all n \geq 4. If n is even, we obtain

\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}= \ldots = \frac{a_{3}+a_{1}}{a_{2}}=200

while if n is odd,

\frac{a_{n+1}+a_{n-1}}{a_{n}}=\frac{a_{n-1}+a_{n-3}}{a_{n-2}}=\ldots=\frac{a_{4}+a_{2}}{a_{3}}=11

It follows that a_{n+1} = 200a_{n}-a_{n-1}, if n is even,

and a_{n+1}=11a_{n}-a_{n-1}, if n is odd.

An inductive argument shows that all a_{n} are positive integers.

More later,

Nalin Pithwa

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