Sequences of integers

Posted by Nalin Pithwa

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}=1$ , $a_{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 Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

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

w

Connecting to %s

%d bloggers like this: