**Maintainer:**admin

How to solve every problem. Will draw on examples from past finals, the 3 in-class tests, and assignments.

*1*Preliminaries¶

*1.1*Sets and functions¶

*1.2*Mathematical induction¶

*1.2.1*Proof by induction¶

Prove something by induction

*1.2.1.1*General solution¶

Easy

*1.2.1.2*Examples¶

*2*The real numbers¶

*2.1*The algebraic and order properties of R¶

*2.1.1*Proving that a square root is irrational¶

$\sqrt{a}$

*2.1.1.1*General solution¶

Proof by contradiction, assume rational (use a fraction in lowest form). Use divisibility by $a$, show that the numerator/denominator is a number is both divisible by $a$ and not.

*2.1.2*The arithmetic-geometric mean inequality¶

Prove it

*2.1.2.1*General solution¶

Use the fact that $(\sqrt{a} - \sqrt{b})^2 > 0$. Multiply that out, move things around.

*2.1.3*Bernoulli's inequality¶

Prove it

*2.1.3.1*General solution¶

By induction. Easy.

*2.2*Absolute value and the real line¶

*2.2.1*Finding an upper bound over an interval¶

Find a constant $M$ such that $|f(x)| \leq M$ for all $x$ in that interval.

*2.2.1.1*General solution¶

Usually $f(x)$ will will be a fraction. Then we just use techniques like the triangle inequality, multiplying by the conjugate, etc. We find an upper bound for the numerator, and a lower bound for the denominator, then take the reciprocal of the denominator and turn the lower bound into an upper bound. Then we just multiply the two upper bounds together.

*2.3*The completeness property of R¶

*2.3.1*Finding the supremum of a set¶

Given a set, find its sup or inf.

*2.3.1.1*General solution¶

*2.4*Applications of the supremum property¶

*2.4.1*The Archimedean property¶

State and prove it. Using this property, show that the inf of $\{1/n\}$ is 0.

*2.4.1.1*General solution¶

Property: for every $x \in \mathbb R$ there exists $n \in \mathbb N$ such that $n \geq x$.

Proof: by contradiction. Assume that $\mathbb N$ is bounded above, and thus has a supremum $x \in \mathbb R$. Consider $x-1$. This is less than the supremum and so there's some $m \in\mathbb N$ such that $m > x-1$, so $m + 1> x$. But $m \in \mathbb N$. So $x$ is not an upper bound of $\mathbb N$.

Inf: since the set is non-empty, and bounded below by 0, it must have an infimum. Show that there exists $n$ such that $n > 1/\epsilon$ for any $\epsilon > 0$ and then $1/n < \epsilon$, so $0 \leq \inf < \epsilon$ which means $\inf = 0$.

*2.4.2*The existence of irrationals¶

Prove that $\sqrt{a}$ exists in $\mathbb R$.

*2.4.2.1*General solution¶

Use the supremum property: $\{s \geq 0, s \in \mathbb R: s^2 \leq a\}$ has a supremum $x$ in $\mathbb R$. We show that it's not > or < $\sqrt{a}$: if $x^2 < a$, then $x+1/n$ is in the set by the Archimedean property (show this). Similarly for $x^2 > a$, except we show that there's an upper bound less than $x$ in that case.

*2.4.3*The density theorem¶

State and prove the density theorem for rationals and irrationals.

*2.4.3.1*General solution¶

Rationals: If $x, y \in \mathbb R$ with $x < y$, there exists $r \in \mathbb Q$ such that $x < r < y$. Proof: $y-x > 0$, and by the Archimedean property there exists $n$ such that $y-x > 1/n$. So $ny - nx > 1$, and $ny > nx + 1$. Also, there exists $m$ such that $m-1 \leq nx < m$, so $m \leq nx + 1 < m + 1$. So $ny > nx + 1 > m$, and $ny > m > nx$. Divide by $n$ and we get $y > m/n > x$ where $m/n$ is rational.

