\chapter{Real Sequences and series} \section{Real Sequences} Sequences are first covered in Set Theory as an ordered list of (possibly infinite) values, where repetition is allowed. It is then formally defined as a function mapping integers to elements of an arbitrary set. Set theory being as fundamental as it is, it didn't have much more to say about sequences. Elementary Number Theory goes further and delegates a chapter to 'integer sequences'; sequences of integers and rational numbers (so much for the 'integer part)'. This book discusses properties of any real sequence and particularly focuses on their behaviour as the amount of terms approaches infinity; elementary number theory does not concern itself with such concepts. This chapter introduces sequences in the space of real numbers and aims to build a correct rigorous understand of precisely what it means for a sequence to 'converge' to a value. This chapter additionally aims to act as a stepping stone for dealing with real functions. Real sequences are still functions, and despite being simpler, we will see that they form the fundamentals for rigorously defining ideas of analysis such as limits. Even if our sequences terms are all happen to be rational, it is still interesting to note that the sequence might be approaching an irrational number. These are the kinds of fun things that happen when you get 'real' about mathematics (okay, that was pretty lame). \begin{definition}[Real sequence] A \emph{real sequence} is a sequence $(x_n)^{\infty}_{n=1}$ contained in $\mathbb{R}$, so each $ x_n \in \mathbb{R}$ \end{definition} Some of the more interesting sequences are those that follow special properties \begin{definition}[Real bounded sequence] A real sequence is \emph{bounded above} iff there is some $M$ such that for all $n$ we have $x_n \leq M$ . A real sequence is \emph{bounded below} iff there is some $M$ such that for all $n$ we have $x_n \geq M$ A \emph{real bounded sequence} is a real sequence bounded above and below, equivalently, there is some $M$ such that for all $n$ we have $|x_n| \leq M$. \end{definition} We can think of bounded sequences as installing a set of walls that the sequence cannot pass. \begin{definition}[Real monotone sequence] A real sequence is \emph{monotone increasing} iff $x_n > x_{n-1}$. A real sequence is \emph{monotone decreasing} iff $x_n < x_{n-1}$. \end{definition} These types of sequences are always being pushed in the same direction; they can never back track. But what happens when an unstoppable force meets an immovable object? What happens when our monotone sequence is forced to increase (or decrease) but it is bounded, so our sequence faces the wall? Such a sequence would have to converge! It gets squeezed against the least upper bound of the sequence since by being monotone it cannot oscillate backwards. \begin{theorem}[Monotone convergence theorem] Bounded, monotone sequences are convergent \end{theorem} Note that there is another theorem called the monotone convergence theorem; it's completely different and it refers to a sufficient condition for swapping the order of taking a limit and an integral. Another tool that will become indispensable to us is the notion of a subsequence. \begin{definition}[Real subsequence] Let $(x_n)$ be a real sequence, then a \emph{real subsequence of $(x_n)$} is a real sequence of the form $(x_{n_{k}})$, where $(n_k)$ is some natural numbered sequence used index certain term from the original sequence. \end{definition} The idea is that subsequences of a sequence can 'skip' whatever terms of the original sequence as desired, so the multiples of 4 are a subsequence of the even numbers since it skips every odd index. \begin{definition}[Real convergent sequence] For a real sequence $(a_n)$, a \emph{limit of $(a_n)$} is a real number $L$ such that for any positive $\varepsilon$, we can find an integer $N$ so that whenever $n >N$ we have $| a_n -L| < \varepsilon$. Basically, $L$ is arbitrarily close all remaining terms of a sequence. A \emph{convergent real sequence} is a real sequence with a limit. \[ a_n \to L \iff \forall \varepsilon \in (0,\infty) ( \exists N \in \mathbb{N} [ n > N \implies |a_n - L| < \varepsilon ] ] ) \] \end{definition} We'll also call sequences that aren't convergent to be divergent sequences. We may also prematurely use the $\lim$ notation to denote what a sequence converges to; its 'limit at infinity'. We formally define limits for a general function later. \begin{proposition} The limit of a convergent real sequence is unique. \[x_n \to L \land x_n \to M \implies L = M \] \end{proposition} Due to the uniqueness of limits of convergent real sequences, we introduce the following notation for limits. \[x_n \to x \iff \lim_{n \to \infty} x_n = x\] \subsection{Bolzano-Weierstrass theorem} \begin{theorem}[Bolzano-Weierstrass theorem (BWT)] Let $(x_n)$ be a real, bounded (above and below) sequence, then $(x_n)$ has a convergent subsequence. \end{theorem} Obviously if $(x_n)$ is convergent, so are its subsequences. When $(x_n)$ is not convergent, we This follows from the fact that for any non convergence sequence we can choose \section{Real Cauchy sequences} Now that we know about convergent sequences, it's time to abstractify this conect a little bit with Cauchy sequences. These sequences are one that eventually 'settle down' (i.e they have 'convergent behaviour'). \begin{definition}[Real Cauchy sequence] A \emph{real Cauchy sequence} is a real sequence $(a_n)_{n \in \mathbb{N}}$, where for any positive $\varepsilon$, we can find an integer $N$ so that whenever $n,m > N$ we have $|a_n - a_m| < \varepsilon$. Basically, the absolute difference between all remaining terms can be bouned arbitrarily close to $0$ given enough terms of the sequence have passed. \[ (x_n)_{n\in \mathbb{N}} \text{ is Cauchy} \iff \forall \varepsilon \in (0,\infty) ( \exists N \in \mathbb{N} [ n,m > N \implies |a_n - a_m| < \varepsilon ] ] ) \] \end{definition} Isn't this the same as a convergent sequence? Due to the completeness of the real numbers, real cauchy sequences and real convergent sequences are the same, however Cauchy sequences are more general in that they don't require the limit to exist within the space itself; just the convergent behaviour. In spaces without completeness, convergent sequences are merely a special type of Cauchy sequence. The notion of convergent sequences and Cauchy sequences being the same is \emph{Cauchy completeness}. \begin{proposition} A real sequence is convergent iff it is Cauchy. In other words, the real numbers are Cauchy complete. \end{proposition} Proving that real sequences are Cauchy is not so bad.For real convergent sequence $x_n \to L$, we can let $|x_n -L| < \frac{\varepsilon}{2}$ for any $\varepsilon$ and proceed as such. \[|x_n - x_m| = |x_n -x_m +L -L| \leq |x_n - L | + |x_m - L| < \frac{2\varepsilon}{2} = \varepsilon\] To prove that Cauchy sequences are convergent sequences is more difficult; we need to prove that Cauchy sequences are bounded, and then the Bolzano Weierstrass theorem will immediately imply that it is convergent. Since the real numbers are Cauchy complete, Cauchy sequences are a useful tool for proving convergence of a sequence without the need to conjecture its limit. Let's say we have a real sequence and we want to see if it is convergent, but we don't know its limit. We can't prove it directly using the definition of a convergent sequence since it requires a limit, however one can resort to proving that the sequence is Cauchy to imply that the sequence is convergent. \subsection{Rationals are not Cauchy complete} \begin{definition}[Rational sequence] A \emph{rational sequence} is a sequence $(x_n)^{\infty}_{n=1}$ of rational numbers, so each $ x_n \in \mathbb{Q}$. Futhermore, we say that $x_n$ converges iff $|x_n -x_m|$ can be made as small as we like by finding some $N \leq n,m$. \end{definition} %Some examples include $x_n = \frac{1}{n} , y_n =\frac{2+n}{3+n} , z_n=n^2$. We can tell that as $n$ grows, $x_n$ approaches 0, $y_n$ approaches 1, and $z_n$ just blows up indefinitely. We will study formally what it means for sequences to 'approach' a number, but for now an intuitive understanding will do. Let's consider the rational sequence $x_n =\frac{4}{x_{n-1}+ \frac{2}{x_{n-1}}}, x_1=1 $. This is a rational Cauchy sequence, however as it turns out, this sequence does not approach any rational number! This means it is not convergent in $\mathbb{Q}$. This leads us to the following; instead of defining the real numbers as the Dedekind completeness of $\mathbb{Q}$, we can define the real numbers as the Cauchy completion of $\mathbb{Q}$ (with the Archimedian property, since some of the ordering properties are not implied by Cauchy completion). Similar to how Dedekind completion refers to creating equivalence classes of bounded sets with the same upper bounds, the Cauchy completion refers to creating equivalence classes of Cauchy sequences whose difference converges to $0$. In either case, the whole point of $\mathbb{R}$ is to 'patch up' $\mathbb{Q}$ so that Cauchy sequences and convergent sequences are equivalent notions and supremums always exist. \section{Squeeze theorem} Yet another intuitive result that we would like to prove. \begin{theorem}[Squeeze theorem] Let $a_n \to L$ and $c_n \to L$ with $a_n \leq b_n\leq c_n$, then $b_n \to L$. \end{theorem} \section{Limit supremum and infimum} What does the supremum of a sequence become eventually? \begin{definition}[Limit supremum] \[\limsup x_n = \lim_{N \to \infty} \sup (\{x_n : n \geq N \}) \] \end{definition} \begin{definition}[Limit infimum] \[\liminf x_n = \lim_{N \to \infty} \inf (\{x_n : n \geq N \}) \] \end{definition} BWT can be used to tell us that bounded real sets always have limit supremums and infimums. $x_n$ is a convergent real sequence iff $\limsup x_n =\liminf x_n$. \section{Series} Series are merely the limit of a type of infinite sequence where terms are added to the previous result, however the study of a particular sequences that converge to a series is particularly colorful. - partial sum \begin{definition}[Series] Given a sequence $\{x_n\}_{n=1}^{\infty}$, its \emph{series} is the limit of the sequence $s_1 =x_1 , s_n = s_{n-1} +x_n$, or otherwise $s_n = \sum^{n}_{k=1} x_k$; the partial sums made from $x_n$ (if the limit exists). If the limit exists, it is a convergent series, otherwise it is a divergent series. \[\sum^{\infty}_{n=1} x_n = S\] \end{definition} One can note that $x_n \to 0$ to have a chance of being a convergent series. However this condition alone will not suffice to prove that a series is convergent; we will look at the harmonic series as a counterexample to this claim. - absolutely convergent series - conditionally convergent series \section{Harmonic series} \begin{definition}[Harmonic series] \[ \sum^{\infty}_{n=1} \frac{1}{n} \] \end{definition} Even though the series progresses by quantities that get closer to 0, the series still doesn't converge. \begin{proposition} The harmonic series is divergent \end{proposition} The idea is that at any point in the series, we can still group enough terms to make an arbitrarily large number; this is essentially the \emph{Cauchy condensation test}, which we will cover soon. If we consider the behaviour of the Harmonic sequence rather than its divergent series, we note that it grows in a similar fashion to the natural logarithm, in fact their difference converges! It converges to a rather interesting number, the \emph{Euler-Mascheroni constant}. \begin{definition}[Euler-Mascheroni constant] \[ \gamma := \lim_{n \to \infty} [ H_n - \ln (n)] \] \end{definition} \section{Geometric series} The geometric sequence is typically introduced in high school. \begin{definition}[Geometric series] A \emph{geometric series} is a series of the following form. \[\sum^{\infty}_{n=1} ar^n \] \end{definition} \begin{proposition}[Closed form for geometric sequence] \[\sum^{n}_{k=1} ar^k = a\frac{1-r^{n+1}}{1-r}\] \end{proposition} \begin{corollary}[Closed form of a geometric series] \[\sum^{\infty}_{n=1} ar^n = \frac{a}{1-r}\] \end{corollary} \section{Convergent series tests} Series have a bit more structure than any ordinary limit, so they permit a wide range of 'tests' we can derive as general tools for checking convergence. \begin{theorem}[Absolute convergence test] Any absolutely convergent series is convergent. \end{theorem} \begin{theorem}[Comparison test] If $\sum^{\infty}_{n=1} y_n $ converges and $x_n \leq y_n$ then $\sum^{\infty}_{n=1} x_n$ converges. \end{theorem} \begin{theorem}[Limit comparison test] Consider the series $\sum^{\infty}_{n=1} x_n$ and $\sum^{\infty}_{n=1} y_n $ with strictly positive terms, if $\lim_{n \to \infty} \frac{x_n}{y_n} \neq 0$ then the series either both converge or both diverge. \end{theorem} \begin{theorem}[Ratio test] Consider the series $\sum^{\infty}_{n=1} x_n$ with strictly positive terms \[\lim_{n \to \infty} \frac{x_{n+1}}{x_{n}} = L\] The series converges when $L <1$, diverges when $L>1$. When $L=1$ the test is inconclusive. \end{theorem} \begin{theorem}[Leibniz test] If $x_n$ is monotone sequence and $x_n \to 0$ then $\sum^{\infty}_{n=1} (-1)^n x_n$ converges. \end{theorem} \begin{theorem}[$n$th root test] Consider the series $\sum^{\infty}_{n=1} x_n$ \[\mathrm{limsup} \sqrt{n}{|x_n|} =L\] The series converges when $L <1$, diverges when $L>1$. When $L=1$ the test is inconclusive. \end{theorem} \begin{theorem}[$P$ test] $\sum^{\infty}_{n=1} \frac{1}{n^p}$ converges for $p >1$ \end{theorem} \begin{theorem}[Cauchy condensation test] $x_n$ nonnegative, monotone decreasing sequence $\sum^{\infty}_{n=1} x_n$ converges iff $\sum^{\infty}_{n=1} 2^n x_{2^n}$ converges. \end{theorem} \begin{theorem}[Integral test] $\sum^{\infty}_{n=N} f(n) $ iff $\int^{\infty}_{N} f(x)dx$ converges \end{theorem} These tests are useful to verify that a series converges, however they don't offer a method to calculate the series itself. In the case of the geometric series we deduced its value by considering a closed form for partial sums and finding the limit of said closed form; we got lucky here, we won't always be able to do that. It's much more difficult to determine what a convergent series equals, however when we formally study differentiation we will unlock a tool called \emph{Taylor series} which are extremely useful for calculating series. That said, we should be happy; we can calculate geometric series and check convergence for a wide range of series. \chapter{Bachmann-Landau family of notations} It is a tool to describe the growth of functions and is used extensively in mathematical analysis, analytical number theory, numerical analysis. In computer science, one may way to consider a function that eats a number representing an input to some model of computation and spits out the amount of atomic steps that algorithm takes to terminate. Algorithms may have extremely complex behaviour, so usually such functions are unable to be explicitly documented by its mappings, but rather the asymptotic class it belongs to. Consider $f : X \to \mathbb{R}$ and $g : X \to \mathbb{R}$ \section{Original Bachmann-Landau notation} They notation were introduced in analytic number theory by Paul Bachmann and popularized by Edmund Landau. Hardy and Littlewood also made use of these notations and extended upon them. Unfortunately in modern times, computer science and analytic number theory have their own notations in use, however the use of big-$O$ and little-$o$ is understood universally in mathematics. \begin{definition}[Big-$O$ function class] \[f \in O (g) \iff \exists M \in \mathbb{R}_{+} [ \forall n \in X [ |f(n)| \leq M g(n) ] ]\] \[f \in O (g) \iff \sup_{n \in X} \frac{|f(n)|}{g(n)} < \infty\] \end{definition} \begin{definition}[Little-$o$ function class] \[f \in o(g)\] \end{definition} There are a following conventional abuse of notations associated with $O$, $o$, and related notations. The primary abuse of notation is using the equality sign instead of set inclusion sign, so some write $f=O(g)$ instead of $f \in O(g)$. The second prevalent abuse of notation is doing arithmetic with asymptotic classes, so some write $f+O(g)$ instead of $f+h,h \in O(g)$. \section{Knuth's notation} In the 1970s, Donald Knuth devised a range of standard function classes alongside $O$ and $o$ for use in computational complexity theory. Specifically, he introduced $\Omega$ ($\Omega$ existed before Knuth, however he created his own distict definition of the symbol to better suit the nature of his field), $\Theta$, and $\omega$. Computational complexity theory adheres to Knuth and the original Bachmann-Landau notations to describe the complexity of algorithms (where the function generally maps some notion of 'input size' to the amount of irreducible steps the algorithm takes). \begin{definition}[Big-$\Omega$ function class (Knuth)] \[f \in \Omega (g) \iff \exists M \in \mathbb{R}_{+} [ \forall n \in X [ f(n) \geq M g(n) ] \] \[f \in \Omega (g) \iff \inf_{n \in X} \frac{f(n)}{g(n)} > 0 \] \end{definition} \begin{definition}[Big-$\Theta$ function class (Knuth)] \[f \in \Theta (g) \iff \exists M_1,M_2 \in \mathbb{R}_{+} [ \forall n \in X [ M_1 g(n) \leq f(n) \leq M_2 g(n) ] ] \] \[f \in \Theta (g) \iff f \in O (g) \land g \in O (f)\] \end{definition} \begin{definition}[Little-$\omega$ function class] \[f \in \omega (g)\] \end{definition} \section{Vinogradov-Hardy-Littlewood notation} Before the time of Knuth and little after the creation of $O$ and $o$, various mathematicians working in analytic number theory extended upon Bachmann-Landau notation to describe a wider range of asymptotic behaviour of functions. Unlike Knuth whose notation only introduces more function classes, VHL notation introduced function relations. Though they could have been introduced as function classes, they are conventionally treated as relations. \begin{definition}[$\ll$ function relation (Vinogradov)] \[f \ll g \iff \sup_{n \in X} \frac{|f(n)|}{g(n)} < \infty \] \end{definition} \begin{definition}[$\gg$ function relation (Vinogradov)] \[f \gg g \iff \inf_{n \in X} \frac{f(n)}{g(n)} > 0 \] \end{definition} \begin{definition}[$\asymp$ function relation (Hardy-Littlewood)] \[f \asymp g \iff f \ll g \land g \ll f \] \end{definition} We can see that we have $f \ll g$ iff $f \in O(g)$, and $f \gg g$ iff $f \in \Omega(g)$ in the sense of Knuth, and hence $f \asymp g$ iff $f \in \Theta(g)$; so far these have been equivalent notations to Knuth. There are 2 more notations in analytic number theory that are not widespread in computational complextiy theory: $\Omgea$ in the sense of Hardy-Littlewood and $\sim$. \begin{definition}[Big-$\Omega$ function class (Hardy-Littlewood)] \[f \in \Omega (g) \iff \limsup_{n \to \infty} \frac{|f(n)|}{g(n)} > 0 \] \end{definition} \begin{definition}[$\sim$ function relation (Hardy-Littlewood)] \[f \sim g \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 \] \end{definition}