# 3. Mathematical induction, infimum, sumpremum and limits of sequences

Part 1.: Problems, solutions.
Part 2.: Problems, solutions.
Part 3.: Problems, solutions.
Part 4.: Problems, solutions.
Part 5.: Problems, solutions.
Part 6.: Problems, solutions.
Part 7.: Problems, solutions.

### Indukcja matematyczna

We start with the mathematical induction. It is a powerful tool to prove things. The sentences proved by this method will not have a continuous character like the rest of calculus, will only concern for example natural numbers.

It is a very simple and yet powerful method of making conclusions. Assume we have a sequence of batteries (arranged left to right) about which we know two facts:

• the first battery in the sequence has its minus side on the left
• each subsequent battery is placed well in the sense it has on the left side opposite sign then the previous battery on the right side,

then immediately we can tell, that all the batteries in the sequence have minus side on the left. Obvious, isn’t it? Those two pieces of deduction are called the first and the induction steps.

More generally we are given a sentence which depends on a natural number (in our example: n-th battery has minus side on the left) and we would like to prove that the sentence is true for any . The mathematical induction makes it sufficient to check only the two following facts:

• the sentence is true for (the first step)
• the following implication holds: if the sentence is true for , then it is true for (induction step).

Let us prove a mathematical fact using the induction. E.g. that for any natural , the sum equals . First we check the first step. Indeed for we get .

Next we check the induction step. Assume that the sentence is true for , meaning (we will call it the induction assumption). We would like to prove the sentence for , i.e. . Using the induction assumption:

Therefore:

and we are done. We have checked the induction step. Under the principle of induction we have proved that for all , .

### Infima and suprema

A number is an upper bound of a set if for every we get . Similarly is a lower bound of if for every we get .

If is an upper bound of and additionally it will be called the greatest element of , and such a lower bound will be called the least element of a set. Obviously a set may not have greatest or least element, eg. in there is no least element and neither there is the greatest one.

The least upper bound of a set (if it exists) will be called the supremum of and denoted as . The greatest lower bound of (if it exists) will be called infimum of and denoted . Notice that sometimes supremum or infimum may not be an element of the given set, eg. .

Other example. Let . Then , because it is the greatest element in this set — for every , and . Now, . Indeed, for all we get , because (so is a lower bound of ). Moreover, it is the greatest lower bound, because if , let be a natural number greater than . Then , so is not a lower bound of . We have proved that is its infimum.

If a set has no upper bound we will write and if it has no lower bound, we will write .

### Definition of a limit

The notion of sequence convergence seems intuitively clear. A sequence converges to limit if its elements are closer and closer to . E.g. sequence , for converges to zero. Speaking more precisely, for any , there exists , such that for all , distance between and is less than . So:

And indeed, , because if , let , then, if , then .

Meanwhile, sequence , does not converge to any limit, since for any and , for all , or .

### Squeeze theorem

Given two sequences i , which have limits and respectively and such that for any we have , we have also that .

Therefore if we study convergence of a sequence we may try to find sequences and such that for all and . Then also converges to — this theorem is usually called the squeeze theorem.

E.g, let , . Then for all . Since , also .

### Arithmetic of limits

We have a natural arithmetical theorem on limits. If and , then:

• ,
• ,
• ,
• , if (assuming that for any

Let us calculate the limit of . Notice that:

Since , , the numerator converges to , and since and , the limit of denominator is (we apply the theorem on arithmetic of limits). Therefore (again we apply the theorem).

### Bounded sequences

A sequence is bounded, if there exists , such that for any . We have the following theorem: if converges to zero and is bounded, then also converges to zero.

E.g. let . Obviously , where is bounded, and converges to zero. So .

### Infinite limits

If is such that for all there exists , such that for all we have , so if for arbitrarily large number from a given place on the elements of sequence are greater then this number we say that the sequence tends to infinity and write .

If a sequence is such that for any there exists , such that for all we have , we say that the sequence tends to minus infinity and write .

E.g. let . This sequence tends to infinity, because if , , let . Then for all , we get .

### Arithmetic of infinite limits

Let and be sequences of real numbers. Then

• if jest converges to any finite number or , and , then .
• if converges to any finite number or , and , then .
• if converges to any finite number g>0 or , and , then .
• if converges to any finite number g<0 or , and , then .
• if converges to any finite number g>0 or , and , then .
• if converges to any finite number g<0 or , and , then .
• if converges to any finite number g, and , then .

Notice that this theorem does not tell anything about some types of limit operation, in which we can tell nothing about the limits. E.g. operations like , or . In this cases usually some further calculations are needed to be able to use the above theorem.

E.g., let . Therefore . Since , . Because , we get that .

### Number e

Imagine that you have a bank account with interest rate of a year! But you have only in this account. If interest rates are calculated every year, after one year you will have dollars. But if the interest rates were calculated twice a year you will get a half of your money twice a year, so at the end of the year you will have . If it would be calculated four times a year, you will get , monthly . It is clear that the final amount of money increases if the frequency of calculating interest rate increases. How big this amount can be?

Obviously we ask about the limit of sequence , . The answer is quite surprising. The limit of this sequence is an irrational number, which plays a huge role in mathematics and is denoted by . .

Knowing that , we can calculate limits of many other sequences, e.g. . Notice, that , so .

### Cauchy condition

A sequence is a Cauchy sequence if for any positive arbitrarily small from some place on the distance between any two elements of the sequence is less than . So:

E.g.: sequence is a Cauchy sequence. Indeed, let . Then let . Then for all we get:

It turns out that a sequence of real numbers is a Cauchy sequence if and only if it converges to a finite number.