Irrationals: also dense. Apply the density theorem above to $x/\sqrt{2}$ and $y/\sqrt{2}$, then $r' = r\sqrt{2}$ is irrational and is in between $x$ and $y$.

*2.4.4*The uncountability of R¶

Prove the uncountability of $\mathbb R$ in two ways.

*2.4.4.1*General solution¶

Cantor's diagonal argument

Nested intervals thing (choose an interval that does not contain something in the list each time)

*3*Sequences and series¶

*3.1*Sequences and their limits¶

*3.1.1*Uniqueness of limits¶

Prove that the limit of a sequence is unique.

Suppose both $x'$ and $x''$ are limits. Then we have $|x_n - x'| < \epsilon/2$ for all $n \geq K'$, and $|x_n - x''| < \epsilon / 2$ for all $n \geq K''$. Let $K$ be the larger of $K'$ and $K''$. Then, by the triangle inequality, for $n \geq K$:

$$|x' - x''| = |x' - x_n + x_n - x''| \leq |x' - x_n'| + |x_n - x''| < \epsilon/2 + \epsilon/2 = \epsilon$$

Hence $x' - x'' = 0$ and so $x' = x''$.

*3.1.2*Finding the limit of a sequence using epsilon¶

Use inequalities, and the Archimedean property usually. Or, the theorem that if $|x_n - x| \leq Ca_n$ where $a_n$ converges to 0, then $(x_n)$ converges to $x$.

*3.1.3*Disproving convergence¶

Find some epsilon such that no matter what values we use for $K$, $|x_n - x| \geq \epsilon$

*3.2*Limit theorems¶

*3.2.1*Convergent sequences are bounded¶

prove this

*3.2.1.1*General solution¶

To prove that convergent sequences are bounded, let $\epsilon = 1$ (or just let $\epsilon$ remain $\epsilon$, up to you). So we know that $|x_n - x| < 1$ for all $n \geq K$. Then, applying the triangle inequality to the following, we get: $|x_n| = |x_n - x + x| \leq |x_n - x| + |x| < 1 + |x|$. So if we take the sup of $|x_1|$, $|x_2|$, etc, and $1+|x|$, then $|x_n| \leq M$ for all $n$. $\blacksquare$

*3.2.1.2*The limit of the product of two sequences¶

Prove that it's preserved, etc

$|x_ny_n - xy| = |(x_ny_n - x_ny) + (x_ny - xy)| \leq |x_n(y_n-y)| + |(x_n-x)y| = |x_n||y_n-y| + |x_n-x||y|$. We know that $|x_n|$ has an upper bound $M_1$. So let $M = \sup\{M_1, |y|\}$. So then we have $|x_ny_n - xy| \leq M|y_n-y| + M|x_n-x|$ and using $\epsilon/(2M)$ we get $|x_ny_n - xy| < M(\epsilon/(2M)) + M(\epsilon/(2M)) = \epsilon$. $\blacksquare$

*3.2.2*Squeeze theorem¶

State and prove it.

*3.2.2.1*General solution¶

State: If $X = (x_n)$ and $Y = (y_n)$ with $\lim X = \lim Y = z$, then $Z = (z_n)$ where $x_n \leq z_n \leq y_n$ holds for all $n \in \mathbb N$ has a limit of $z$.

Proof: If $w$ is the limit, then $|x_n-w| < \epsilon$, and $|z_n -w| <\epsilon$. From the inequality in the hypothesis, we have that $x_n-w \leq y_n- w \leq z_n-w$. Also, $-\epsilon < x_n - w < \epsilon$ and $-\epsilon < z_n -w < \epsilon$. So then $-\epsilon < y_n-w < \epsilon$ and so $|y_n-w| < \epsilon$ for all $\epsilon$ which shows that $w$ is the limit.

*3.2.3*The ratio test¶

State and prove it.

State: If $\lim(x_{n+1}/x_n) < 1$, then the limit of $(x_n)$ is 0.

