Assignment 6

\documentclass[a4paper]{article}

\usepackage{amsmath,amsfonts}

\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textheight}{8.7in}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\title{Assignment 6}
\author{Frank Yang}

\begin{document}
\maketitle
\section{Homework list}

\begin{itemize}

\item Section 3.3:  2, 12, 24

\item Section 4.1:  26ac

\item Section 4.2:  6ab, 12cdef

\end{itemize}

\section{Solution}

\begin{enumerate}

\item[2]
We give a proof by induction. 
Let $S(n)=1+5+9+...+(4n-3)$, where n is a positive integer.
We want to prove that for every n, $S(n)=2n^2-n$.


Basis step:
$S(1)=2 \times 1^2-1=1$, which is same with sum of 1. 


Inductive step:
Assume $S(k)=2k^2-k$. We want to show $S(k+1)=2(k+1)^2-k$. 
$$S(k+1)=1+5+9+...+(4k-3)+(4(k+1)-3)=S(k)+4(k+1)-3$$
$$S(k+1)=2k^2-k+4(k+1)-3=2k^2+4k+2-1-k$$
$$2k^2+4k+2-1-k=2(k^2+2k+1)-1-k=2(k+1)^2-(k+1)$$


So, we have shown that if $S(k)=2k^2-k$, then $S(k+1)=2(k+1)^2-k$. Since the statement is also true for the basis case, $S(n)=2n^2-n$ for every positive integer n.




\item [12]
We give a proof by induction. 
Let $b(n)=1/3+1/15+...+1/(4n^2-1)$, where n is a positive integer.


(a)$b_{1}=1/3,b_{2}=2/5,b_{3}=3/7,b_{4}=4/9, b_{5}=5/11$ 


(b)$b_{n}=n/(2n+1)$


(c)We give a proof by induction. 
We want to prove that for every n, $b_{n}=n/(2n+1)$.


Basis step:
$b_{1}=1/(2\times 1 +1)=1/3$, which is the same with sum of $1/(4\times 1^2-1)=1/3$. 

Inductive step:
Assume $b_{k}=k/(2k+1)$. We want to show $b_{k+1}=(k+1)/(2(k+1)+1)=(k+1)/(2k+3)$. 

