Sequences

Upper bound

Definition

$B \in \mathbb{R}$ is an upper bound for $\{ a_n \}^{\infty}_{n=n_0}$ if $a_n \leq B$ for all $n \in \mathbb{R}$.

Lower bound

Definition

$B \in \mathbb{R}$ is an upper bound for $\{ a_n \}^{\infty}_{n=n_0}$ if $a_n \geq B$ for all $n \in \mathbb{R}$.

Supremum, least upper bound

Definition

$S \in \mathbb{R}$ is the supremum, for $\{ a_n \}^{\infty}_{n=n_0}$ if $S \leq B$ for all upper bounds $B$.

$$ S = \min \{ B \in \mathbb{R} | a_n \leq B, \forall n \in \mathbb{N} \} $$

Infimum, greatest lower bound

Definition

$I \in \mathbb{R}$ is the infimum, for $\{ a_n \}^{\infty}_{n=n_0}$ if $I \geq B$ for all lower bounds $B$.

$$ I = \max \{ B \in \mathbb{R} | a_n \geq B, \forall n \in \mathbb{N} \} $$

Convergent sequences

Theoreme

Convergent sequences are bounded.

Proof

Let $(s_n)_{n \in \mathbb{N}}$ be a converging sequence, and let $s = \lim_{x\rightarrow \infty} s_n $.
Let us take $\varepsilon = 1$ and apply the definition of a limit. We know that there exists $N$ such that $n > N \Rightarrow | s_n - s | < 1 $. Now by the triangle inequality $n > N \Rightarrow |s_n| < |s| + 1$

$$ |s_n| = |s_n - s + s| \leq |s_n| + |s| \leq 1 + |s| $$

We can now define: $M := \max \{ |s|+1, |s_1|, \cdots , |s_N| \}$
This means $|s_n| \leq M$ for all $n \in \mathbb{N}$ and so $(s_n)$ is a bounded sequence.

$\square$

Monotonic sequences

• A sequence $\{ a_n \}^{\infty}_{n=n_0}$ is called monotone increasing if:

  $$ a_{n+1} \geq a_n \quad \forall n \geq n_0 $$

• A sequence $\{ a_n \}^{\infty}_{n=n_0}$ is called monotone decreasing if:

  $$ a_{n+1} \leq a_n \quad \forall n \geq n_0 $$

Monotone Convergence Theorem

• If \(\{a_n\}_{n=n_0}^\infty\) is a monotone increasing sequence, with supremum \(S\), then

  \[ a_n \to S \]

• If \(\{a_n\}_{n=n_0}^\infty\) is a monotone decreasing sequence, with infimum \(I\), then

  \[ a_n \to I \]

Proof

Since \(S\) is the supremum we have that \(|a_n - S| = S - a_n\) for all \(n \in \mathbb{N}\). Now let \(\epsilon > 0\) and assume that \(S - a_n \geq \epsilon\) for all \(n \in \mathbb{N}\). Then \(a_n \leq S - \epsilon\) for all \(n \in \mathbb{N}\), that is, \(S - \epsilon\) is an upper bound. This contradicts the fact that \(S\) is the supremum, so there must be some \(N \in \mathbb{N}\) such that \(S - a_N < \epsilon\).
Since \(a_n\) is monotone increasing \(a_n \geq a_N\) for all \(n \geq N\). So \[|a_n - S| = S - a_n \leq S - a_N < \epsilon\] for all \(n \geq N\).

Arithmetic mean - geometric mean inequality

Arithmetic mean - geometric mean inequality theorem

Let \(x_{1},\ldots,x_{n}\) satisfy \(x_{i}\geq 0\) for \(i=1,\ldots,n\). Then their geometric mean is at most their arithmetic mean:

\[ \sqrt[n]{x_{1}\cdot x_{2}\cdot\ldots\cdot x_{n}}\leq\frac{x_{1}+x_{2}+\ldots+x_{n}}{n} \]

