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.


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.


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


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,


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

Real Numbers, Sequences and Series: Part 6


Given x \in \Re_{+} and n \in N, we can find y \in \Re such that x=y^{n}.


Let A={u \in \Re_{+}: u^{n}<x}. If x<1, then x^{n} <x and hence x \in A. On the other hand, if x \geq 1, then 1/2 \in A. Thus, A is non-empty. Next, observe that if v^{n}>x, then v is an upper bound of A. In particular, \{ 1+x\} is an upper bound of A.

By the least upper bound property, A admits a least upper bound. Let us denote it by y. We will rule out the possibilities y^{n}>x and y^{n}<x implying that x=y^{n}.

If y^{n}<x, let a=\frac{x-y^{n}}{nx} and z=y(1+a). It can be checked that z^{n}<x so that z \in A. But, y <x, contradicting the fact that y is the least upper bound of A. (we have used the inequalities 7 and 8 in the previous blog).

On the other hand, if y^{n}>x, let \frac{y^{n}-x}{ny^{n}} and w=y(1-b). Again, it can be verified that w^{n}>x and hence w is an upper bound of A. But, w<y, contradicting the fact that y is the least upper bound of A. Hence, y^{n}=xQED.

In particular, we see that there is an element \alpha \in \Re such that \alpha^{2}=2 and hence also (-\alpha)^{2}=2 which means that the equation x^{2}=2 has two solutions. The positive one of those two solutions is \sqrt{2}. In fact, the above theorem has guaranteed its extraction of the square root, cube root, even nth root of any positive number. You could ask at this stage, if this guarantees us extraction of square root of a negative number. The answer is clearly no. Indeed, we have

x^{2} \geq 0 for x \in \Re.


We can further extend \Re to include numbers whose squares are negative, which you know leads to the idea of complex numbers.

We have shown that Q is a subset of \Re. One can also show that between any two distinct real numbers there is a rational number. This naturally leads to the decimal representation of real number: Given any real number x and any q \in N, we can get a unique a_{0} \in Z and unique a_{1},a_{2}, \ldots a_{q} \in N such that 0 \leq a_{1} \leq a_{2} \ldots a_{q} \leq 9 and

|x-(a_{0}+a_{1}/10+a_{2}/100+\ldots + \frac{a_{q}}{10^{q}})|<\frac{1}{10^{q}}

You are invited to try to  prove this familiar decimal representation.

If we have a terminating decimal representation of a real number, then surely it is rational.But, we know that rationals like 1/3, 1/7, 1/11, do not have a terminating decimal expansion.

It is clear that the decimal representation of \sqrt{2} cannot terminate as it is not rational. There are many elements of \Re which are not in Q. Any element of \Re which is not in is called an irrational number, and irrational numbers cannot have terminating decimal representation.

More later,

Nalin Pithwa

Real numbers, sequences and limits: part IV

Representation of Q on the Number Line.

We have seen earlier that every element of can be represented on a straight line with a certain point representing 0. Positive integers are represented by points to the right of this marked point at equal lengths, and negative integers are similarly represented by points to the left of this.

We can use the same straight line to represent the newly constructed rational numbers as follows.

We know that we can divide a line segment, using a straight edge and compass, into q equal parts. So, the line segment between 0 to 1 can be divided into q equal parts for every positive integer q.