Proof: Let $r$ be a number such that $L < r < 1$, and let $\epsilon = r - L > 0$. Then there exists $K \in \mathbb N$ such that if $n \geq K$, $|x_{n+1}/x_n - L| < \epsilon$. Then, if we add $L$ to both sides and use the triangle inequality, we get

$$\frac{x_{n+1}}{x_n} < L+ \epsilon = L + (r-L) = r$$

So then we have $0 < x_{n+1} < x_nr < x_{n-1}r^2 < \ldots x_Kr^{n-K+1}$. Then if we set $C = x_K / r^K$, we see that $0 < x_{n+1} < Cr^{n+1}$. Since $0 < r < 1$, then $\lim(r^n) = 0$ and so $\lim(x_n) = 0$ (since the sequence of $|x_n - x|$ is less than a constant multiple of another one that does converge to zero).

*3.3*Monotone sequences¶

*3.3.1*The monotone convergence theorem¶

State and prove it.

*3.3.1.1*General solution¶

State: A monotone sequence $X$ is convergent if and only if it's bounded.

Proof: If $X$ is bounded and increasing, there exists $M \in \mathbb R$ such that $x_n \leq M$. Also, according to the completeness property of $\mathbb R$, the set $\{x_n:n\in \mathbb N\}$ has a supremum in $\mathbb R$, which we will call $x^*$. We will show that $x^* = \lim(x_n)$. Given $\epsilon > 0$, $x^*-\epsilon$ is not an upper bound of the set, by definition of the supremum; consequently, there exists $x_k$ such that $x^*-\epsilon < x_k$. Also, we have that $x_k \leq x_n$ whenever $n \geq k$ since the sequence is increasing. Consequently, we have:

$$x^*-\epsilon < x_k \leq x_n \leq x^* \leq x^* + \epsilon, \quad n \geq k$$

and so $-\epsilon < x_n - x^* < \epsilon$ which means that $|x_n-x^*| < \epsilon$. So the sequence converges to $x^*$.

For decreasing sequences, we can use the negative of the sup to get the inf, or we can just prove it in the same way.

*3.3.2*Proving convergence of a monotone sequence¶

Given a sequence (probably inductively-defined), prove that it's monotone and then that it is bounded, then use that to prove that it's convergent.

*3.3.2.1*General solution¶

Show monotone by induction, then find a bound and prove it by induction. Then use the monotone convergence theorem.

For Euler's number, we use the binomial theorem, and the fact that $2^{p-1} \leq p!$.

*3.3.3*Calculating square roots¶

Write a sequence that converges to $\sqrt{a}$.

$s_1 = 1$ (arbitrary). $s_{n+1} = 1/2(s_n + a/s_n)$.

*3.4*Subsequences and the Bolzano-Weierstrass theorem¶

*3.4.1*Criteria for divergent subsequences¶

State and prove the equivalency

TFAE:

(i) A sequence $X = (x_n)$ does not converge to $x$.

(ii) There exists an $\epsilon > 0$ such that for any $k \in \mathbb{N}$, there exists $n_k \in \mathbb{N}$ such that $n_k \geq k$ and $|x_{n_k} - x| \geq \epsilon$.

(iii) There exists an $\epsilon > 0$ and a subsequence $(x_{n_k})$ of $X$ such that $|x_{n_k} - x| \geq \epsilon$ for all $k \in \mathbb{N}$.

Proof for (i) $\to$ (ii): just the definition of converging to a limit.

Proof for (ii) $\to$ (iii): Just find terms that fit the definition and make a subsequence out of them.

Proof for (iii) $\to$ (i): A subsequence satisfying the condition in (iii) (meaning that it does *not* converge to $x$) exists. So, the sequence as a whole cannot converge to $x$ either.

*3.4.2*Monotone subsequences¶

Prove that every sequence (even sequences that are not themselves monotone) has a monotone subsequence.

