-
Notifications
You must be signed in to change notification settings - Fork 2
/
appendix-induction.tex
277 lines (202 loc) · 8.31 KB
/
appendix-induction.tex
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
\subsection{Mathematical Induction Review}
\label{app:induction}
Mathematical induction is a very powerful tool for proving results. It allows us to prove generalized results.
Its shortcoming is that you already have to suspect what the solution is. It then allows you to prove it.
\begin{definition}[The Principle of Mathematical Induction]
Assume that ${\bf P}(1)$, ${\bf P}(2)$, ${\bf P}(3), \ldots$ is an infinite sequence of mathematical statements. \\
\begin{tabular}{ll|ll}
{\bf If} & & {\bf If} \\
& (a) \quad ${\bf P}(1)$ is true, & & first domino falls \\
& {\bf and} & & {\bf and} \\
& (b) \quad for any $k$, ${\bf P}(k)$ implies ${\bf P}(k+1)$
& & if a domino falls, then the next one falls \\
{\bf then} & & & {\bf then} \\
& all the statements in the sequence are true & & all dominoes fall!
\end{tabular}
\end{definition}
\begin{example}
For any $n\in \N$, $1+3+5+\cdots+(2n-1) = n^2$. \\
Let us prove this formula using Mathematical Induction.
\paragraph{Proof.}
If $n=1$, we get $1=1^2$, which is true -- ${\bf P}(1)$ holds.
Assume that $1+3+5+\cdots+(2k-1) = k^2$ for some $k$.
Then
\begin{align*}
1+3+5+\cdots+\big(2(k+1)-1\big)
& = \underbrace{1+3+5+\cdots+(2k-1)}_{= k^2 \text{ by induction hypothesis}} + (2k+1) \\
& = k^2+(2k+1)\\
& = k^2 + 2k + 1\\
& = (k+1)^2.
\end{align*}
By induction, the equality holds for all $n\in \N$.
\end{example}
\begin{example}
For any $x\in \R$ with $x\geq -1$ and $n \in \N$, then $(1+x)^n \geq 1+nx$. \hfill (Bernoulli's Inequality)
\paragraph{Proof.}
For $n=1$, $1+x\geq 1+x$, which is true!
Assume that $(1+x)^k \geq 1+kx$. Then
\begin{align*}
(1+x)^{k+1}
& = (1+x)^k (1+x)
\geq (1+kx)(1+x) \\
& = 1 + x + kx^2 + kx
= 1+(k+1)x+kx^2 \\
& \geq 1+(k+1)x.
\end{align*}
By induction, the claim holds for all $n \in \N$.
\begin{graybox}
In the proof, we didn't use the fact that $x\geq -1$, but
for $n=3$ and $x=-4$, $(1+x)^n = -27 \not\geq -11 = 1+nx$. \\
Where did we use the hypothesis $x\geq -1$?
\end{graybox}
\end{example}
%%%%%%%%%%
\newpage
\begin{definition}[Principle of Strong Mathematical Induction]
Assume that ${\bf P}(1)$, ${\bf P}(2)$, ${\bf P}(3), \ldots$ is an infinite sequence of mathematical statements. \\
\begin{tabular}{lll|ll}
{\bf If} & & & {\bf If} \\
& (a) & ${\bf P}(1)$ is true, & & first domino falls \\
& {\bf and} & & & {\bf and} \\
& (b) & For any $k$, ${\bf P}(1), \ldots, {\bf P}(k)$ implies ${\bf P}(k+1)$ & & if all previous dominos fell, \\
& & & & then the next one falls \\
{\bf then} & & & {\bf then} \\
& \multicolumn{2}{l|}{all the statements in the sequence are true} & & all dominoes fall!
\end{tabular}
\end{definition}
\begin{example}
\begin{theorem}
Every number $n\in\N, n\geq 2$ can be written as a product of primes (or is a prime).
\end{theorem}
\paragraph{Proof.}
Base case: $n=2$ is a prime.
Assume that the Theorem holds for $n=2,3,4,\ldots, k$ and consider $n=k+1$.
If $k+1$ is prime, the claim holds.
If $k+1$ is not a prime, then it is divisible by some $2 \leq m \leq k$: $k+1=m\cdot \ell$ for some $2 \leq m,\ell\leq k$.
By hypothesis, both $m$ and $\ell$ are products of primes, hence so is $k+1$.
The Theorem follows by strong induction.
\end{example}
%\begin{ex} How many cuts are needed to cut a chocolate bar with $n$ squares into $1\times 1$ pieces?
%\end{ex}
%
%\paragraph{Claim: } $n-1$ cuts are needed to separate $n$ squares. \\
%
%\begin{minipage}{12cm}
%\begin{proof}
%For $n=1$, no cuts are needed, so the claim holds.
%
%Assume that the claim holds for $n=1,2,3,\ldots,k$ and consider a bar with $k+1$ squares.
%Perform one cut to obtain smaller bars with $m$ and $\ell$ squares (so $k+1=m+\ell$).
%By assumption, $m-1$ and $\ell-1$ are needed to cut the smaller bars, so to cut the original bar, we need
%$$
%1 + m-2+\ell-1 = m + \ell -1 = k
%$$
%The claim holds for $n=k+1$, so by strong induction it holds for all $n\in\N$.
%\end{proof}
%\end{minipage}
%\qquad
%\begin{minipage}{125pt}
%\includegraphics*[width=100pt]{figures/chocobar.pdf}
%\end{minipage}
%
%
%
%\begin{thm}
%Every $n\in \N$ can be written as a sum of distinct nonnegative integer powers of $2$.
%\end{thm}
%
%\begin{ex}
%\begin{align*}
%17 & = 2^0 + 2^4 \\
%42 & = 2^1 + 2^3+ 2^5 \\
%65 & = 2^0 + 2^6
%\end{align*}
%\end{ex}
%
%\begin{proof}
%The Theorem holds for $n=1$, since $1 = 2^0$.
%
%Assume that it works for $n=1,2,\ldots, k$ and consider $n=k+1$.
%
%If $k$ is even then by assumption $k=2^{a_1} + 2^{a_2} + \cdots + 2^{a_\ell}$ for $0<a_1<a_2<\cdots<a_\ell$ and
%$$
%k+1 = 2^0 + 2^{a_1} + 2^{a_2} + \cdots + 2^{a_\ell}
%$$
%is the required representation.
%
%If $k$ is odd, then $k+1$ is even, hence $k+1=2 m$ for some $m\in \N$. By assumption, $m=2^{a_1} + 2^{a_2} + \cdots + 2^{a_\ell}$ for some $0\leq a_1<a_2<\cdots<a_\ell$ and hence
%$$
%k+1 = 2^{a_1+1} + 2^{a_2+1} + \cdots + 2^{a_\ell+1}.
%$$
%By strong induction, the Theorem follows.
%\end{proof}
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% practice problems
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{exercises}
% Topics:
%
\begin{problist}
%
\prob Is the triangle inequality true for more than two numbers?
$$
|x_1 + x_2 + \cdots + x_n| \stackrel{?}{\leq} |x_1| + |x_2| + \cdots + |x_n|
$$
If it is, prove it.
\prob Is the AGM inequality true for any $x_1, x_2, \ldots, x_n \geq 0$?
$$
\sqrt{x_1 x_2 \cdots x_n} \stackrel{?}{\leq}\frac{x_1 + x_2 + \cdots + x_n}{n}
$$
If it is, prove it.
\prob Prove that for any $n \in \N$, $2^{6n}+3^{2n-2}$ is divisible by $5$.
\prob How many subsets does a set $S$ with $n$ elements have (including $S$ and $\emptyset$)?
\prob Show that If $x_1, \ldots, x_n \in [0,1]$ then $\displaystyle \prod_{i=1}^n (1-x_i) \geq 1 - \sum_{i=1}^n x_i$
\prob Can you use Mathematical induction to prove that $P(m), P(m+1), P(m+2),\ldots$ are true? If so, how?
\prob Can you use Mathematical induction to prove that $P(2), P(4), P(6), P(8), \ldots$ are true? If so, how?
\prob Can you use Mathematical induction to prove that $P(1), P(3), P(5), P(7), \ldots$ are true? If so, how?
\prob For which $n \in \N$, $2^n \geq (n+1)^2$? Prove your answer.
\prob Show that for even $n$'s, $n(n^2+3n+2)$ is divisible by $24$.
\begin{center}
\includegraphics*[width=15pt]{images/app-ind-L-shape.pdf}
\end{center}
\prob Prove that for any $n \in \N$, a $2^n \times 2^n$ checkerboard with one single square removed has an L--tiling (i.e., can be covered with L--shapes).
%
%{\it Proof. }
%For $k=1$, a $2\times 2$ board with one square removed has an L--shape, so it can be covered with a single L.
%
%Assume for $k$ and prove for $k+1$:
%
%\begin{minipage}{10cm}
%Divide the board in 4 $2^k \times 2^k$ boards. One of the smaller boards will have a square missing.
%
%Remove three squares from the centre from each of the other 3 boards - forming an L--shape as in the figure.
%We then have 4 boards with dimensions $2^k \times 2^k$ with one square removed.
%
%By induction hypothesis, we can cover each of these boards with L--shapes and we can cover the middle gap with one L--shape.
%Therefore the $2^{k+1} \times 2^{k+1}$ board has an L--tiling, and the claim follows by induction. \qed
%\end{minipage}
%\quad
%\begin{minipage}{150pt}
%\includegraphics*[width=150pt]{images/app-ind-2k1_board.pdf}
%\end{minipage}
\prob Read the following proof:
\begin{theorem} All horses have the same colour.
\end{theorem}
\begin{graybox}
\paragraph{Proof.}
Assume that the claim holds for groups of $k$ horses, and consider a group with $k+1$ horses $S = \{h_1, \ldots, h_{k+1}\}$.\\
By hypothesis, the horses in $A = \{h_1,\ldots, h_k\}$ and $B = \{h_2, \ldots, h_{k+1}\}$ have the same colour. Since the horse $h_2$ is in both groups, we deduce that the colour of the horses in $A$ must be the same as of these in $B$. \\
In conclusion, the horses in $S = A \cup B$ must have the same colour, and the claim holds by induction.
\end{graybox}
This proof is flawed. Explain how.
%
%\paragraph{The proof above is FALSE: }
%For $k=1$, $k+1=2$ and $A = \{h_1\}$ and $B = \{h_2\}$, so there are no common horses to $A$ and $B$ an the argument that the colour in $A$ is the same as in $B$ fails!
%
%(it's like we proved that the first domino falls and if a domino falls the next one also falls, except the second one never falls!)
\end{problist}
\end{exercises}