/
Math350HW0.tex
121 lines (82 loc) · 3.83 KB
/
Math350HW0.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
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\renewcommand{\P}{{\cal P}}
\pagestyle{empty}
\begin{document}
\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}
\section*{Math 350: Homework 0 (\LaTeX sample)}
\section*{Name: {\it Sample}}
\subsection*{Problem 1: }
Show that $\neg (P\lor Q) \equiv \neg P \land \neg Q$ using truth tables:
$$
\begin{array}{|c|c|c|c|c|c|c|}
P & Q & \neg P & \neg Q & P\lor Q& \neg(P\lor Q) & \neg P \land \neg Q\\
\hline
T & T & F& F& T& \bf F & \bf F \\
T & F & F& T& T& \bf F & \bf F \\
F & T & T& F& T& \bf F & \bf F \\
F & F & T& T& F& \bf T & \bf T \\
\end{array}
$$
\subsection*{Problem 2: }
Show that $(A\cap B)^c = A^c \cup B^c$:
Suppose $x\in (A\cap B)^c$. Then $x\not \in A\cap B$, meaning that $x$ is not in both $A$ and $B$: either $x\not \in A$ or $x\not \in B$. In other words, $x\in A^c$ or $x\in B^c$, making $x\in A^c \cup B^c$.
Conversely, if $x \in A^c \cup B^c$ then $x\in A^c$ or $x\in B^c$. So $x\not \in A$ or $x\not \in B$, so it is not possible for $x$ to be in both $A$ and $B$. That is $x\not\in A\cap B$, making $x\in (A\cap B)^c$.
\subsection*{Problem 3: }
Consider a function $f:X\to Y$.
a) Show that $A\subset B \Rightarrow f(A)\subset f(B)$:
For any $y\in f(A)$ there is an $x\in A$ with $y=f(x)$. Since $A\subset B$, we have $x\subset B$, so $y\in f(B)$.
b) Show that $U\subset V \Rightarrow f^{-1}(U)\subset f^{-1}(V)$:
For any $x\in f^{-1}(U)$ there is $y\in U$ with $y=f(x)$. Since $y\in U$ and $U\subset V$, we have $y\in V$. Thus $x=f^{-1}(y)\in f^{-1}(V)$.
\subsection*{Problem 4: Solve exercise 1 from section 1.1 (page 3) }
(from C.S.) Let $(x,y)\in (A\times B)\cap (C\times D)$. Then $(x,y)$ is in $A\times B$ and in
$C\times D$. So $x $ is in $A$ and in $C$ and $y$ is in $B $ and in $D$. Thus
$x\in A\cap C$ and
$y\in B\cap D$. So
$x\in (A\cap C)\times (B\cap D)$.
Therefore $(A\times B)\cap (C\times D)\subset (A\cap C)\times (B\cap D)$.
For the other inclusion, let $(x,y) \in (A\cap C)\times (B\cap D)$.
Then $x\in A\cap C$ and $y\in B\cap D$. So $(x,y)\in A\times B$ and
$(x,y)\in C\times D$. Thus $ (A\cap C)\times (B\cap D)\subset (A\times B)\cap (C\times D)$.
\subsection*{Problem 5: Prove the Binomial formula }
Show that for all numbers $a$ and $b$, \[(a+b)^n=\sum_{i=0}^n \binom{n}{i} a^i b^{n-i}\] where $\binom{n}{i}=\frac{n!}{i!(n-i)!}$ is the binomial coefficient.
We proceed by induction. The base step is clear as $\binom{1}{0}=1=\binom{1}{1}$.
For the inductive step assume that $(a+b)^n=\sum_{i=0}^n \binom{n}{i} a^i b^{n-i}$.
Then
\renewcommand{\arraystretch}{1.5}
$$
\begin{array}{rl}
(a+b)^{n+1} &= (a+b)(a+b)^n=(a+b) \cdot \sum_{i=0}^n \binom{n}{i} a^i b^{n-i}\\
&=\sum_{i=0}^n \binom{n}{i} a^{i+1} b^{n-i}+\sum_{i=0}^n \binom{n}{i} a^i b^{n+1-i}\\
&=a^{n+1}+\sum_{i=0}^{n-1} \binom{n}{i} a^{i+1} b^{n-i}+\sum_{i=1}^n \binom{n}{i} a^i b^{n+1-i}+b^{n+1}\\
&=a^{n+1}+\sum_{i=0}^{n-1} \binom{n}{i} a^{i+1} b^{n-i}+\sum_{i=0}^{n-1} \binom{n}{i+1} a^{i+1} b^{n-i}+b^{n+1}\\
&=a^{n+1}+\sum_{i=0}^{n-1} \left[\binom{n}{i}+\binom{n}{i+1}\right] a^{i+1} b^{n-i}+b^{n+1}\\
&=a^{n+1}+\sum_{i=0}^{n-1} \binom{n+1}{i+1} a^{i+1} b^{n-i}+b^{n+1}\\
&=a^{n+1}+\sum_{i=1}^{n} \binom{n+1}{i} a^{i} b^{n+1-i}+b^{n+1}\\
&=\sum_{i=0}^{n+1} \binom{n+1}{i} a^{i} b^{n+1-i},
\end{array}
$$
which completes the inductive step.
We used the identity
\[
\binom{n}{i}+\binom{n}{i+1} = \binom{n+1}{i+1}
\]
which we now verify by direct calculation from the definition (we omit
a few steps).
$$
\begin{array}{rl}
\binom{n}{i}+\binom{n}{i+1} &=
\frac{n!}{i!(n-i)!}+\frac{n!}{(i+1)!(n-(i+1))!}\\
&=\frac{n!(i+1)+n!(n-i)) } {(i+1)!(n-i)!}\\
&=\frac{n!(i+1+n-i) } {(i+1)!(n-i)!}\\
&=\frac{(n+1)!} {(i+1)!(n+1-(i+1))!}\\
&= \binom{n+1}{i+1}.
\end{array}
$$
\end{document}