From 8dafd8aec819e85fd36cbd1d6231aad24e62c31b Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Tue, 16 Aug 2022 18:21:57 -0400 Subject: Finished work from last semester --- howard/hw9.tex | 144 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) create mode 100644 howard/hw9.tex (limited to 'howard/hw9.tex') 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 -- cgit