\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