with equality if and only if \(x_{1}=x_{2}=\ldots=x_{n}\).

Proof

We will prove it by induction over \(n\geq 1\).

• For \(n=1\): we get an equality

  \[ x=\sqrt{x}=\frac{x}{1}=x \]

• Suppose its true for any \(n\)-tuple of non-negative numbers. Consider an \((n+1)\)-tuple \(x_{1},\ldots,x_{n+1}\) and let \(\alpha\) be their arithmetic mean, that is:

  \[ \alpha=\frac{x_{1}+x_{2}+\ldots+x_{n+1}}{n+1} \]

  We now have

  \[ (n+1)\alpha=x_{1}+\cdots+x_{n+1}=\sum_{k=1}^{n+1}x_{k} \]

Examining different cases:

1. One of the numbers is 0, that is there exists some \(i\) such that \(x_{i}=0\). The inequality here is obvious as one side is 0. And for the other side to also be 0 we need that \(x_{k}=0\) for \(k=1,\ldots,n+1\), so equality only occurs in the case when all terms are equal.

2. When we have \(x_{i}=\alpha\), \(i=1,\ldots,n+1\), then we get equality by a simple computation:

   \[ \sum_{k=1}^{n+1}x_{k}=(n+1)\alpha \]

   so

   \[ \frac{\sum_{k=1}^{n+1}x_{k}}{n+1}=\alpha \]

   and

   \[ \sqrt[n+1]{x_{1}\cdot\ldots\cdot x_{n+1}}=\sqrt[n+1]{\alpha^{n+1}}=\alpha \]

3. Everything else! That is \(x_{k}>0\) for \(k=1,\ldots,n+1\) and not all the terms are equal. In this case there is an \(x_{i}\) strictly greater than \(\alpha\) and one that is strictly smaller (otherwise \(\sum_{k=1}^{n+1}x_{k}\neq(n+1)\alpha\)). Up to reordering, let's suppose that these numbers are \(x_{n}\) and \(x_{n+1}\), that is: \(x_{n}>\alpha\) and \(x_{n+1}<\alpha\). In particular, \(x_{n}-\alpha>0\) and \(\alpha-x_{n+1}>0\) so we have

   \[ (x_{n}-\alpha)(\alpha-x_{n+1})>0.\qquad(\star) \]

   We define a new real number \(y\) as

   \[ y=x_{n}+x_{n+1}-\alpha\geq x_{n}-\alpha>0 \]

   now

   \[ (n+1)\alpha=x_{1}+\cdots+\underbrace{x_{n}+x_{n+1}}_{y+\alpha}=x_{1}+\cdots+x_{n-1}+y+\alpha. \]

   so

   $$ n \cdot \alpha = x_{1}+\cdots+x_{n-1}+y $$

   And thus \(\alpha\) is also the arithmetic mean of \(x_{1},\ldots,x_{n-1},y\).
   By the induction hypothesis we have

   \[ \underbrace{\frac{x_{1}+\cdots+x_{n-1}+y}{n}}_{\alpha} \geq \sqrt[n]{x_{1} \ldots x_{n-1}y} \]

   and so

   \[ \alpha^{n} \geq x_{1}\ldots x_{n-1}y \]

   now

   \[ \alpha^{n+1} = \alpha^{n} \cdot \alpha \geq x_{1}\ldots x_{n-1}y\alpha \]

   But \(y = x_{n} + x_{n+1} - \alpha\) and so

   $$ y \cdot \alpha - x_{n} \cdot x_{n+1} = (x_{n} + x_{n+1} - \alpha)\alpha - x_{n}x_{n+1} $$ $$= x_{n}\alpha + x_{n+1}\alpha - \alpha^{2} - x_{n}x_{n+1} $$ $$ = (\alpha - x_{n+1})(x_{n} - \alpha) > 0 $$

   by the inequality \((\star)\) above.
   We thus have that \(y \cdot \alpha > x_{n}x_{n+1}\).
   In conclusion: \(\alpha^{n+1} > x_{1}\ldots x_{n-1} \cdot x_{n} \cdot x_{n+1}\), that is

   \[ \left(\frac{x_{1}+\cdots+x_{n+1}}{n+1}\right)^{n+1} > x_{1} \cdot \ldots \cdot x_{n+1} \]