$$b_{k+1}=b_{k}+1/(4(k+1)^2-1)=k/(2k+1)+1/(4(k+1)^2-1)$$
$$=k/(2k+1)+1/(4k^2+8k+3)=k/(2k+1)+1/((2k+1)(2k+3))$$
$$=k(2k+3)/((2k+1)(2k+3))+1/((2k+1)(2k+3)=(2k^2+3k+1)/((2k+1)(2k+3))$$
$$=(k+1)(2k+1)/((2k+1)(2k+3))$$
$$=(k+1)/(2k+3)$$



We have shown that if $b_{k}=k/(2k+1)$, then $b_{k+1}=(k+1)/(2(k+1)+1)=(k+1)/(2k+3)$. Since the statement is also true for the basis case, $b_{n}=n/(2n+1)$ for every positive integer n.

(d) Based on our previous proof, the statement is equivalent as $b_{\infty}$ converges. Since $\displaystyle \lim_{n \to \infty}b_{n}=\displaystyle \lim_{n \to \infty}n/(2n+1)=1/2$. The sum of this series converges to $1/2$.


\item[24]
We give a proof by induction. Let $f_{n}$ be the $n$th Fibonacci, where n is a integer $\geq 0$. We want to show that for every n, $f_{n}<2^n$. 


Basis step:
$f_{0}=0$, which is less then $2^0=1$. 
$f_{1}=1$, which is less then $2^1=2$. 


Inductive step:
Assume $f_{k}<2^k$ and $f_{k+1}<2^{k+1}$. We want to show $f_{k+2}<2^{k+2}$. 

$$f_{k+2}=f_{k}+f_{k+1}<2^k+2^{k+1}<2^{k+1}+2^{k+1}=2^{k+2}$$


We have shown that if $f_{k}<2^k$ and $f_{k+1}<2^{k+1}$, then$f_{k+2}<2^{k+2}$. Since the statement is also true for the two basis cases,  $f_{n}<2^n$ for all n.


\item[26a]
We give a proof by induction.


We want to prove for all $I$, $A \cap (\displaystyle \bigcup_{i\in I}  A_{i}) = \displaystyle \bigcup_{i\in I}(A \cap A_{i}) $.


Basis Step:
Assume there are only two sets in $A_{i}$ family, $A_{1}$ and $A_{2}$.
From basic set identities, we know that $A \cap (A_{1} \cup A_{2}) = (A \cap A_{1}) \cup (A \cap A_{2})$. Thus, the statement is true for basis case. 


Inductive step:
Assume for any integer $k>2$, $A \cap (\displaystyle \bigcup_{i\in k}  A_{i}) = \displaystyle \bigcup_{i\in k}(A \cap A_{i})$. We are going to show that $A \cap (\displaystyle \bigcup_{i\in k+1}  A_{i}) = \displaystyle \bigcup_{i\in k+1}(A \cap A_{i})$. 
$$A \cap (\displaystyle \bigcup_{i\in k+1}  A_{i}) = A \cap (\displaystyle \bigcup_{i\in k}  A_{i} \cup A_{k+1})$$
Since $\displaystyle \bigcup_{i\in k}  A_{i}$ can be treated as a single set, 
$$A \cap (\displaystyle \bigcup_{i\in k}  A_{i} \cup A_{k+1})=(A \cap \displaystyle \bigcup_{i\in k} A_{i}) \cup (A \cap A_{k+1})$$
$$=\displaystyle \bigcup_{i\in k}(A \cap A_{i}) \cup (A \cap A_{k+1})$$
$$=\displaystyle \bigcup_{i\in k+1}(A \cap A_{i})$$


\item[26c]
We give a proof by induction.


We want to prove for all $I$, $(\displaystyle \bigcap_{i\in I}  A_{i})^{c} = \displaystyle \bigcup_{i\in I} A_{i}^{c}$.


Basis Step:
Assume there are only two sets in $A_{i}$ family, $A_{1}$ and $A_{2}$.
From basic set identities, we know that $ (A_{1} \cap A_{2})^c = A_{1}^c \cup A_{2}^c$. Thus, the statement is true for basis case. 


Inductive step:
Assume for any integer $k>2$, $(\displaystyle \bigcap_{i\in k}  A_{i})^{c} = \displaystyle \bigcup_{i\in k} A_{i}^{c}$. 


We are going to show that $(\displaystyle \bigcap_{i\in k+1}  A_{i})^{c} = \displaystyle \bigcup_{i\in k+1} A_{i}^{c}$. 
$$(\displaystyle \bigcap_{i\in k+1}  A_{i})^{c}=(\displaystyle \bigcap_{i\in k}  A_{i} \cap A_{k+1})^{c}$$

Since $\displaystyle \bigcap_{i\in k}  A_{i}$ can be treated as a single set, 
$$(\displaystyle \bigcap_{i\in k}  A_{i} \cap A_{k+1})^{c}=(\displaystyle \bigcap_{i\in k}  A_{i})^{c} \cup A_{k+1}^{c}$$
$$=(\displaystyle\bigcup_{i\in k} A_{i}^{c}) \cup A_{k+1}^{c}$$
$$=\displaystyle \bigcup_{i\in k+1} A_{i}^{c}$$


\item[6]
(a) not reflexive, symmetric, not antisymmetric, not transitive


(b) reflexive, symmetric, not antisymmetric, not transitive

 
\item[12]
(c) Assume $R$ and $S$ are symmetric and odered pair $(a,b)$ is in $R \cap S$. Then, $(a,b)$ is in $R$ and in $S$. Since both relations are symmetric, $(b,a)$ is also in $R$ and in $S$. So $(b,a)$ is in $R \cap S$, which shows $R \cap S$ is symmetric. 

(d) Assume $R$ and $S$ are symmetric and odered pair $(a,b)$ is in $R \cup S$. Then, $(a,b)$ is in $R$ or in $S$. Since both relations are symmetric, $(b,a)$ is also in $R$ or in $S$. So $(b,a)$ is in $R \cup S$, which shows $R \cup S$ is symmetric.

(e) Assume $R$ and $S$ are transitive and odered pairs $(a,b)$, $(b,c)$ are in $R \cap S$. Then, $(a,b)$, $(b,c)$ are in $R$ and in $S$. Since both relations are transitive, $(a,c)$ is also in $R$ and in $S$. So $(a,c)$ is in $R \cap S$, which shows $R \cap S$ is transitive.


(e) Assume $R$ and $S$ are transitive and odered pairs $(a,b)$, $(b,c)$ are in $R \cup S$. Then, $(a,b)$, $(b,c)$ are in $R$ or in $S$. Since both relations are transitive, $(a,c)$ is in $R$ or in $S$. So $(a,c)$ is in $R \cup S$, which shows $R \cup S$ is transitive.


\end{enumerate}
\end{document}