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
|
\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\lcm{\mathop{\rm lcm}}
\li Use mathematical induction to prove that the following statement is
true for all positive integers $n.$
$$8+15+22+29+\ldots+(7n+1) = {(7n(n+1)+2n)\over 2}.$$
We start with the base case $n = 1.$
$$8 = {7(1)(1+1)+2(1)\over 2} = {14+2\over 2} = 8.$$
We now inductively assume that the statement is true for some positive
integer $k,$ and prove the statement for $k+1.$
$$8+15+\ldots+(7k+1) = {7k(k+1)+2k\over 2}.$$
We add $7(k+1)+1$ to both sides.
$$8+15+\ldots+(7k+1)+(7(k+1)+1) = {7k(k+1)+2k\over 2} + 7(k+1)+1 =$$$$
{7k(k+1) + 7(2)(k+1) + 2k + 2\over 2} = {7(k+1)(k+2) + 2(k+1)\over 2}.$$
We have thus shown the statement for $k+1.$
By mathematical induction, we have proven the initial statement for all
positive integers $n.$
\li Use mathematical induction to prove or disprove that the following
statement is true for all non-negative integers $n.$
$$1+nh \leq (1+h)^n,\hbox{ where }h>-1.$$
We start with the base case of the smallest non-negative integer $n=0.$
$$1+0h = 1 \leq 1 = (1+h)^0,$$
(note that $h>-1,$ so $(1+h)>0,$ so $(1+h)^0 = 1.$)
We now assume that the statement is true for some non-negative integer
$k$ and prove the statement for $k+1.$
We know the inductive hypothesis $1+kh \leq (1+h)^k$ and multiply both
sides by $1+h$ to get
$(1+kh)(1+h) = 1+(k+1)h+kh^2 \leq (1+h)^{k+1}$
$0\leq h^2,$ so $0\leq kh^2,$ so $1+(k+1)h \leq (1+h)^{k+1}.$
By mathematical induction, we have shown that for all non-negative
integers $n,$ $1+nh \leq (1+h)^n.$
\li Use mathematical induction to prove or disprove that the following
statement is true for all positive odd integers $n.$
$$n^2-1\hbox{ is divisible by }8.$$
We start with the base case of the smallest positive odd integer $n=1.$
$n^2-1 = 1-1 = 0,$ and $8\mid 0,$ showing our base case.
We now assume that the statement is true for some positive odd integer
$k.$ Because $k$ is odd, there is an integer $j$ such that $k = 2j+1.$
We start from the inductive hypothesis $k^2-1$ is divisible by 8, so
there is an $l$ such that $k^2-1 = 8l.$
$$k^2-1 = (2j+1)^2-1 = 4j^2+4j.$$
We add $8j+8$ to both sides.
$$4j^2+12j+8=(2j+3)^2-1 = (k+1)^2-1 = 8(l+j+1),$$
showing that $(k+1)^2-1$ is divisible by 8.
By mathematical induction, we have now shown that, for all positive odd
integers $n,$ $n^2-1$ is divisible by 8.
\li Use mathematical induction to prove that the following statement is
true for all integers $n$ greater than 1.
$$n! < n^n.$$
We start with the base case $n = 2.$ $2! = 2 < 4 = 2^2.$
We now inductively assume the statement is true for some $k \geq 2,$ and
we show that $(k+1)! < (k+1)^{k+1}.$
Noting that $k^k < (k+1)^k$ for $k > 1,$
$$k! < k^k < (k+1)^k.$$
We then multiply both sides by $k+1,$ giving
$$(k+1)! < (k+1)^{k+1}.$$
We have shown by mathematical induction that for all integers $n>1,$
$n! < n^n.$
\bye
|
