Maintainer: admin

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


1.1Sets and functions

1.2Mathematical induction

1.2.1Proof by induction

Prove something by induction solution


2The real numbers

2.1The algebraic and order properties of R

2.1.1Proving that a square root is irrational

$\sqrt{a}$ 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.2The arithmetic-geometric mean inequality

Prove it solution

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

2.1.3Bernoulli's inequality

Prove it solution

By induction. Easy.

2.2Absolute value and the real line

2.2.1Finding an upper bound over an interval

Find a constant $M$ such that $|f(x)| \leq M$ for all $x$ in that interval. 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.3The completeness property of R

2.3.1Finding the supremum of a set

Given a set, find its sup or inf. solution

2.4Applications of the supremum property

2.4.1The Archimedean property

State and prove it. Using this property, show that the inf of $\{1/n\}$ is 0. 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.2The existence of irrationals

Prove that $\sqrt{a}$ exists in $\mathbb R$. 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.3The density theorem

State and prove the density theorem for rationals and irrationals. 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.4The uncountability of R

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

Cantor's diagonal argument

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

3Sequences and series

3.1Sequences and their limits

3.1.1Uniqueness 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.2Finding 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.3Disproving convergence

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

3.2Limit theorems

3.2.1Convergent sequences are bounded

prove this 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$ 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.2Squeeze theorem

State and prove it. 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.3The 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.3Monotone sequences

3.3.1The monotone convergence theorem

State and prove it. 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.2Proving 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. 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.3Calculating 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.4Subsequences and the Bolzano-Weierstrass theorem

3.4.1Criteria for divergent subsequences

State and prove the equivalency


(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.2Monotone 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.3The 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.5The Cauchy criterion

3.5.1Cauchy 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.2Convergence 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.6Properly divergent sequences

3.6.1Definition 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.1Limits of functions

4.1.1The 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.2The sequential criterion

State and prove


(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.3Divergence critera


  • 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.2Limit theorems


4.3Some extensions of the limit concept


5Continuous functions

5.1Continuous functions

5.1.1The 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.2Combinations of continuous functions