HTSEFP
How to solve every problem. Will draw on examples from past finals, the 3 in-class tests, and assignments.
1Preliminaries¶
1.1Sets and functions¶
1.2Mathematical induction¶
1.2.1Proof by induction¶
Prove something by induction
1.2.1.1General solution¶
Easy
1.2.1.2Examples¶
2The real numbers¶
2.1The algebraic and order properties of R¶
2.1.1Proving that a square root is irrational¶
$\sqrt{a}$
2.1.1.1General 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
2.1.2.1General solution¶
Use the fact that $(\sqrt{a} - \sqrt{b})^2 > 0$. Multiply that out, move things around.
2.1.3Bernoulli's inequality¶
Prove it
2.1.3.1General 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.
2.2.1.1General 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.
2.3.1.1General 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.
2.4.1.1General 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$.
2.4.2.1General 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.
2.4.3.1General 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.
2.4.4.1General 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
3.2.1.1General 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.2The 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.
3.2.2.1General 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.
3.3.1.1General 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.
3.3.2.1General 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
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.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.
4Limits¶
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
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.3Divergence 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.2Limit theorems¶
Nah
4.3Some extensions of the limit concept¶
Nope
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¶
eh