1 files changed, 144 insertions, 0 deletions
diff --git a/howard/hw9.tex b/howard/hw9.tex
new file mode 100644
index 0000000..eec9dd4
--- /dev/null
+++ b/howard/hw9.tex
@@ -0,0 +1,144 @@
+\newfam\bbold
+\def\bb#1{{\fam\bbold #1}}
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+
+\newcount\indentlevel
+\newcount\itno
+\def\reset{\itno=1}\reset
+\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
+\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
+\aftergroup\afterstartlist}
+\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
+    i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
+    s\or t\or u\or v\or w\or x\or y\or z\fi}
+\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
+                                  \alph\itno)\else
+                                  (\number\itno)\fi
+                           }%
+         #1\smallskip\advance\itno by 1\relax}
+\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}}
+\let\endul\egroup
+\def\hline{\noalign{\hrule}}
+\let\impl\rightarrow
+\newskip\tableskip
+\tableskip=10pt plus 10pt
+\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt
+depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}}
+\def\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+
+\li Use strong induction to show that the square root of 18 is
+irrational. You must use strong induction to receive credit on this
+problem.
+
+Let $P(n)$ be the proposition that $\sqrt{18} \neq {n\over b}$ for all
+natural numbers $b$ (note: we can assume $b>0$ because $\sqrt{18} > 0$)
+We will $P(n)$ for all nonnegative $n.$
+We will thus conclude that $\sqrt{18}$ is irrational.
+
+We start with the base case $P(0)$ that $\sqrt{18} \neq {0\over b}$ for
+any natural number $b$ (this is clear because $\sqrt{18} \neq 0$).
+
+We now assume for the sake of induction that for all $0\leq j\leq k,$
+for some $k\geq 0,$ $P(j).$
+We will show $P(k+1),$ that $\sqrt{18} \neq {k+1\over b}$ for any
+natural number $b.$
+We assume for the sake of contradiction that $\sqrt{18} = {k+1\over c}$
+where $c\in\bb N.$
+Rearranging,
+$$18c^2 = (k+1)^2.$$
+$(k+1)^2=2(9c^2),$ and $9c^2\in\bb Z$ by closure, so $2\mid (k+1)^2,$ so
+$2\mid k+1$ (if the square of an integer is even, that integer is even).
+
+By definition of even, there exists $l\in\bb Z$ such that $2l = k+1.$
+Also, $4l = (k+1)^2.$
+Substituting, $18c^2 = 4l.$
+With algebra, we obtain $9c^2 = 2l.$
+$2\nmid 9,$ and $2\mid 9c^2,$ so we must have $2\mid c^2.$
+Similarly, this implies $2\mid c,$ so there exists $m\in\bb Z$ such that
+$c = 2m.$
+We now have $\sqrt{18} = {2l\over 2m} = {l\over m},$ and
+$0 < l < k+1,$ contradicting $P(l).$
+We have now shown that $P(0),\ldots,P(k)\impl P(k+1).$
+
+By strong induction, we have shown that $\sqrt{18}$ is not equal to any
+nonnegative rational, so $\sqrt{18}$ is irrational.
+
+\li Use strong induction to show that every integer amount of postage 30
+cents or more can be formed using just 6-cent and 7-cent stamps.
+
+We will first show the base case that all values between 30 and 35 cents
+can be formed from 6- and 7-cent stamps by example: $30 = 6(5)$ and $31
+= 6(4) + 7(1)$ and $32 = 6(3) + 7(2)$ and $33 = 6(2) + 7(3)$ and $34 =
+6(1) + 7(4)$ and $35 = 7(5).$
+
+For the sake of induction we assume that for some $k\geq 30,$ all
+postage amounts from $k$ to $k+5$ can be formed, and we show that
+postage amount $k+6$ can be formed.
+By adding a 6-cent stamp to the formulation for $k$ cents, we achieve a
+formula for $k+6$ cent postage.
+We have shown that being able to form postage of sizes $k$ through
+$k+5$ implies we can form postage of $k+6$ cents.
+
+By strong induction, for all $n\geq 30,$ 6- and 7-cent stamps can form
+$n$ cents of postage.
+
+\li Show that if $a_1,a_2,\ldots,a_n$ are $n$ distinct real numbers,
+exactly $n-1$ multiplications are used to compute the product of these
+$n$ numbers no matter how parentheses are inserted into their product.
+
+We first take the base case that the product of $n=1$ numbers can be
+computed with 0 multiplications (the answer is $a_1$)
+
+Then, for the sake of induction, we assume that for some $k\in\bb N,$
+all multiplications of $1\leq j\leq k$ numbers require exactly $j-1$
+multiplications.
+We will show that multiplying $k+1$ numbers requires $k$ multiplications
+regardless of how the numbers are partitioned (how many parentheses are
+inserted).
+To account for any possible arrangement of upper level parentheses, we
+partition our $k+1$ distinct real numbers into $2\leq r\leq k+1$ sets
+$A_1,A_2,\ldots,A_r.$
+This will require $k-r+1$ multiplications to obtain products for each
+partition, in total:
+$$\sum_{i=1}^r |A_i| = k+1 \Rightarrow \sum_{i=1}^r |A_i| = k-r+1.$$
+We then multiply together the $r$ products which we obtain, requiring
+another $r-1$ multiplications, resulting in $k$ total multiplications,
+regardless of the parenthesis placement we chose.
+
+By strong induction, we have now shown that multiplying $n$ numbers
+always requires $n-1$ multiplications regardless of the position of
+parentheses.
+
+\li Suppose you begin with a pile of $n$ stones and split this pile into
+$n$ piles of one stone each by successively splitting a pile of stones
+into two smaller piles. Each time you split a pile you multiply the
+nmuber of stones in each of the two smaller piles you form, so that if
+the piles have $r$ and $s$ stones in them, you compute $rs.$ Show that
+no matter how you split the stones, the sum of the products compared at
+each step equals $n(n-1)/2.$
+
+We will first show the base case of breaking a pile of 2 stones.
+This pile must be broken into piles of one stone and one stone.
+The product would then be $1 = {n(n-1)\over 2} = {2(2-1)\over 2}.$
+
+We will now assume for the sake of induction that this proposition is
+true for all piles of $j\leq k$ stones where $k\geq 1,$ and we will show
+that this proposition is true for a pile of $k+1$ stones.
+This pile can be broken into a piles of sizes $r$ and $k-r+1,$ where
+$1\leq r\leq k.$
+The sum for each of these piles and the new product is
+$$r(k-r+1)+{r(r-1)\over 2}+{(k-r+1)(k-r)\over 2} =$$$$
+{2rk-2r^2+2r+r^2-r+k^2+r^2-2kr+k-r\over 2} =
+{k^2+k\over2} = {(k+1)k\over 2}.$$
+We have now shown that, assuming all smaller sums for $j$ piles are
+${j(j-1)\over 2},$ $k+1$ stones build the sum ${(k+1)k\over 2}.$
+
+By strong induction, we have shown that for all piles of $n$ stones,
+this process yields a sum ${n(n-1)\over 2}.$
+
+\bye