$$ \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\EE}{\mathbb{E}} \newcommand{\HH}{\mathbb{H}} \newcommand{\FF}{\mathbb{F}} \newcommand{\SO}{\operatorname{SO}} \newcommand{\dist}{\operatorname{dist}} \newcommand{\length}{\operatorname{length}} \newcommand{\uppersum}[1]{{\textstyle\sum^+_{#1}}} \newcommand{\lowersum}[1]{{\textstyle\sum^-_{#1}}} \newcommand{\upperint}[1]{{\textstyle\smallint^+_{#1}}} \newcommand{\lowerint}[1]{{\textstyle\smallint^-_{#1}}} \newcommand{\rsum}[1]{{\textstyle\sum_{#1}}} \newcommand{\partitions}[1]{\mathcal{P}_{#1}} \newcommand{\erf}{\operatorname{erf}} \newcommand{\ihat}{\hat{\imath}} \newcommand{\jhat}{\hat{\jmath}} \newcommand{\khat}{\hat{k}} \newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}} \newcommand{\smat}[1]{\left(\begin{smallmatrix}#1\end{smallmatrix}\right)} $$

Assignment 2

This assignment accompanies our rigorous investigation of analysis, and we focus on building up known and useful facts from algebra / precalculus directly from our concise axiom system. Throughout this assignment you are allowed to use the axioms, definitions and shorthand notations we have developed, as well as the theorems proven directly from them in class:

From the Field Axioms

For any $x$ in a field $0x=0$.
If $a,b$ are elements of a field and $ab=0$ then $a=0$ or $b=0$.
For any $x$ in a field, $-x=(-1)x$.
$-(-1)=1$ and $-(-x)=x$.

From the Order Axioms

In any ordered field $1>0$.
If $x$ is any nonzero element of an ordered field then $x^2>0$.
If $a<b$ and $b<c$ in an ordered field, then $a<c$.
If $a<b$ and $c>0$ then $ca<cb$. If $c<0$ instead we have $cb< ca$.
If $0< a < b$ in an ordered field, then $a^2< b^2$.

Arithmetic

Exercise 1 (Multiplying it Out) Let $a,b$ be elements of a field. Prove the familiar “foiling identities” of elementary algebra: \[(a+b)^2=a^2+2ab+b^2\] \[(a+b)(a-b)=a^2-b^2\]

Solution. Both cases use very similar logic, so we just do the second. Beginning with the expression $(a+b)(a-b)$, and can use the distributive property of multiplication to distribute terms. \[\begin{align*} (a+b)(a-b) &= (a+b)a + (a+b)(-b) \\ &= aa + ba + a(-b) + b(-b) \end{align*}\] Note that the symbol $-b$ denotes the additive inverse of $b$, so $b + (-b) = 0$. Note also that since 0 is the additive identity, $c\cdot 0 = 0$ for all $c \in \mathbb{F}$. We can use these facts by noting that multiplication is commutative, and factoring out $a$ from this middle two terms: \[\begin{align*} aa + ba + a(-b) + b(-b) &= aa + ab + a(-b) + b(-b) \\ &= aa + a(b - b) + b(-b) \\ &= aa + a(0) + b(-b)\\ &= aa + 0 + b(-b)\\ &= aa + b(-b) \end{align*}\] From a proof proved in the notes, we know that $-x = (-1)x$ for any $x \in \mathbb{F}$. We can use this in combination with the definition $x^2 = xx$ and the multiplication operators commutativity to simplify: \[\begin{align*} aa + b(-b) &= aa + b(-1)(b) \\ &= aa + (-1)bb\\ &= a^2 + (-1)b^2\\ &= a^2 - b^2 \end{align*}\]

Exercise 2 (Fractions) Let $b,d\neq 0$, and prove the following laws of fraction arithmetic:

Getting a common denominator \[\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}\]
Dividing by a fraction is multiplying by the reciprocal \[\frac{a/b}{c/d}=\frac{a}{b}\frac{d}{c}\]

(For the second, you may wish to first prove that $(x^{-1})^{-1}=x$ for $x$ a nonzero element of a field).

Solution (Part I). We can rewrite $\frac{a}{b} = ab^{-1}$ and $\frac{c}{d} = cd^{-1}$ (by the definition of the fraction bar as a short hand for multiplying by the inverse) so
\[ \frac{a}{b} + \frac{c}{d} = ab^{-1} + cd^{-1}. \]

Similarly, we can rewrite the other side without this shorthand as \[ \frac{ad + bc}{bd} = (ad + bc)(b^{-1}d^{-1}) \]

Thus, our goal is to prove the equality of $ab^{-1} + cd^{-1}$ and $(ad + bc)(b^{-1}d^{-1})$ as elements of $\FF$. Our strategy will be to start with this latter term and reduce it by field operations to the former. Distributing the element $(b^{-1}d^{-1})$ gives

\[(ad + bc)(b^{-1}d^{-1})= (ad)(b^{-1}d^{-1})+bc(b^{-1}d^{-1})\]

Taking the first term of this sum and re-arranging using commutativity and associativity of multiplication

\[ (ad)(b^{-1}d^{-1}) = (ad)(d^{-1}b^{-1})= a(d d^{-1})b^{-1}\]

Then using the definition of $d^{-1}$ as the multiplicative inverse of $d$ and $1$ as the multiplicative identity we see

\[a(d d^{-1})b^{-1}=a\cdot 1 \cdot b^{-1}=a b^{-1}\]

An analogous computation run on the second term $bc(b^{-1}d^{-1})$ reveals

\[bc(b^{-1}d^{-1}) = cb(b^{-1}d^{-1})=c(bb^{-1})d^{-1}=c\cdot 1\cdot d^{-1}=cd^{-1}\]

Adding these two back together shows

\[(ad)(b^{-1}d^{-1})+bc(b^{-1}d^{-1}) = a b^{-1}+cd^{-1}\]

Which is exactly what we wanted.

Solution (Part II). We start by proving that $(x^{-1})^{-1}=x$ for any nonzero $x\in\FF$ by showing it satisfies the definition. The multiplicative inverse of $x^{-1}$ is the field element $y$ such that $y(x^{-1})=1$. But the definition of $x^{-1}$ itself says that $x$ satisfies this! So $x$ is the multiplicative inverse of $x^{-1}$, or $x=(x^{-1})^{-1}$ in our notational shorthand.

It will also be useful to note (as a lemma) that the multiplicative inverse of $xy$ is $x^{-1}y^{-1}$, as using commutativitiy and associativity \[xy(x^{-1}y^{-1})=yxx^{-1}y^{-1}=y\cdot 1\cdot y^{-1}=yy^{-1}=1\]

Now we are ready to begin the main proof. We start with unpacking the shorthand of the left side, and show through field operations it equals the right.

\[\frac{a/b}{c/d}= (a/b)(c/d)^{-1}=(ab^{-1})(cd^{-1})^{-1}\]

Using our lemma we can distribute the inverse in the second term to give $c^{-1}(d^{-1})^{-1}$, and then then lemma above that ensures the second factor here is just $d$. Thus we have

\[(ab^{-1})(cd^{-1})^{-1} = (ab^{-1})(c^{-1}d)\]

Which is exactly what we were after.

Exercise 3 Let $r\neq 1$ be an element of a field. Prove by induction that \[1+r+r^2+r^3+\cdots +r^n = \frac{1-r^{n+1}}{1-r}\]

Hint: multiply both sides by $1-r$

Solution. Following the hint, we multiply through by $1-r$ to get an equivalent expression we may hope to prove. \[(1-r)(1+r+r^2+r^3\cdots + r^n)=1-r^{n+1}\]

We will proceed by induction, and show that for each $n$ the left side simplifies to the right side. For $n=1$ the left side product is $(1-r)(1+r)$ which multiplies out by our previous homework exercise to $1-r^2$: thus the base case is proven. For the inductive step, assume that we know for some $n$ that $(1-r)(1+r+r^2+r^3\cdots + r^n)=1-r^{n+1}$, and consider the product

\[(1-r)(1+r+r^2+r^3\cdots + r^n+r^{n+1})\]

We may use the distributive law to distribute $(1-r)$ across the two terms $1+r+\cdots + r^n$ and $r^{n+1}$, giving

\[(1-r)(1+r+\cdots+r^n)+(1-r)r^{n+1}\]

Our inductive hypothesis tells us that the first term here is precisely $1-r^{n+1}$! So, substituting that in

\[=(1-r^{n+1})+(1-r)r^{n+1}\]

Continuing to simplify, we distribute $r^{n+1}$ across $(1-r)$ and simplify:

\[1-r^{n+1}+r^{n+1}-rr^{n+1}=1-0+r^{n+2}=1-r^{n+2}\]

This is precisely what we were hoping to prove, so our induction is done and the result holds for all $n$.

Inequality

Exercise 4 (Powers Inequalities) Recall that natural number powers are a shorthand for repeated multiplication $x^n=x\cdot x\cdots x$ and for a positive $x$ we define the $n^{th}$ root $y=x^{1/n}$ to be a positive element of the field such that $y^n=x$, if such a $y$ exists, and we define $x^{p/q}=(x^p)^{1/q}$ when $x^p$ has a $q^{th}$ root.

Let $a,b$ be two positive elements of an ordered field and assume that $a<b$. Prove that

$a^n<b^n$ for all $n\in\NN$
$a^{1/n}< b^{1/n}$ (if their $n$th roots exist)
$a^r<b^r$ for $r=p/q$ any positive rational number (assuming $a^r$ and $b^r$ exist).

Solution (Part I). Assume $a, b \in \mathbb{F}$, $a > 0$, $b > 0$, and $a < b$. We will prove by induction. Base Case: $n = 1$. This is just our assumption! So, we move onto the Inductive Step. Here we assume for some $n\in\NN$ we already know $a^n<b^n$, and try to prove the corresponding statement for the $n+1^{st}$ power. Since $a>0$ we can multiply our inequality through by $a$ to get $a\cdot a^n<a\cdot b^n$. But also we can multiply our starting assumption through by $b^n$ (which is positive, since $b>0$, by closure) to get $b^n \cdot a <b^n \cdot b$. By commutativity of multiplication and transitivity of inequality, we can string these together to \[a\cdot a^n< a\cdot b^n <b\cdot b^n\]

But $a\cdot a^n = a^{n+1}$ by definition, and similarly for $b\cdot b^n$. Thus we’ve proven $a^{n+1}<b^{n+1}$ as required to complete the induction, so the result holds for all $n\in\NN$.

Solution (Part II). Assume for the sake of contradiction that this is false, so there exists some positive $a,b$ with $a<b$ but yet their $n$th roots exist in $\FF$ and $a^{1/n}\geq b^{1/n}$. We separate out two cases: first, if $a^{1/n}>b^{1/n}$ is strictly greater, since $n^{th}$ roots are by definition positive, we are all set to apply part I of this problem and conclude that after raising to the $n^{th}$ power we have \[\left(a^{1/n}\right)^n>\left(b^{1/n}\right)^n\] But the definition of the $n^{th}$ root of $x$ is precisely the number such that raising to the $n^{th}$ power returns $x$. Thus this inequality says $a>b$, contradicting what we know to start.

A similar problem occurs if we assume equality: then raising to the $n^{th}$ power gives (again, by definition of the $n^{th}$ root) that $a=b$, contradicting that we know $a<b$.

Solution (Part III). If $r$ is a positive rational number we can represent $r$ as a fraction $r=p/q$ for $p> 0$ and $q>0$. (Note we could also represent it as a quotient of two negative numbers). Since rational powers are defined as $a^{p/q}=(a^p)^{1/q}$, we apply Parts I and II in succession. Given any positive $a<b$ Part I ensures that $a^p<b^p$, and now since these are both still positive, part II implies that $(a^p)^{1/q}<(b^p)^{1/q}$, which is precisely what we want: $a^r<b^r$.

Exercise 5 (Exponentials and Factorials) Given an natural number $c$, the is the function $c^n = c\cdot c\cdot c\ldots c$. The factorial $n!$ is defined as $n!=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1$.

Prove that the factorial function $f(n)=n!$ is eventually larger than the exponential function $e(n)=10^n$. That is, show there is some $N$ where for all larger $n>N$ we have $n!>10^n$.

Hint: find a good base case, then use induction!

Solution. We prove this by induction. But note that we are not trying to prove the statement for all $n$, but rather just that its eventually always true for large enough $n$. This is good because of course its false for small $n$: $10^2=100$ but $2!=2$, and 2 is certainly not greater than 100. So there’s some work to be done in selecting the right base case: we need to find an $n$ where it actually is true! (Note also we’re just asked to prove that it holds for large enough n so we don’t need to be super careful and have base case being the first time its true or anything.)

Let’s take the base case be $n = 25$; we have $25! = 15,511,210,043,330,985,984,000,000$ and $10^{25} = 10,000,000,000,000,000,000,000,000$, so $25! > 10^{25}$. Given this base case, the induction is actually pretty straightforward. Let’s assume that $n! > 10^n$. Now taking a look at the $(n+1)^{th}$ case, we have $(n+1)! = (n+1) \cdot n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 = (n+1) \cdot n!$. On the RHS, we have $10^{n+1} = 10^n \cdot 10$. Now because the base case is $n=25$ we know $n+1$ is greater than 10 (its actually 26 or more!) so since $n!>10^n$ we see that $(n+1)n!>(n+1)10^n$ and $(n+1)10^n>10\cdot 10^n$. Stringing these together gives $(n+1)n!>10\cdot 10^n$, or $(n+1)!>10^{n+1}$ as required.

Exercise 6 (Bernoulli’s inequality) Prove the following inequality for any positive $x$ and positive integer $n$: \[(1+x)^n\geq 1+nx\] This will be useful to us in studying exponentials, powers, and limits later on in the course! Hint: induction!

Solution. For the base case we just plug in $n=1$ \[\begin{align*} (1+x)^1 & \geq 1+(1)x \\ 1+x & \stackrel{\checkmark}{\geq} 1+x \end{align*}\] This is true because they’re just equal! Then the inductive hypothesis is as follows: we assume \[ (1+x)^n\geq 1+nx \]

holds for some $n\in\NN$. Since $1+x$ is a positive number, we can mutltiply the inductive hypothesis by this to get

\[(1+x)(1+x)^n \geq (1+x)(1+nx) \]

The left side is $(1+x)^{n+1}$ by definition. Multiplying out the right, gives $1+nx+x+xnx=1+(n+1)x+nx^2$, so we have \[(1+x)^{n+1} \geq 1+(n+1)x+nx^2\]

And finally, since $n\in\NN$ is positive and $x^2$ is positive (its a square), we know $nx^2$ is positive and

\[1+(n+1)x+nx^2> 1+(n+1)x\]

(You can get this by starting from $nx^2>0$ and adding $1+(n+1)x$ to both sides). Now by the transitivity of inequality we may string these together and conclude

\[(1+x)^{n+1} > 1+(n+1)x\]

Thus our proof actually concludes that for $n=1$ the two are equal and for all $n>1$ we have a strict inequality! In any case, this implies the weaker statement we were after, that for all $n$, $(1+x)^{n+1}\geq 1+nx$.

Exercise 7 (The Inequality $|x-a|<\epsilon$) Let $a,x$ be arbitrary elements of an ordered field and $\epsilon$ a positive element. Show that $|x-a|<\epsilon$ is true if and only if $a-\epsilon < x < a+\epsilon$

Solution.

Exercise 8 (Reverse Triangle Inequality) Prove that for $a,b$ in an ordered field, \[\left||a|-|b|\right|\leq |a-b|\]

Solution. By the triangle inequality, we have \[|x|=|(x-y)+y|\leq |x-y| + |y| \] Simplifying and subtracting $|y|$ from both sides gives \[ |x|-|y| \leq |x-y|\] We can run a similar calculation: \[|y|=|(x-y)-x| \leq |x-y| + |-x| = |x-y| + |x| \] After moving some terms around with algebra yields \[ -|x-y| \leq |x| - |y|\] Thus we have two inequalities involving $|x|-|y|$: \[-|x-y| \leq |x| - |y| \leq |x - y| \] But $-a< x < a$ is equivalent to $|x|<a$ by the previous problem! So we have \[||x|-|y|| \leq |x - y|\]