\documentclass[12pt]{article}
\usepackage{fullpage,mathpazo,amsfonts,nicefrac}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\begin{document}
\section*{Math 104: Homework 1 solutions}
\begin{enumerate}
\item The basis for induction, $P_1$, is true, since $1^3=1^2$. Now consider
the induction step, assuming $P_n$ is true and examining $P_{n+1}$. By
making use of the result $(1+2+\ldots+n) = n(n+1)/2$ that is given as an
example result in Section~1, we see that
\begin{eqnarray*}
1^3 + 2^3 + \ldots n^3 + (n+1)^3 &=& (1^3 + 2^3 + \ldots n^3) + (n+1)^3 \\
&=& (1+2+ \ldots + n)^2 + (n+1)^3 \\
&=& \left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3 \\
&=& \frac{n^2(n+1)^2}{4} + (n+1)^3 \\
&=& \frac{(n+1)^2}{4} \left( n^2 + 4n+4 \right) \\
&=& \frac{(n+1)^2(n+2)^2}{4} \\
&=& (1+2+\ldots + n + (n+1))^2,
\end{eqnarray*}
and thus $P_{n+1}$ is satisfied. Hence, by the principle of mathematical
induction, $P_n$ is true for all $n\in \N$.
\item
\begin{enumerate}
\item For this exercise, $P_2$ is treated as the basis for induction. We
see that $2^2 = 4 > 2+1=3$, so $P_2$ is true. Now consider the
induction step, assuming $P_n$ is true and examining $P_{n+1}$:
\[
(n+1)^2 = n^2+2n+1 >(n+1)+ 2n+1 > (n+1) +1.
\]
Hence if $P_n$ holds then $P_{n+1}$ holds. By the principle of
mathematical induction, $P_n$ is true for all $n\in \N$ with $n \ge 2$.
\item Here, $P_4$ is treated as the basis for induction. We see that $4!
= 24 > 4^2=16$ so $P_4$ is true. Now consider the induction step,
assuming $P_n$ is true and examining $P_{n+1}$:
\[
(n+1)! = n! (n+1) > n^2 (n+1).
\]
Now, apply the result from (a), which is true for $n>2$ and thus valid
for all cases under consideration:
\[
(n+1)! = n^2 (n+1) > (n+1)(n+1) = (n+1)^2.
\]
Hence if $P_n$ holds then $P_{n+1}$ holds. By the principle of
mathematical induction, $P_n$ is true for all $n\in \N$ with $n \ge 4$.
\end{enumerate}
\item
\begin{enumerate}
\item The golden ratio satisfies the relation
\[
\varphi^2 = \frac{(1+\sqrt{5})^2}{4} = \frac{6+2\sqrt{5}}{4} = 1 + \frac{1+\sqrt{5}}{2} = 1 + \varphi.
\]
\item First consider the induction hypothesis $H_1$:
\[
f(0)= \frac{\varphi^0 - (1-\varphi)^0}{\sqrt{5}} = 0, \qquad f(1) = \frac{\varphi- (1-\varphi)}{\sqrt{5}} = \frac{2\varphi-1}{\sqrt{5}} = 1,
\]
and hence $H_1$ is true. Now consider the induction step. Suppose $H_n$
is true, and consider $H_{n+1}$. Then $F_n=f(n)$ and
\begin{eqnarray*}
F_{n+1} &=& F_n+F_{n-1} \\
&=& \frac{\varphi^n - (1-\varphi)^n + \varphi^{n-1} - (1-\varphi)^{n-1}}{\sqrt{5}} \\
&=& \frac{\varphi^{n-1}(1+\varphi) - (1-\varphi)^{n-1} ( 1+ (1-\varphi))}{\sqrt{5}} \\
&=& \frac{\varphi^{n-1}(\varphi^2) - (1-\varphi)^{n-1} ( 2-\varphi))}{\sqrt{5}}.
\end{eqnarray*}
Since $(1-\varphi)^2 = 1-2\varphi+\varphi^2 = 1-2\varphi+(1+\varphi) = 2-\varphi$, it follows
that
\begin{eqnarray*}
F_{n+1} &=& \frac{\varphi^{n-1}\varphi^2 - (1-\varphi)^{n-1}(1-\varphi)^2}{\sqrt{5}} \\
&=& \frac{\varphi^{n+1} - (1-\varphi)^{n+1}}{\sqrt{5}} \\
&=& f(n+1)
\end{eqnarray*}
so $H_{n+1}$ is true. Hence by mathematical induction $H_n$ is true for
all $n$, so $F_n=f(n)$ for all $n \in \N \cup \{0\}$.
\end{enumerate}
\item To begin, search for a polynomial that is satisfied by
$x=(5-\sqrt{3})^{1/3}$:
\begin{eqnarray*}
x^3 &=& 5-\sqrt{3} \\
x^3 - 5 &=& -\sqrt{3} \\
(x^3-5)^2 &=& 3 \\
x^6 - 10x^3 + 22 &=& 0.
\end{eqnarray*}
Now suppose that $x$ is rational, so that it can be written as $x=p/q$
where $p,q \in \Z$ and $q \ne 0$ with $p$ and $q$ coprime. Then by the
rational zeroes theorem, $p$ divides $22$ and $q$ divides $1$. Hence the
only possible solutions are $\pm 1$, $\pm 2$, $\pm 11$, and $\pm 22$.
The table below shows that none of these values satisfy the equation.
\begin{center}
\begin{tabular}{c|c|c|c|c}
$x$ & 1 & 2 & 11 & 22 \\
\hline
$x^6-10x^3+22$ & 13 & 6 & 1,758,273 & 113,273,446 \\
$(-x)^6-10(-x)^3+22$ & 33 & 166 & 1,784,893 & 113,486,406 \\
\end{tabular}
\end{center}
\item To begin, we find a polynomial that is satisfied by $x=\sqrt{2} +
\sqrt{3}$:
\begin{eqnarray*}
x^2 &=& (\sqrt{2}+\sqrt{3})^2 \\
x^2 &=& 5+ 2\sqrt{2}\sqrt{3} \\
(x^2-5) &=& 2\sqrt{2}\sqrt{3} \\
(x^2-5)^2 &=& 24 \\
x^4-10x^2 + 25 &=& 24 \\
x^4-10x^2 + 1 &=& 0.
\end{eqnarray*}
By the application of the rational zeroes theorem, if $x=p/q$ with $p$ and
$q$ coprime, then $p$ divides 1 and $q$ divides 1. Hence the only possible
rational solutions to this polynomial are $\pm 1$. However
\begin{eqnarray*}
(1)^4 - 10(1)^2 + 1 &=& -8 \ne 0 \\
(-1)^4 - 10 (-1)^2 +1 &=& -8 \ne 0
\end{eqnarray*}
and since neither possibility satisfies the equation, $\sqrt{2} + \sqrt{3}$
is irrational.
\item
\begin{enumerate}
\item For $a,b,c\in \N$, associativity (A1) and commutativity (A2) hold,
so that $(a+b)+c = a+(b+c)$, and $a+b=b+a$. A3 is violated, since
$\N$ does not contain the additive identity element $0$. A4 is violated,
since for all $a\in \N$, $-a\notin \N$. Multiplication is also associative
and commutative so M1 and M2 hold. The multiplicative inverse $1$ is in $\N$
so M3 holds. M4 does not hold since all elements other than 1 do not
have multiplicative inverses.
The DL property is satisfied. Likewise, since $\N$ is a subset of $\R$,
all of the ordering axioms O1--O5 are immediately satisfied.
\item Many of the same arguments can be made for $\Z$. The only change is
that the set contains the additive identity and the additive inverses,
so that A3 and A4 are satisfied. M4 still remains invalid.
\end{enumerate}
\item We start by considering the statement $0<1$. Suppose that this was untrue,
so that $1 \le 0$. Then by applying axiom O4, we know that
\begin{eqnarray*}
1 + (-1) &\le& 0 + (-1) \\
0 &\le& -1
\end{eqnarray*}
Now, apply axiom O5, using $a=0$, $b=-1$, and $c=-1$ to show that $0 \le
(-1)\cdot(-1)$. Then by making use of Theorem~3.1(iv), we know that
\[
0 \le 1 \cdot 1 = 1
\]
But now $0 \le 1$ and $0 \ge 1$, so by axiom O2, $0=1$. Since zero and one
are distinct elements, this is a contradiction, and thus $0<1$.
Why is $0 \ne 1$? In the textbook's treatment, the rational numbers $\Q$
are assumed to exist and then the axioms A1--A4, M1--M4, and DL are
subsequently introduced to create the field structure. If the numbers $0$
and $1$ are constructed {\it a~priori} as elements of $\Q$ then it is safe
to assume that they are distinct objects. In other presentations of the
field axioms, which describe them in the abstract and not in relation to an
already given set, it is assumed that the additive and multiplicative
inverses are unique, which would immediately disallow $0=1$. Regardless, it
is clear that $0=1$ leads to catastrophic problems: using Theorem~3.1(i),
we would see that for any element $a$,
\[
a = a\cdot 1 = a\cdot 0 = 0
\]
implying that all elements are zero.
We now wish to show that for all non-zero $a,b\in \R$, $0<a<b$ implies
$0<b^{-1} < a^{-1}$. By the transitivity axiom O3, we know that $0\le a$
and $a \le b$ implies that $0\le b$, and since $b$ is non-zero, $0<b$. Thus
by Theorem 3.2(vi), $0<b^{-1}$.
Now suppose that $b^{-1} \ge a^{-1}$. Since $b>0$, axiom O5 can be applied
to show that
\begin{eqnarray*}
b \cdot b^{-1} &\ge& b \cdot a^{-1} \\
1 &\ge& b \cdot a^{-1},
\end{eqnarray*}
and since $a>0$, axiom O5 can be applied to show that
\begin{eqnarray*}
a \cdot 1 &\ge& a \cdot b \cdot a^{-1} \\
a &\ge& b.
\end{eqnarray*}
This is a contradiction, and hence $b^{-1} < a^{-1}$. Thus
$0<b^{-1}<a^{-1}$.
\item
\begin{enumerate}
\item First suppose that $-a\le b \le a$. Then either $|b|=b$ in which case
$|b|\le a$, or $|b|=-b$ in which case $-|b| \ge -a$ and thus $|b| \le a$.
Thus, $|b| \le a$ in all cases.
Now suppose that $|b| \le a$. Since $|b|\ge 0$ for all $b$, it follows
that $a\ge 0$ by transitivity. If $b \ge 0$, then $|b| = b$ and hence
$b\le a$. In addition $b \ge 0 \ge -a$, and hence $-a \le b \le a$. If
$b \le 0$, then $|b| = -b$, and hence $-b \le a$, so $-a \le b$. In
addition, $b \le 0 \le a$, and thus $b \le a$ also. Thus $-a \le b
\le a$ in all cases.
\item The triangle inequality states that for all $c,d\in \R$,
\[
|c| + |d| \le |c+d|.
\]
For any two numbers $a,b\in \R$, substituting $c=a-b$ and $d=b$ into the
triangle inequality gives
\begin{eqnarray*}
|a-b| + |b| &\ge& | a - b + b| \\
|a-b| &\ge& |a| - |b|.
\end{eqnarray*}
Similarly, a substitution of $c=a$ and $d=b-a$ gives
\begin{eqnarray*}
|a| + |b-a| &\ge& | a + b -a | \\
|b-a| &\ge& |b| - |a|.
\end{eqnarray*}
Applying Theorem~3.2(i) to this expression gives $-|b-a| \le |a| - |b|$.
Also, $|b-a| = |a-b|$, and hence
\begin{equation}
-|a-b| \le |a| - |b| \le |a-b|. \label{eq:tmod}
\end{equation}
By using the result from part (a), it follows that
\[
\left| |a| - |b| \right| \le |a-b|.
\]
\end{enumerate}
\end{enumerate}
\end{document}