\documentclass{article}
\usepackage{fullpage,amsmath}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{mathtools}



%%  Common macros for the course CSC165H1F,
%%  on the St. George Campus at the University of Toronto.
%%
%%  Copyright (c) 2009-2011 Francois Pitt <fpitt@cs.utoronto.ca>
%%
%%  This work may be distributed and/or modified under the conditions of
%%  the LaTeX Project Public License, either version 1.3 of this license
%%  or (at your option) any later version.
%%  The latest version of this license is in
%%      http://www.latex-project.org/lppl.txt
%%  and version 1.3 or later is part of all distributions of LaTeX
%%  version 2003/12/01 or later.
%%
%%  This work has the LPPL maintenance status "author-maintained".
%%
%%  The Current Maintainer of this work is
%%  Francois Pitt <fpitt@cs.utoronto.ca>.
%%
%%  This work consists of the file macros-165.tex.

% Trick so that math symbols are bold when text is.
\let\seiresfb\bfseries\def\bfseries{\boldmath\seiresfb}
\let\seiresdm\mdseries\def\mdseries{\unboldmath\seiresdm}

% Spacing macros with default argument.
\newcommand*{\vstretch}[1][1]{\vspace*{\stretch{#1}}}
\newcommand*{\hstretch}[1][1]{\hspace*{\stretch{#1}}}

% General fonts and characters.
\let\altemph\textsl  % alternate way to emphasize
\let\strong\textbf  % strong emphasis
\let\latinabb\emph  % abbreviations of latin phrases
\let\code\texttt  % code fragments
\let\const\textsf  % constants
\let\term\textbf  % newly-introduced (or defined) words
\let\var\mathrm  % multi-letter variables (or constants)
\let\pred\mathbf  % predicates
\newcommand*{\txtbksl} {\symbol{"5C}}% \
\newcommand*{\txtcaret}{\symbol{"5E}}% ^
\newcommand*{\txtunder}{\symbol{"5F}}% _
\newcommand*{\txtlcurl}{\symbol{"7B}}% {
\newcommand*{\txtrcurl}{\symbol{"7D}}% }
\newcommand*{\txttilde}{\symbol{"7E}}% ~
\newcommand*{\N}{\ensuremath{\mathbb{N}}}  % requires amssymb
\newcommand*{\Z}{\ensuremath{\mathbb{Z}}}  % requires amssymb
\newcommand*{\Q}{\ensuremath{\mathbb{Q}}}  % requires amssymb
\newcommand*{\R}{\ensuremath{\mathbb{R}}}  % requires amssymb
\newcommand*{\bigOh}{\mathcal{O}}
\newcommand*{\onehalf}{\ensuremath{{}^1\!\!/\!_2}}

% Abbreviations of latin phrases.
\newcommand*{\ie}{\latinabb{i.e.}}
\newcommand*{\eg}{\latinabb{e.g.}}
\newcommand*{\etc}{\latinabb{etc}}
\newcommand*{\vs}{\latinabb{vs}}

% General math macros.
\newcommand*{\comp}[1]{\overline{#1}}  % set complement
\newcommand*{\emptystr}{\varepsilon}  % empty string
\newcommand*{\lequiv}{\mathrel{\ \Longleftrightarrow\ }}  % equivalence
\newcommand*{\lxor}{\oplus}  % exclusive or
\newcommand*{\cat}{\cdot}  % string concatenation
\newcommand*{\invisible}[1]{\mathrel{\hphantom{#1}}}
% floors and ceilings, with optional size-changing command,
% e.g., \floor[\Big]{x/2} generates '\Big\lfloor{x/2}\Big\rfloor'
\newcommand*{\floor}[2][]{{#1\lfloor}{#2}{#1\rfloor}}
\newcommand*{\ceil}[2][]{{#1\lceil}{#2}{#1\rceil}}
\newcommand*{\lcm}{\operatorname{lcm}}  % requires amsmath
\newcommand*{\size}{\operatorname{size}}  % requires amsmath

% Redefined symbols from amssymb.
\renewcommand*{\emptyset}{\varnothing}  % rounder than default
\let\bigiff\iff
\renewcommand*{\iff}{\mathrel{\Leftrightarrow}}  % smaller than default
\let\bigimplies\implies
\renewcommand*{\implies}{\mathrel{\Rightarrow}}  % smaller than default
\renewcommand*{\ge}{\geqslant}  % with slanted line under the > sign
\renewcommand*{\le}{\leqslant}  % with slanted line under the < sign

% For algorithms, in Python.
\let\kw\textbf  % keywords
\let\proc\textsc  % function names
\newcommand*{\opgets}[1]{\mathrel{#1=}}
\newcommand*{\eq}{\mathrel{==}}
\newcommand*{\True}{\const{True}}
\newcommand*{\False}{\const{False}}
\newcommand*{\None}{\const{None}}
\newcommand*{\cmod}{\mathbin{\%}}
\newcommand*{\len}{\operatorname{len}}  % requires amsmath

% Like {itemize} but using less vertical space.
\newenvironment*{points}
 {\ifvmode\else\unskip\par\fi\begin{list}{$\bullet$}
   {\setlength{\topsep}{.25ex plus .125ex minus .1825ex}
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}
    \setlength{\labelwidth}{1.75em}}\ignorespaces}
 {\ifvmode\else\unskip\fi\end{list}\ignorespaces}

% Checkboxes and checklists.
\newcommand*{\cbox}[1]{{\fboxrule.125ex\fboxsep0ex
    \framebox[2.75ex]{\rule[-.75ex]{0ex}{2.75ex}\smash{#1}}}}
\newcommand*{\cmark}{\raisebox{.0625ex}{$\surd$\kern.125ex}}
\newcommand*{\xmark}{\raisebox{-.1875ex}{\kern.0625ex{X}}}
\newcommand*{\checkbox}{{\sf\cbox{}}}
\newcommand*{\checkedbox}{{\sf\cbox{\cmark}}}
\newcommand*{\markedbox}{{\sf\cbox{\xmark}}}
\newenvironment{checklist}{\begin{list}{\checkbox}{}}{\end{list}}
\newcommand*{\checkeditem}{\item[\checkedbox]}
\newcommand*{\markeditem}{\item[\markedbox]}

% Proof-related environments and macros.
\newcommand*{\just}{{\quad\#\ }}  % justification for a proof step
\newenvironment*{pindent}
   {\begin{list}{}
       {\topsep 0pt
        \partopsep 0pt
        \itemsep 0pt
        \parsep 0pt
        \parskip 0pt}\item\relax}
   {\unskip\end{list}\ignorespaces}
% Usage: \begin{assumption}[<pre-text>]{<assumption>}
%          ...body...
%        \end{assumption}{<conclusion>}
% is formatted as
%    <pre-text> assume <assumption>
%        ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Assume <assumption>
%        ...body...
%    <conclusion>
\newenvironment*{assumption}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{a}ssume {#2}
    \begin{pindent}}
   {\end{pindent}}
% Usage: \begin{pickavalue}[<pre-text>]{<names>}
%          ...body...
%        \end{pickavalue}{<conclusion>}
% is formatted as
%    <pre-text> let <names>
%    ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Let <names>
%    ...body...
%    <conclusion>
\newenvironment*{pickavalue}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{l}et {#2}
    \par\ignorespaces}
   {\unskip\par\ignorespaces}


\DeclarePairedDelimiter\abs{\lvert}{\rvert}%
\DeclarePairedDelimiter\norm{\lVert}{\rVert}%



\title{CSC165, Summer 2014\\
Assignment 6\\
Weight: 8\% \\
Solutions}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle


\begin{enumerate}
	\item State whether the following claim is true, and then prove or disprove it. Give a detailed structured proof, justifying every step.
		$$\forall n \in \mathbb{N}, [(\exists k \in \mathbb{N}, n = 4k)\lor(\exists k \in \mathbb{N}, n = 4k+1)]$$

\textbf{Solution:}

The statement is \textbf{false}. We prove its negation. The strategy is to realize that the statement is false since, for example, $2 mod 4 = 2$ and not $0$ or $1$, and to go back to the definition of $\mathbb{N}$.

\textbf{Proof}:\\

\begin{pindent}
Let $n = 2$
Then $n \in \mathbb{N}$\just{$2 \in \mathbb{N}$}\\
Then $n \not \in \{0, 4, 8, 12, ...\}$ \just{by inspection, $2$ is not in that sorted list}\\
Then $n \not \in \{4*0, 4*1, 4*2, ...\}$\just{algebra}\\
Then $\lnot [\exists k \in \mathbb{N}, n = 4k]$\\
Then also $n \not \in \{1, 5, 9, 13, ...\}$ \just{by inspection, $2$ is not in that sorted list}\\
Then $n \not \in \{4*0+1, 4*1+1, 4*2+1, ...\}$\just{algebra}\\
Then $\lnot [\exists k \in \mathbb{N}, n = 4k+1]$\\
Then $\lnot [\exists k \in \mathbb{N}, n = 4k] \land \lnot [\exists k \in \mathbb{N}, n = 4k+1]$\just{conjunction of two true statements}\\
Then $\lnot [ [\exists k \in \mathbb{N}, n = 4k] \lor  [\exists k \in \mathbb{N}, n = 4k+1]]$\just{De Morgan}\\
Then $\exists n \in \mathbb{N}, \lnot [ [\exists k \in \mathbb{N}, n' = 4k] \lor  [\exists k \in \mathbb{N}, n = 4k+1]]$\just{introduce existential, $n=2$ is such an $n$}\\
Then $\lnot[\forall n \in \mathbb{N}, [ [\exists k \in \mathbb{N}, n' = 4k] \lor  [\exists k \in \mathbb{N}, n = 4k+1]]]$\just{quantifier negation}\\
   \hspace*{13.5cm} $\blacksquare$


\end{pindent}

\newpage

	\item Let $\mathcal{F}$ be the set of all function from $\mathbb{N}$ to $\mathbb{R^+}$. Let $\ceil{f}$ be a function such that $$\forall n \in \mathbb{N}, [(\ceil{f})(n) = \ceil{f(n)}].$$ 

State whether the following claim is true, and then prove or disprove it. Give a detailed structured proof, justifying every step.

$$\forall f \in \mathcal{F}, \forall g \in \mathcal{F}, [f \in \mathcal{O}(g) \implies \ceil{f} \in \mathcal{O}(g)]$$

\textbf{Solution:}

The statement is \textbf{false}. We prove its negation.  The strategy is to prove that for $f(n) = 1/(n+1)$ and $g(n) = 1/(n+1)$, $f \in \mathcal{O}(g)$ but $\ceil{f} = 1 \not \in \mathcal{O}(g)$. (The reason we use $1/(n+1)$ is that $1/n$ is not defined for $n = 0$.

\textbf{Proof:}\\

\begin{pindent}
Let $f(n) = 1/(n+1)$\\
Let $g(n) = 1/(n+1)$\\
Let $B = 1$, $c = 1$\\
Then $B \in \mathbb{N}, c \in \mathbb{R}$\just{$1 \in \mathbb{R^{+}}, 1 \in \mathbb{N}   $}\\
Then $\forall n \in \mathbb{N}, [n\ge B]\implies [f(n) \le cf(n)]$\just{$f(n) \le f(n) = 1*f(n)$ always, so the consequent is always true}\\
Then $\exists c \in \mathbb{R^{+}}, \exists B \in \mathbb{N}, \forall n \in \mathbb{N}, [n\ge B]\implies [f(n) \le cf(n)]$\just{introduce existential, $n  = 1$ and $B=1$ are such $c$ and $B$}\\
Then $f \in \mathcal{O}(g)$\just{definition of big-Oh, $g = f$}\\
Also $\ceil{f} = 1$\just{$\forall n \in \mathbb{N}, 0 < 1/(n+1) < 1$}\\
\begin{assumption}{$c \in \mathbb{R^{+}}, B \in \mathbb{N}$}
	Let $n = max(B+1, (\ceil{c}+1)$\\
	Then $(B+1) \in \mathbb{N}$\just{integers are closed under addition}\\
	Also $(\ceil{c}+1) \in \mathbb{N}$\just{$\forall x \in \mathbb{R^{+}}\ceil{x} \in \mathbb{N}$}\\
	Then $n = max(B+1, \ceil{c}+1) \in \mathbb{N}$\just{both possibilities for the value of max are integers}\\
	Then $n > B$\just{$n = max(x, y) \implies n \ge x$}\\
	Then $(n > c)$\just{ $(\ceil{c}+1) \ge c+1 > c$}\\
	Then $1 > n/(n+1) > c/(n+1)=c*(1/(n+1_)$\just{$c>n>0$}\\
	Then $1 > c*(1/(n+1))$\just{transitivity}\\
	Then $\lnot[[n>B]\implies [1 \le c*(1/(n+1))]]$\just{the antecedent is true and the consequent is false}\\
	Then $\exists n \in \mathbb{N}, \lnot[[n>B]\implies [1 \le c*(1/(n+1))]]$\just{$n = max(B+1, \ceil{c}+1) \in \mathbb{N}$ works}\\
	Then $\lnot [\forall n \in \mathbb{N}, [n>B]\implies [1 \le c*(1/(n+1))]]$\just{quantifier negation}
\end{assumption}
Then $\forall c \in \mathbb{R^{+}}, \forall B \in \mathbb{N}, \lnot [\forall n \in \mathbb{N}, [n>B]\implies [1 \le c*(1/(n+1))]]$\just{introduce universal}\\
Then $\lnot[\exists c \in \mathbb{R^{+}}, \exists B \in \mathbb{N},  [\forall n \in \mathbb{N}, [n>B]\implies [1 \le c*(1/(n+1))]]]$\just{quantifier negation twice}\\
Then $\lnot [1 \in \mathcal{O}(1/(n+1)]$\just{definition of big-Oh}\\
Then $\lnot [\ceil{f} \in \mathcal{O}(g)]$\just{substitution}\\
Then $[f \in \mathcal{O}(g)]\land[\lnot [\ceil{f} \in \mathcal{O}(g)]]$\just{conjunction}\\
Then $\lnot[[f \in \mathcal{O}(g)] \implies [\ceil{f} \in \mathcal{O}(g)]]]$\just{implication negation}\\
Then $\exists f \in \mathcal{F}, \exists g \in \mathcal{F}, \lnot[[f \in \mathcal{O}(g)] \implies [\ceil{f} \in \mathcal{O}(g)]]]$\just{$f(n) = 1/(n+1)$ and $g(n) = 1/(n+1)$ are such $f$ and $g$}\\
Then $\lnot [\forall f \in \mathcal{F}, \forall g \in \mathcal{F}, [[f \in \mathcal{O}(g)] \implies [\ceil{f} \in \mathcal{O}(g)]]]]$\just{quantifier negation twice}\\
   \hspace*{13.5cm} $\blacksquare$
	
\end{pindent}

\newpage

	\item The Fibonacci numbers $fib(n)$ are defined as follows:\\ $fib(0) = 1, fib(1) = 1$,  and $fib(n) = fib(n-1) + fib(n-2)$ for $n \in \{2, 3, 4, 5, ...\}.$\\ Prove that 
		$$\forall n \in \mathbb{N}, fib(n) \leq 2^n.$$

It will  be helpful to prove, using induction, that $[\forall n \in \mathbb{N}, P(n)]$ where $$P(n): \forall k \in \mathbb{N}, [k \le n] \implies fib(k) \leq 2^k.$$

\textbf{Solution:}

Define 
	$$P(n): \forall k \in \mathbb{N}, [k \le n] \implies fib(k) \leq 2^k.$$

We would like to prove that  $[\forall n \in \mathbb{N}, P(n)]$.

We first prove $P(0)$ and  $P(1)$.

\begin{pindent}
	$1 \le 1 = 2^0$\just{algebra}\\
	Then $fib(0) \le 2^0$\just{substitution}\\
	$1 \le 2 = 2^1$\just{algebra}\\
	Then $fib(1) \le 2^1$\just{substitution}\\
	Then $\forall k \in \mathbb{N}, [k \le 1] \implies fib(k) \leq 2^k$\just{the consequent is true when the antecedent is true}\\
	Then $P(1)$\just{substitution}\\
	Also,  $P(0)$\just{the consequent is true in $P(0)$  whenever it's true in $P(1)$}
\end{pindent}

\textbf{Base case:}
\begin{pindent}
	$P(1)$ \just{proved above}
\end{pindent}

\textbf{Induction step:}
\begin{pindent}
\begin{assumption}{$n \in \{1, 2, 3, 4, 5, ...\}$}
	\begin{assumption}{P(n)}
		Then $\forall k \in \mathbb{N}, [k \le n] \implies fib(k) \leq 2^k$\just{substitution}\\
		Then $fib(n-1) \leq 2^{n-1}, fib(n) \leq 2^n$\just{$n \le n, (n-1) \le n$}\\
		Then $fib(n-1)+fib(n) \le 2^{n-1} + 2^n \le 2^n + 2^n = 2^{n+1}$\just{algebra}\\
		Then $fib(n+1) \le 2^{n+1}$\just{definition of fib() for $n\ge 1$}\\
		Then $\forall k \in \mathbb{N}, [k \le (n+1)] \implies fib(k) \leq 2^k$\just{proved for $k \le n$ and for $k = n+1$}\\
		Then $P(n+1)$\just{substitution}
	\end{assumption}{$P(n) \implies P(n+1)$\just{introduce implication}}
\end{assumption}{$\forall n \in \{1, 2, 3, 4, 5, ...\},  P(n) \implies P(n+1)$\just{introduce universal}}
\end{pindent}

\textbf{We can now conclude:} 
\begin{pindent}
	$P(1)$\just{proved above}\\
	$\forall n \in \{1, 2, 3, 4, 5, ...\},  P(n) \implies P(n+1)$\just{proved above}\\
	Then $\forall n \in \{1, 2, 3, 4, 5, ...\}, P(n)$\just{by the principle of simple induction}\\
	Also, $P(0)$\just{proved above}\\
	Then $\forall n \in \mathbb{N}, P(n)$\just{true for all $\mathbb{N} = \{0, 1, 2, 3, 4, ...\} $}\\
\end{pindent}

But $P(n)$ is not exactly what we need to prove. We now conclude:\\
\begin{pindent}
	$[\forall k \in \mathbb{N}, [k \le n] \implies fib(k) \leq 2^k] \implies [fib(n) \leq 2^n]$\just{$n \leq n$}\\
	Then $P(n) \implies [fib(n) \leq 2^n]$\just{substitution}\\
	Then $\forall n \in \mathbb{N}, [P(n)\land[P(n) \implies [fib(n) \leq 2^n]]$\just{conjunction with a true statement}
	Then $\forall n \in \mathbb{N}, fib(n) \leq 2^n$\just{implication elimination}\\
   \hspace*{13.5cm} $\blacksquare$
\end{pindent}


(The last part is more formal that it has to be.)

\item \begin{enumerate}
	\item Write a function \texttt{def lowest\_terms(n,m)} that takes two integers as inputs, and returns True iff $n/m$ is a fraction that is reduced to lowest terms. For example, \texttt{lowest\_terms(2,3)} is True but \texttt{lowest\_terms(4,6)} is False.  In the comments to your code, explain how the code works, and argue informally (i.e., no formal proof is required) that it produces the desired output. In the comments, provide the output for 8 test cases.

	\item In the comments in \texttt{a6.py}, give a tight upper bound on the total number of comparison operators ((\texttt{$==$, $<$, $>$, $<=$, $>=$}) and arithmetic operators (\texttt{$+$,$-$, mod, $/$, $*$,....}) performed when running \texttt{def lowest\_terms(n,m)}. Your answer should be one expression for the tight upper bound on sum of the number of comparison operators and the number of arithmetic operators. Justify your answer. (A formal proof is not required). Note: your answer will be an expression that may depend on both \texttt{m} and \texttt{n}.

\end{enumerate}

\textbf{Solution:}

See \texttt{a6.py}.



	\item \textbf{Bonus question, worth half the weight of the other questions:} Claims 5.3 and 5.4 in Section 5.4 in the notes present a method to list all the rational numbers. Note, however, that, if that method is used, every rational number is actually listed an infinite number of times (for example, the number $1$ is listed as $1/1, 2/2, 3/3, 4/4, 5/5...$). It is possible to modify this method that produces a list of all the rational numbers such that every rational number appears in the list exactly once. Write a Python function \texttt{def r(n)} that takes an integer \texttt{n} as input and prints the $n$-th (starting from 0)  rational number in such a list. For example, if the list begins with $\{0, 1, -1,  1/2, -1/2, 2, -2, ...\}$, \texttt{r(4)} should print ``-1/2" (the output should not contain quotes). In the comments to your code, explain how the code works, and argue informally (i.e., no formal proof is required) that it produces the desired output. Also in the comments, include the output for r(0), r(1), r(2), ..., r(20).  \textit{Hints: (1) I suggest  implementing code that prints a list using the method in Claim 5.3,  then modifying that code to print a list using the method in Claim 5.4, and then thinking how to implement \texttt{def r(n)} by modifying the code from there. You only need to submit \texttt{def r(n)} and not anything else.} \textbf{Clearly documented} attempts at a solution that \textbf{run}  and make progress towards the solution will get part marks. Submit your code and comments in \texttt{bonus6.py}.

\textbf{Solution:}

See \texttt{a6b.py}.


\end{enumerate}


\end{document}