as wanted. And that proves the theorem!

$\square$

Lemma

The sequences \((a_{n})_{n=1}^{\infty}\) and \((b_{n})_{n=2}^{\infty}\) have the following monotonicity properties:

1. \(a_{n+1} > a_{n}\) for \(n \geq 1\)

2. \(b_{n+1} < b_{n}\) for \(n \geq 2\)

Proofs

1. Let \(x_{1} = 1\), \(x_{2} = \ldots = x_{k} = \ldots = x_{n+1} = 1 + \frac{1}{n}\). We apply the AM-GM inequality to these numbers. Their arithmetic mean satisfies:

   \[ \frac{1 + \left(1 + \frac{1}{n}\right) + \cdots + \left(1 + \frac{1}{n}\right)}{n+1} = \frac{n + 1 + n \cdot \frac{1}{n}}{n+1} = 1 + \frac{1}{n+1} \quad (\star\star) \]

   Their geometric mean is

   \[ \sqrt[n+1]{x_{1} \ldots x_{n+1}} = \sqrt[n+1]{\left(1 + \frac{1}{n}\right)^{n}} \quad (\star\star\star) \]

   The \(x_{i}\)s are not all equal, so we know that \((\star\star) > (\star\star\star)\). From this:

   \[ 1 + \frac{1}{n+1} > \sqrt[n+1]{\left(1 + \frac{1}{n}\right)^{n}} \]

   And so:

   \[ a_{n+1} = \left(1 + \frac{1}{n+1}\right)^{n+1} > \left(1 + \frac{1}{n}\right)^{n} = a_{n} \]

2. This case is very similar to what we just did. We set \(y_{1} = 1\) and \(y_{2} = y_{3} = \cdots = y_{n+1} = 1 - \frac{1}{n} > 0\). Then:

   $$ \frac{\sum_{i=1}^{n+1} y_{i}}{n+1} = \frac{1 + n\left(1 - \frac{1}{n}\right)}{n+1} $$ $$ = \frac{1 + n - 1}{n+1} $$ $$ = 1 - \frac{1}{n+1} $$ $$ > \sqrt[n+1]{\left(1 - \frac{1}{n}\right)^{n}} $$

   by the arithmetic mean - geometric mean inequality applied to \(y_{1}, \ldots, y_{n+1}\). We deduce

   \[ \left(1 - \frac{1}{n+1}\right)^{n+1} > \left(1 - \frac{1}{n}\right)^{n} \]

   By taking the inverse on both sides, we reverse the inequality and we get:

   \[ b_{n+1} = \left(1 - \frac{1}{n+1}\right)^{-(n+1)} < \left(1 - \frac{1}{n}\right)^{-n} = b_{n} \]

as required.

$\square$

Lemma

For \(n \geq 2\):

\[ 0 < b_{n} - a_{n} < \frac{4}{n} \]

Proof

We already know that \(b_{n} - a_{n} > 0\). Let's check the other inequality:

\[ b_{n} - a_{n} = b_{n}\left(1 - \frac{a_{n}}{b_{n}}\right) \]

We have:

\[ a_{n} = \left(1 + \frac{1}{n}\right)^{n} = \left(\frac{n+1}{n}\right)^{n} \]

and

\[ b_{n} = \left(1 - \frac{1}{n}\right)^{-n} = \left(\frac{n}{n-1}\right)^{n} \]

so

