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 n (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 n. The mathematical induction makes it sufficient to check only the two following facts:

  • the sentence is true for n=0 (the first step)
  • the following implication holds: if the sentence is true for n=k, then it is true for n=k+1 (induction step).

Let us prove a mathematical fact using the induction. E.g. that for any natural n, the sum 0+1+2+\ldots+n equals \frac{n(n+1)}{2}. First we check the first step. Indeed for n=0 we get 0=\frac{0\cdot 1}{2}.

Next we check the induction step. Assume that the sentence is true for n=k, meaning 0+\ldots+k=\frac{k(k+1)}{2} (we will call it the induction assumption). We would like to prove the sentence for n=k+1, i.e. 0+1+\ldots+k+(k+1)=\frac{(k+1)(k+2)}{2}. Using the induction assumption:

    \[0+\ldots k+(k+1)=\frac{k(k+1)}{2}+k+1\]

Therefore:

    \[=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+2)(k+1)}{2}\]

and we are done. We have checked the induction step. Under the principle of induction we have proved that for all n, 0+1+2+\ldots+n=\frac{n(n+1)}{2}.

Infima and suprema

A number x\in\mathbb{R} is an upper bound of a set A\subseteq\mathbb{R} if for every a\in A we get a\leq x. Similarly x\in\mathbb{R} is a lower bound of A\subseteq\mathbb{R} if for every a\in A we get a\geq x.

If x is an upper bound of A and additionally x\in A it will be called the greatest element of A, 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 (0,1) there is no least element and neither there is the greatest one.

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

Other example. Let B=\left\{\frac{1}{n+1}\colon n\in\mathbb{N}\right\}. Then \sup B=1, because it is the greatest element in this set — for every n\in\mathbb{N}, \frac{1}{n+1}\leq 1 and \frac{1}{0+1}=1. Now, \inf B=0. Indeed, for all n\in\mathbb{N} we get \frac{1}{n}\geq 0, because 1>0 (so 0 is a lower bound of B). Moreover, it is the greatest lower bound, because if x>0, let n be a natural number greater than \frac{1}{x}. Then \frac{1}{n+1}<x, so x is not a lower bound of B. We have proved that 0 is its infimum.

If a set A has no upper bound we will write \sup A=\infty and if it has no lower bound, we will write \inf A=-\infty.

Definition of a limit

The notion of sequence convergence seems intuitively clear. A sequence a_n converges to limit g if its elements are closer and closer to g. E.g. sequence \frac{1}{n}, for n>0 converges to zero. Speaking more precisely, for any \varepsilon>0, there exists N, such that for all n>N, distance between a_n and g is less than \varepsilon. So:

    \[\forall_{\varepsilon>0}\exists{N\in \mathbb{N}}\forall_{n>N}|a_n-g|>\varepsilon\]

And indeed, \lim_{n\to\infty} \frac{1}{n} =0, because if \varepsilon>0, let N=\left\lceil\frac{1}{\varepsilon}\right\rceil, then, if n>N, then \left|\frac{1}{N}-0\right|<\varepsilon.

Meanwhile, sequence (-1)^n, does not converge to any limit, since for any g and \varepsilon=1, for all N, n>N, |(-1)^{2n}-g|>\varepsilon or |(-1)^{2n+1}-g|>\varepsilon.

Squeeze theorem

Given two sequences a_n i b_n, which have limits a and b respectively and such that for any n\in\mathbb{N} we have a_n\leq b_n, we have also that a\leq b.

Therefore if we study convergence of a sequence x_n we may try to find sequences a_n and b_n such that a_n\leq x_n\leq b_n for all n\in \mathbb{N} and \lim_{n\to\infty} a_n=\lim_{n\to\infty} b_n=g. Then also x_n converges to g — this theorem is usually called the squeeze theorem.

E.g, let x_n=\frac{(-1)^n}{n}, n>0. Then \frac{-1}{n}\leq x_n\leq \frac{1}{n} for all n>0. Since \lim_{n\to\infty} \frac{-1}{n}=\lim_{n\to\infty} \frac{1}{n}=0, also \lim_{n\to\infty}x_n=0.

Arithmetic of limits

