Assignment 6
Forfatter:
Frank Yang
Sidst opdateret:
11 år siden
Licens:
Other (as stated in the work)
Resumé:
Assignment for Math Structure
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
\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}