$$ b_{n} - a_{n} = b_{n}\left(1 - \left(\frac{n+1}{n}\right)^{n}\left(\frac{n-1}{n}\right)^{n}\right) $$ $$ = b_{n}\left(1 - \left(\frac{n^{2}-1}{n^{2}}\right)^{n}\right) $$

Set \(q = \frac{n^{2}-1}{n^{2}} < 1\). We have:

\[ b_{n} - a_{n} = b_{n}(1 - q^{n}) \]

and so

\[ 1 - q^{n} = (1 - q)(1 + q + q^{2} + \cdots + q^{n-1}) \]

As \(q < 1\), we also have that \(q^{k} < 1\) and we can deduce that

\[ 1 - q^{n} < (1 - q) \cdot n \]

We've thus shown that

\[ b_{n} - a_{n} < b_{n}(1 - q) \cdot n \]

Now as

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

and \(b_n\) is decreasing so \(b_n \leq b_2 = 4\). We can conclude:

\[ b_n - a_n < 4 \cdot \frac{1}{n^2} \cdot n = \frac{4}{n} \]

$\square$

Squeeze theorem, Sandwhich theorem

Squeeze Theorem

If \((x_n)_{n=n_0}^{\infty}\), \((y_n)_{n=n_0}^{\infty}\) and \((z_n)_{n=n_0}^{\infty}\) are sequences that satisfy

\[ x_n \leq y_n \leq z_n \]

and if

\[ \lim_{n \to \infty} x_n = \lim_{n \to \infty} z_n = \ell \]

for \(\ell \in \mathbb{R}\) then

\[ \lim_{n \to \infty} y_n = \ell. \]

Euler's number

Definition

We define the real number \(e\) as the limit

\[ \lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = \lim_{n \to \infty} \left(1 - \frac{1}{n}\right)^{-n} = e \]

Approximating factorials

Theorem

For \(n \geq 2\) we have

\[ \frac{n^n}{e^{n-1}} < n! < n^n \]

Proof

We have

\[ n! = n(n-1)(n-2)\dots 2\cdot 1 \quad \text{so} \quad n! < \underbrace{n \cdot n \dots n}_{n \text{ times}} = n^{n} \]

Let us establish the second inequality. As \(e\) is the limit of an increasing sequence \(a_{k} = \left(1+\frac{1}{k}\right)^{k}\), we have that, for all \(k \geq 1\), \(e > a_{k} = \left(1+\frac{1}{k}\right)^{k}\). Thus

\[ e^{n-1} > \prod_{k=1}^{n-1}a_{k} (= a_{1} \cdot \dots \cdot a_{n-1}) \]

and from this

\[ e^{n-1} > a_{1} \cdot a_{2} \cdots a_{n-1} = \left(\frac{2}{1}\right)^{1}\left(\frac{3}{2}\right)^{2}\left(\frac{4}{3}\right)^{3} \cdots \left(\frac{n}{n-1}\right)^{n-1} \]

Many terms simplify through telescoping:

\[ a_{1} \cdot a_{2} \cdots a_{n-1} = \frac{n^{n-1}}{(n-1)!} = \frac{n^{n-1}}{(n-1)!} \cdot \frac{n}{n} = \frac{n^{n}}{n!} \]

Therefore

\[ e^{n-1} > \frac{n^{n}}{n!} \quad \text{and} \quad n! > \frac{n^{n}}{e^{n-1}} \]

This completes the proof.

$\square$

Stirlings formula theorem

\[ \lim_{n\to\infty} \frac{n!}{\left(\frac{n^{n}}{e^{n}}\right)\sqrt{2\pi n}} = 1 \]

Proof

We will use the result of the previous theorem. We have

\[ n! \sim \left(\frac{n^{n}}{e^{n}}\right)\sqrt{2\pi n} \]

Thus

\[ \frac{n!}{\left(\frac{n^{n}}{e^{n}}\right)\sqrt{2\pi n}} \to 1 \]

as \(n \to \infty\).

$\square$