1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
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
|