The points of division will now represent the numbers \frac{1}{q}, \frac{2}{q}, \ldots , \frac{q-1}{q}. It is now clear that any rational number of the form \frac{p}{q} can be represented on the straight line. We have seen that between any two distinct rational numbers r and r^{'}, no matter how close they are, we can always find another rational number between them, example, \frac{r+r^{"}}{2}. Geometrically, this means that between any two distinct points on the line representing rational numbers, there is a point between them representing a rational number.

One can ask: does every point on the line correspond to a rational number? Note that we also have a point on the line representing length of the diagonal of a square of side 1. But, we shall show in the next blog that the length of the diagonal of unit square does not correspond to a rational number.

To prepare the ground for such discussions, let us start with a few definitions:

A subset A \subset Q is said to be bounded below if there exists a rational number \alpha such that

\alpha \leq \beta for every \beta \in A

and \alpha is called a lower bound of A. Similarly, A \subset Q is said to be bounded above if there is a \gamma \in Q such that \beta \leq \gamma, and \gamma is called an upper bound of A. A set which is bounded above and also bounded below is called a bounded set. Observe that if a set has a lower bound \alpha then it has many more like \alpha -1, \alpha -2, \ldots. Similarly, a set that is bounded above has many upper bounds. If there is a least element of all these upper bounds, then we call it the least upper bound of the set. But, it is not true that every set of rational numbers which is bounded above has a least upper bound. We can say similar things about sets which are bounded below. Some sets may have least upper bound. For example, the set of negative rational numbers is certainly bounded above and it is easy to see that 0 is the least upper bound.

More later,

Nalin Pithwa

Real Numbers, Sequences and Series: part I:

 Natural Numbers.

Natural numbers are perhaps, the earliest mathematical notions of man. The difference between a pack of wolves and one wolf, a swarm of bees and one bee, a school of fish and a single fish, a heap of stones and a single stone, etc., may have led primitive man tbo systematize the idea of numbers. The fact that in Sanskrti (and in some other ancient Indo-European languages) there are usages where one object, two objects and many objects are distinguished, example, narah, nari, naraah — indicates man’s attempt to distinguish betweeh numbers. Heaps of stones found in caves, where early man lived, and the discovery of animal bones on which notches have been cut in regular series of five are indicative of devices by the human beings of yore to keep count of their livestock. That is how they understood plurality.

But, what do we understand by numbers? Is number the same thing as plurality ? We often use expressions like “there are five fingers on my hand”, “Pandavas were five brothers”, “there are five books on this table”, “there are five mangoes in the basket”, etc. Observe what we are talking about. In the first case, we were talking about a set of fingers on my hand, in the next about a set of brothers, next about a set of books  on a table, next about a set of mangoes. But to each of these sets we attached the common attribute “five”. Why was that? There must have been something common in all these sets to justify our attaching the common attribute. The commonality between them is that the elements of one set can be put in one-to-one correspondence with the elements of the other sets under discussion.

We say that two sets A and B are equinumerous (or of the same cardinality) if there is a map

f: A \rightarrow B

which is one-to-one and onto, that is, a bijection. One sees that if A and B are equinumerous and the sets B and C are also equinumerous, then so are A and C. One can easily observe that being equinumerous is an equivalence relation among sets.

This relation decomposes any class of sets into disjoint equivalence classes of sets. Two sets are in the same equivalence class if they are equinumerous. The equivalence class is characterized by a common property of its members, that is, any two of them are equinmerous. This characterizing property is what we would like to call the number of elements of the set belonging to the equivalence class. Since equivalence classes, into which we have classified the sets, are disjoint, the characterizing property associated with disjoint classes are distinct. “Commonness”, “common property” or ‘characteristics” is too imprecise an idea to be handled easily; some authors have defined the number of elements of a set as the equinumerous class to which it belongs. Thus, the number “two” would mean the class of all pairs, the number “three” the class of all triplets, …and so on. But, this too has some foundational problems which are hard to circumvent. We do not go into the details of such things here.

Instead, we adopt the axioms devised by Peano for the natural numbers N with the following properties:

1) There is a map (called the successor map) from N to N, sending an element n to n^{+} (called the successor of n), which is injective, that is, n \neq m \Longrightarrow n^{+} \neq m^{+}

2) There is an element 1 that is not a successor of any element (that is, 1 is not in the image of any successor map, that is, 1 \neq n^{+} for all n \in N). Also, every other element of N is the successor of some element of N.

3) Suppose that A \subseteq N and that (a) 1 \in A (b) n^{+} \in A whenever n \in A. Then, A=N, that is, the only subset of N which contains 1 and the successor of each of its elements in N itself.

The third axiom is known as the Principle of Mathematical Induction.

More later,

Nalin Pithwa