-
Notifications
You must be signed in to change notification settings - Fork 0
/
Homework2.tex
150 lines (124 loc) · 6.18 KB
/
Homework2.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
\documentclass[paper=letter, fontsize=11pt]{scrartcl} % Letter paper and 11pt font size
\usepackage{amstext, amsmath, amssymb}
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header
\setlength\parindent{0pt} % Removes all indentation from paragraphs
%----------------------------------------------------------------------------------------
% TITLE SECTION
%----------------------------------------------------------------------------------------
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\title{
\normalfont \normalsize
\textsc{San Francisco State University} \\ [25pt]
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge MATH 301 Assignment 2 \\ % The assignment title
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{Omar Sandoval}
\date{\normalsize\today}
\begin{document}
\maketitle
%----------------------------------------------------------------------------------------
% PROBLEM 8
%----------------------------------------------------------------------------------------
\textbf{8.} Prove the following statements concerning a real number \textit{x}. \\
(i) $x^2 - x - 2 = o \Leftrightarrow x = -1$ or $x = 2$.\\
(ii) $x^2 - x - 2 > 0 \Leftrightarrow x < -1$ or $x > 2$.
\\
-- \\
Proving $\rightarrow$: \\
\begin{align*}
x^2 - x - 2 = 0 &\rightarrow (x-2)(x+1) = 0. \\
&\rightarrow (x-2) = 0 \text{ or } (x+1) = 0. \\
&\rightarrow x = 2 \text{ or } x = -1. \\
\end{align*}
So, $x^2 - x - 2 = 0 \rightarrow x = 2 or x = -1.$ \\\\
Proving $\leftarrow$: \\
If $x = 2$, \\
$x^2 - x - 2 = 2^2 - 2 - 2 = 0.$ \\
If $x = -1$, \\
$x^2 - x - 2 = (-1)^2 - (-1) - 2 = 0.$ \\\\
Therefore, $x^2 - x - 2 = 0 \leftrightarrow x = 2$ or $x = -1$.\\
\\
%----------------------------------------------------------------------------------------
% PROBLEM 9
%----------------------------------------------------------------------------------------
\textbf{9.} Prove by contradiction that there does not exist a largest integer. [Hint: Observe that for any integer \textit{n} there is a greater one, say \textit{n} + 1. So begin your proof:
Suppose for contradiction that there is a largest integer. Let this integer be \textit{n}.$ \cdot$]
\\
-- \\
Suppose for contradiction that there is a largest integer. Let this integer be \textit{n}. Notice, $0 < 1 \rightarrow n + 1$. Therefore, $n$, is not the largest integer, since for all $n$, $n + 1 > n$.\\
\\
%----------------------------------------------------------------------------------------
% PROBLEM 10
%----------------------------------------------------------------------------------------
\textbf{10.} What is wrong with the following proof that 1 is the largest integer? \\
Let \textit{n} be the largest integer. Then, since 1 is an integer we must have $1 \le n$. On the other hand, since $n^2$ is also an integer we must have $n^2 \le n$ from which it follow that $n \le 1$. Thus, since $1 \le n$ and $n \le 1$ we must have $n = 1$. Thus 1 is that largest integer as claimed.
\\
What does this argument prove?
\\
--\\
The initial statement in this proof is false, which we showed in Problem 9. The conclusion is also false since 1 is not the largest integer. This argument tries to prove that if a largest integer existed, that integer would be 1.\\
\\
%----------------------------------------------------------------------------------------
% PROBLEM 11
%----------------------------------------------------------------------------------------
\textbf{11.} Prove by contradiction that there does not exist a smallest positive real number.
\\
--\\
Suppose for contradiction that there exists a smallest positive real number, $n$. Notice that $ 0 < \frac{1}{2} \rightarrow 0 < \frac{1}{2}n < n.$ So, the integer $\frac{1}{2}n,$ is real and less than $n$. That is a contradiction. Therefore, the original statement holds.\\
\\
%----------------------------------------------------------------------------------------
% PROBLEM 12
%----------------------------------------------------------------------------------------
\textbf{12.} Prove by induction on \textit{n} that, for all positive integers n, 3 divides $4^n + 5$.
\\
--\\
I) Base Step:\\
For $n = 1, 4^n + 5 = 4^1 + 5 = 9$ which is indeed divisible by 3. \\
II) Inductive Step: Suppose for some positive $k$, $P(k) \Rightarrow P(k+1)$.\\
$P(k): 4^k + 5 = 3q.$\\
$P(k+1): 4^{k+1} + 5 = 3q.$\\
Considering $P(k+1):$
\begin{align*}
4^{k+1} + 5 &= 4 \cdot 4^k + 5\\
&= 4(3q - 5) + 5, \text{ by our inductive hypothesis.}\\
&= 12q - 15 \\
&= 3(4q - 5) \\
&= 3p, \text{ where \textit{p} is an integer.}\\
& \text{Thus, 3 divides } 4^{k+1} + 5.
\end{align*}
Finally, by induction on $n$, 3 divides $4^n + 5$ for all positive integers $n$.\\
\\
%----------------------------------------------------------------------------------------
% PROBLEM 13
%----------------------------------------------------------------------------------------
\textbf{13.} Prove by induction on \textit{n} that $n! > 2^n$ for all integers $n$ such that $n \ge 4$.
\\
--\\
I) Base Step: $P(4) = 4! > 2^4 = 24 > 16.$\\
Clearly, base case holds. \\
II) Inductive step: Suppose for some positive $k \ge 4$, $P(k) \Rightarrow P(k+1)$ \\
$P(k): k! > 2^k$ \\
$P(k+1): (k+1)! > 2^{k+1}$ \\
Considering $P(k+1):$
\begin{align*}
2k! &> 2 \cdot 2^k \\
&> 2^{k+1}, \text{ by our inductice hypothesis.}\\
\\
(k+1)! &= (k+1)k! \\
(k+1)k! &\ge (4+1)k!, \text{ because k >= 4}\\
&= 5k! > 2k! > 2 \cdot 2^k = 2^{k+1} \\
\end{align*}
Finally, by induction on $n$, $n! > 2^n$ for all integers greater than or equal to 4.
\end{document}