Proof: Consider the concept of a "peak" (a term in a sequence that is greater than everything that follows it). Any given sequence $X$ can have either finitely many (including zero) or infinitely many peaks. In the first case, we can simply take the first term after the last peak. Since this term is not a peak, there must be a term after it that is greater than it, and so on, until we get an increasing subsequence. In the second case, the subsequence of peaks is decreasing and thus monotone.

*3.4.3*The Bolzano-Weierstrass theorem¶

State and prove

A bounded sequence of real numbers has a convergent subsequence.

Proof: By the monotone subsequence theorem, this sequence must contain a monotone subsequence. Since it's also bounded, we can use the monotone convergence theorem to show that this subsequence is convergent as well.

*3.5*The Cauchy criterion¶

*3.5.1*Cauchy sequences¶

State what it means for a sequence to be Cauchy. Prove it.

State: for every $\epsilon> 0$, there exists $H$ such that for all $m, n \geq H$, we have that $|x_m - x_n| < \epsilon$.

To show a sequence is Cauchy: inequalities, etc. To show that a sequence is not: find an epsilon (win the game)

*3.5.2*Convergence and Cauchy sequences¶

Prove that they're equivalent (convergence implies Cauchy and vice-versa)

Lemma: if a sequence of real numbers is convergent, it is a Cauchy sequence. Proof: $\epsilon$ definition, using $|x_n - x| < \epsilon/2$ and $|x_m - x| < \epsilon/2$.

For →, we use the previous lemma. For ←, we first note that a Cauchy sequence is bounded (second lemma in previous section). By Bolzano-Weierstrass, there is a subsequence that converges to some number $x'$. We then use the $\epsilon$ definition for the sequence and the subsequence, and then we can sort of combine the two and then use the triangle inequality to conclude that the sequence itself converges to $x'$, and so the sequence is convergent. (Use $\epsilon/2$.)

*3.6*Properly divergent sequences¶

*3.6.1*Definition of proper divergence¶

Give it. Use it to prove that $(n)$ diverges.

$(x_n)$ tends to infinity if for every $\alpha \in \mathbb R$ there exists $K \in \mathbb N$ such that if $n \geq K$, then $x_n \geq \alpha$. By the Archimedean property, $(n)$ diverges.

*4*Limits¶

*4.1*Limits of functions¶

*4.1.1*The epsilon-delta definition of limit¶

Give it

The function $f:A \to \mathbb R$ has a limit $L$ at the cluster point $c$ if, for every $\epsilon > 0$, there exists $\delta > 0$ such that for all $x$ satisfying $0 < |x-c| < \delta$, we have $|f(x) - L| < \epsilon$.

*4.1.2*The sequential criterion¶

State and prove

TFAE:

(i) $\displaystyle \lim_{x \to c} f = L$

(ii) For every sequence $(x_n)$ in $A$ that converges to $c$ (with $x_n \neq c$), then the sequence $(f(x_n))$ also converges to $L$.

Proof: (→) it involves $\delta$ and $\epsilon$ and $K$ (the definitions). ← contrapositive, look at neighbourhoods.

*4.1.3*Divergence critera¶

State

- If there exists a sequence where $x_n \neq c$ but the sequence converges to $c$, and $(f(x_n))$ does not converge to $L$, then $f$ does not converge to $L$ at $c$
- If the sequence $(f(x_n))$ does not converge at all at $c$, neither does $f$ at $c$

*4.2*Limit theorems¶

Nah

*4.3*Some extensions of the limit concept¶

Nope

*5*Continuous functions¶

*5.1*Continuous functions¶

*5.1.1*The epsilon-delta definition of continuity¶

Give it

The function $f: \to \mathbb R$ is continuous at the cluster point $c$ if, for every $\epsilon> 0$, there exists $\delta > 0$ such that for all $x$ satisfying $0 < |x-c| < \delta$, we have $f(x) - f(c)| < \epsilon$.

If $c$ is a cluster point, then the limit at $c$ must be equal to $f(c)$ (must be defined).

*5.2*Combinations of continuous functions¶

eh