\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