We have a natural arithmetical theorem on limits. If a_n\to a and b_n\to b, then:

  • a_n+b_n\to a +b,
  • a_n-b_n\to a -b,
  • a_n\cdot b_n\to a \cdot b,
  • \frac{a_n}{b_n}\to \frac{a}{b}, if b\neq 0 (assuming that b_n\neq 0 for any n\in\mathbb{N}

Let us calculate the limit of a_n=\frac{3n^3-2n^2+2}{-n^3+2n-2015}. Notice that:

    \[\frac{3n^3-2n^2+2}{-n^3+2n-2015}=\frac{n^3\left(3-\frac{2}{n}+\frac{2}{n^3}\right)}{n^3\left(-1+\frac{2}{n^2}-\frac{2015}{n^3}\right)}=\frac{3-\frac{2}{n}+\frac{2}{n^3}}{-1+\frac{2}{n^2}-\frac{2015}{n^3}}\]

Since \frac{2}{n}\to 0, \frac{2}{n^3}\to 0, the numerator converges to 3, and since \frac{2}{n^2}\to 0 and \frac{2015}{n^3}\to 0, the limit of denominator is -1 (we apply the theorem on arithmetic of limits). Therefore \lim_{n\to\infty}a_{n}=\frac{3}{-1}=-3 (again we apply the theorem).

Bounded sequences

A sequence y_n is bounded, if there exists m, such that |y_n|\leq m for any n\in\mathbb{N}. We have the following theorem: if x_n converges to zero and y_n is bounded, then x_n\cdot y_n also converges to zero.

E.g. let a_n=\frac{(-1)^n}{2^n}. Obviously a_n=(-1)^n\cdot \frac{1}{2^n}, where (-1)^n is bounded, and \frac{1}{2^n} converges to zero. So \lim_{n\to\infty} a_n=0.

Infinite limits

If a_n is such that for all m\in\mathbb{N} there exists N\in\mathbb{N}, such that for all n>N we have a_n> m, 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 \lim_{n\to\infty} a_n=\infty.

If a sequence a_n is such that for any m\in\mathbb{N} there exists N\in\mathbb{N}, such that for all n>N we have a_n< -m, we say that the sequence tends to minus infinity and write \lim_{n\to\infty} a_n=-\infty.

E.g. let a_n=3^n. This sequence tends to infinity, because if m\in\mathbb{N}, m>0, let N=\lceil \log_3 m\rceil. Then for all n>N, we get a_n>m.

Arithmetic of infinite limits

Let a_n and b_n be sequences of real numbers. Then

  • if a_n jest converges to any finite number or \infty, and b_n\to\infty, then a_n+b_n\to\infty.
  • if a_n converges to any finite number or -\infty, and b_n\to-\infty, then a_n+b_n\to-\infty.
  • if a_n converges to any finite number g>0 or \infty, and b_n\to\infty, then a_n\cdot b_n\to\infty.
  • if a_n converges to any finite number g<0 or -\infty, and b_n\to\infty, then a_n\cdot b_n\to-\infty.
  • if a_n converges to any finite number g>0 or \infty, and b_n\to-\infty, then a_n\cdot b_n\to-\infty.
  • if a_n converges to any finite number g<0 or -\infty, and b_n\to-\infty, then a_n\cdot b_n\to\infty.
  • if a_n converges to any finite number g, and b_n\to\pm\infty, then \frac{a_n}{b_n}\to 0.

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 \infty-\infty, or \frac{\infty}{\infty}. In this cases usually some further calculations are needed to be able to use the above theorem.

E.g., let a_n=n^2-n. Therefore a_n=n^2(1-\frac{1}{n}). Since \frac{1}{n}\to 0, (1-\frac{1}{n})\to 1. Because n^2\to\infty, we get that lim_{n\to\infty}a_n=\infty.

Number e

Imagine that you have a bank account with interest rate of 100\% a year! But you have only 1USD in this account. If interest rates are calculated every year, after one year you will have (1+1)=2 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 \left(1+\frac{1}{2}\right)\cdot\left(1+\frac{1}{2}\right)=\left(1+\frac{1}{2}\right)^2=2,25. If it would be calculated four times a year, you will get \left(1+\frac{1}{4}\right)^4=2,44, monthly \left(1+\frac{1}{12}\right)^{12}=2,61. 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 \left(1+\frac{1}{n}\right)^n, n>0. 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 e. e=2,71828\cdots.

Knowing that \left(1+\frac{1}{n}\right)^n\to e, we can calculate limits of many other sequences, e.g. b_n=\left(\frac{n}{n+1}\right)^n. Notice, that b_n=\frac{1}{\left(\frac{n+1}{n}\right)^n}=\frac{1}{\left(1+\frac{1}{n}\right)^n}, so \lim_{n\to\infty} b_n=\frac{1}{e}.

Cauchy condition

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

    \[\forall_{\varepsilon>0}\exists_{N\in\mathbb{N}}\forall_{n,m>N} |a_n-a_m|<\varepsilon\]

E.g.: sequence \frac{(-1)^n}{2^n} is a Cauchy sequence. Indeed, let \varepsilon>0. Then let N=\lceil \log_2 \varepsilon\rceil +1. Then for all n,m>N we get:

    \[|a_n-a_m|\leq |a_n|+|a_m|<\frac{1}{2^N}+\frac{1}{2^N}=\frac{1}{2^{N-1}}\leq\varepsilon\]

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