1 files changed, 115 insertions, 0 deletions
diff --git a/howard/hw8.tex b/howard/hw8.tex
new file mode 100644
index 0000000..c760b02
--- /dev/null
+++ b/howard/hw8.tex
@@ -0,0 +1,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