\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 5\\
Solutions}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle

The goal of this assignment is for you to keep practicing writing proofs. Our goal this semester is for you to learn to write proofs by the end of the course, and the only way to learn to write proofs is through practice. \textbf{In your proofs, justify each step}. If you are asked to prove or disprove a claim, first determine whether the claim is true, and then prove that it is true or prove that it is false (i.e., that its negation is true), depending on which is correct.

You may work in groups of no more than two students, and \textbf{you should submit a TEX file named \texttt{a5.tex} and a PDF file named \texttt{a5.pdf} that was produced by compiling your  \texttt{a4.tex}} and that contains the answers to the questions below. You should also submit your Python code in \texttt{a5.py} These files should be submitted using
\href{https://markus.cdf.toronto.edu/csc165-2014-05/main?locale=en}{MarkUs}. 

For this assignment, you will \textbf{not} receive 20\% of the marks for leaving questions blank or writing ``I cannot answer this.''


\begin{enumerate}
	\item Prove that
		$$\forall a \in \mathbb{R}, \forall n \in \mathbb{N}, [0 < a < 1] \implies a^n \le 1$$
using mathematical induction. Justify every step, and use the detailed structured proof format (you can follow the format used in the induction handout on the website.) \\


\textbf{Solution:}

	First, we define the predicate: $ P(k) := [\forall a \in \mathbb{R}, [0 < a < 1] \implies a^k \le 1 ]$ \\

	\textbf{Base case:}

	\begin{pindent}
	\begin{assumption}{$a \in \mathbb{R}$}
		\begin{assumption}{$0 < a < 1$}
			Then $a^0 = 1 \le 1$\just{algebra}
		\end{assumption}{Then $[0 < a < 1] \implies a^0 \le 1$ \just{introduce implication}}		
	\end{assumption}{Then $\forall  a \in \mathbb{R}, [0 < a < 1] \implies a^0 \le 1$ \just{introduce universal}}\\
	Then $P(0) \just{substitution}$
	\end{pindent}

\newpage
	
	\textbf{Induction step:}
	\begin{pindent}

	\begin{assumption}{$k \in \mathbb{N}$}
	\begin{assumption}{$P(k)$ is true}
		Then $\forall a \in \mathbb{R}, [0 < a < 1] \implies a^k \le 1$\just{substitution} 
		\begin{assumption}{$a \in \mathbb{R}$}
			\begin{assumption}{$0 < a < 1$}
				Then $a^k \le 1$\just{implication} \\
				Then $a*a^k \le a*1$\just{$a>0$}\\
				Then $a^{k+1} \le a < 1$ \just{$a < 1$}\\
				Then $a^{k+1} < 1$ \just{transitivity}
			\end{assumption}{Then $0 < a < 1 \implies a^{k+1} < 1$ \just{introduce implication}}
		\end{assumption}
		Then $\forall a \in \mathbb{R}, [0 < a < 1 \implies a^{k+1} \le 1]$\just{introduce universal}\\
		Then $P(k+1)$\just{substitution}
	\end{assumption}{Then $P(k) \implies P(k+1)$ \just{introduce implication}}
	\end{assumption}
	Then $\forall k \in \mathbb{N}, P(k) \implies P(k+1)$ \just{introduce universal}

	\end{pindent}

	We now conclude:
	\begin{pindent}
	$P(0)$ \just{proven above}\\
	Also, $\forall k \in \mathbb{N}, P(k) \implies P(k+1)$ \just{proven above}\\
	Then $\forall n \in \mathbb{N}, P(n)$ \just{principle of simple induction}\\
	Then $\forall n \in \mathbb{N}, \forall  a \in \mathbb{R}, [0 < a < 1] \implies a^n \le 1$\just{substitution}\\
	Then $\forall a \in \mathbb{R}, \forall  n \in \mathbb{N}, [0 < a < 1] \implies a^n \le 1$\just{universal quantifiers commute}\\
   \hspace*{13.5cm} $\blacksquare$

	\end{pindent}

\noindent Note: this proof is somewhat fussier than what should get perfect marks, but note that it is necessary to make sure that $a$ and $n$ are defined wherever they are used.


	\item  Prove that
		$$\forall n \in \mathbb{N}, [n>2 \implies n! < n^n]$$
using mathematical induction. Justify every step, and use the detailed structured proof format (you can follow the format used in the induction handout on the website). \\

\textbf{Solution:}

We prove a helpful lemma: $\forall k \in \mathbb{N}, k^k < (k+1)^{k}$ :

	\begin{pindent}
		\begin{assumption}{ $k \in \mathbb{N}$}
		Then $0 < \frac{k}{k+1} \le 1$  \just{$k>0, k+1>1, k < k+1$}\\
		Then  $\frac{k}{k+1}^k \le 1$ \just{Question 1} \\
		Then, $\frac{k^k}{(k+1)^k} \le 1$ \just{algebra} \\
		Then, $k^k \le (k+1)^k$ \just{Multiply both sides by $(k+1)^k$}
		\end{assumption}{Then  $\forall k \in \mathbb{N}, k^k \le (k+1)^{k}$ \just{introduce universal}} 
	\end{pindent}

\vspace{.2in}

	Now, define the predicate: $ P(k) := k! < k^k $




	\textbf{Base case:}
	\begin{pindent}
	$3! = 1*2*3 = 6$ \just{algebra}\\
	Also, $3^3 = 3*3*3 = 27$ \just{algebra}\\
	Then $3! < 3^3$ \just{$6 < 27$}\\
	Then $P(3)$\just{substitution}	
	\end{pindent}


	\newpage

	\textbf{Induction step:}
	\begin{assumption}{$k \in \mathbb{N}$}
	\begin{assumption}{$P(k)$ is true}
		Then $k! < k^k$ \just{substitution}
		Then $(k+1)*k! < (k+1)*k^k$ \just{Multiply both sides by $k+1 > 0$} \\
		Then $(k+1)! < (k+1)*k^k < (k+1)*(k+1)^k = (k+1)^{(k+1)}$ \just{algebra, the lemma above}\\
		Then $(k+1)! <  (k+1)^{(k+1)}$\just{transitivity}\\
		Then $P(k+1)$\just{substitution}
	\end{assumption}{Then $P(k) \implies P(k+1)$\just{implication}}
	\end{assumption}{Then $\forall k \in \mathbb{N}, P(k) \implies P(k+1)$\just{introduce universal}}

	(Note that the induction starts at $3$, but the induction step can start at $0$ as usual, since False implies True and False implies False are both true.)

\vspace{.2in}

	We can now conclude:
	\begin{pindent}
		$P(3)$ is true \just{proven above}\\
		$\forall k \in \mathbb{N}, P(k) \implies P(k+1)$\just{proven above}\\
		Then $\forall n \in \{3, 4, 5, 6, ....\}, P(n)$\just{principle of simple induction}\\
		Then $\forall  n \in \mathbb{N}, n >2 \implies P(n)$\just{$[(n \in \mathbb{N}) \land (n >2)] \Leftrightarrow [ n \in  \{3, 4, 5, 6, ....\}$]}\\
   \hspace*{12.5cm} $\blacksquare$
	\end{pindent}


	\item 
	\begin{enumerate}	
\item Write Python code to determine the how many integers between 0 and n (inclusive) are expressible as the sum of \textbf{squares} of two (possibly equal) positive natural numbers in at least two different ways. For example, $50 = 5^2 + 5^2 = 7^1 + 1^1$ is expressible as the sum of squares of two positive natural numbers in at least two different ways. On the other hand, the only way to express $2$ as a sum of squares of positive natural number is $2 = 1^2+1^2$, and $3$ is not expressible as a sum of squares of two positive natural numbers at all. Submit the code as \texttt{a5.py}, and submit the relevant parts of the output which shows your answer for $n = 100$ (this could be just one line), explaining clearly what it means, as part of your answer to this question. Justify your answer briefly (a complete formal proof is not required.)

\textbf{Solution:}

The output for \texttt{n = 100} is:\\
 \texttt{There are 3 numbers expressible as a sum of two squares in two different ways between 1 and 100}.


The script works by checking whether each number between $1$ and $n$ is expressible as a sum of squares in at least two different ways. For each  k, we consider all the possibilities $i^2+(k-i)^2$ for $i < (k-i)$ for $0 < i \le \ceil{\sqrt{n/2}}$, which covers all the possibilities.

\item What is a tight upper bound on the  number of comparison operations (i.e., $==$, $<$, $<=$, $>$, $>=$  ) that are executed when running your algorithm for a given \texttt{n}? Ignore the comparison operations that are performed when running functions from the \texttt{math} module.//

\textbf{Solution:}

 The  loop in \texttt{is\_two\_sum\_sq} runs for  $\sqrt{n/2}$  iterations at 2 comparisons each  when checking whether a solution has been found, and there are at most $2$ times that \texttt{found} is compared to $2$, so the upper bound there is  $2\sqrt{n/2}+2$. Checking whether $\{1,2,3, ..., n\}$  are each expressible as a sum of two squares in two different ways takes

		$$(2\sqrt{1/2}+2)+ (2\sqrt{2/2}+2) + (2\sqrt{3/2}+2) + ... + (2\sqrt{n/2}+2) = 2n + (2/\sqrt{2})\sum_{i=1}^n{\sqrt{i}}$$

This is a tight upper bound, and would be sufficient as an answer. (Using a formula from \url{http://mathforum.org/library/drmath/view/65309.html}, you can get that the asymptotic upper bound is $\mathcal{O}(n^{3/2})$ in this case.)


The analysis  would be more straightforward if I didn't try to minimize the number of iterations in line 14. If I had used $n$ iterations instead of $\sqrt{n/2}$ iterations in \texttt{is\_two\_sum\_sq}, I would be performing at most $2k+2$ comparisons for each $k$, and so in total the upper bound would be 
	$$\sum_{i=1}^{n} [2i+2] =  n(n+1)+2n = n^2+3n$$



	\end{enumerate}
	\item Prove that
		$$\exists k \in \mathbb{N}, \forall n \in \mathbb{N}, [n > k] \implies [1000n^2 + 10\le n^4].$$
\textit{Hints: you can divide both sides by $n^2$ and preserve the inequality, since $n^2$ is always positive. Reminder: $n^a/n^b = n^{a-b}$. You can then figure out (in your rough work) what value of k you need}. Note that $10/n^2 < 1$ if $n \ge 4$. Justify every step, and use the detailed structured proof format.\\

\textbf{Solution:}

\begin{pindent}
	Let k = 32 \\
	Then $k \in \mathbb{N}$ \just{$32 \in \mathbb{N}$}
	\begin{assumption}{$n \in \mathbb{N}$}
		\begin{assumption}{$n > k$} 
			Then $10/n^2 < 1$\just{$n^2 > 32^2 = 1024 > 10$}\\
			Then $1000 + 10/n^2 < 1001 < 1023 < 32^2 < n^2$ \just{$10/n^2 < 1, n > 32$}\\
			Then $1000 + 10/n^2 < n^2$\just{transitivity of $<$}\\
			Then $1000n^2 + 10 < n^4$\just{multiply both sides by $n^2$}
		\end{assumption}{Then $[n > k] \implies  1000n^2 + 10 < n^4$\just{introduce implication}}
	\end{assumption}{Then $\forall n \in \mathbb{N}, [n > k] \implies  1000n^2 + 10 < n^4$\just{introduce universal}}\\
   \hspace*{12.5cm} $\blacksquare$
\end{pindent}

\newpage
	\item Let $\mathbb{R^{+}}$ be the set of positive real numbers and $\mathbb{N}^+$ be the set of positive natural numbers.  Prove that
		$$\forall a \in \mathbb{R^{+}}, \forall b \in \mathbb{R^{+}}, \forall p_1 \in \mathbb{N^{+}}, \forall p_2 \in \mathbb{N^{+}}, [p_1 \le p_2] \implies a n^{p_1} \in \mathcal{O}(b n^{p_2}.)$$ 

You may not use, without proof, any properties of big-Oh, other than its definition. Justify every step, and use the detailed structured proof format. \\

\textbf{Solution:}



\begin{pindent}


\begin{assumption}{$p_1 \in \mathbb{N^{+}},  p_2 \in \mathbb{N^{+}}, a \in \mathbb{R^{+}}, b \in \mathbb{R^{+}}$}
	\begin{assumption}{$p_1 \le p_2$}
		Let $c = \frac{a}{b}$ \just{$b \neq 0$ since $b \in \mathbb{R^{+}}$} \\
		Then $c \in \mathbb{R^{+}}$ \just{both a and b are $\in \mathbb{R^{+}}$ and it is closed under division} \\
		Let $B = 1$ \\
		Then $B \in \mathbb{N}$ \just{$1 \in \mathbb{N}$}
		\begin{assumption}{$n \in \mathbb{N}$}
			\begin{assumption}{$n \ge B$}
				Then $n^{p_2-p_1} \ge 1$\just{$p_2-p_1 \ge 0, n > 1 > 0$}\\
				Then $n^{p_2} \ge n^{p_1}$\just{multiply  both sides by $n^{p_1} > 0$ (since $n>0$)}\\
				Then $n^{p_1} \le n^{p_2}$\just{algebra}\\
				Then $a n^{p_1} \le a n^{p_2}$ \just{multiply both sides by $a>0$}\\
				Then $a n^{p_1} \le \frac{a}{b} b  n^{p_2}$ \just{algebra}\\
				Then $a n^{p_1} \le c ( b  n^{p_2})$ \just{substitution}
			\end{assumption}{Then $n \ge B \implies a n^{p_1} \le c ( b  n^{p_2})$ \just{introduce implication}}
		\end{assumption}{Then $\forall n \in \mathbb{N}, n \ge B \implies a n^{p_1} \le c ( b  n^{p_2})$ \just{introduce universal}}\\
		Then $\exists B \in \mathbb{N}, \exists c \in \mathbb{R^{+}}, \forall n \in \mathbb{N}, n \ge B \implies a n^{p_1} \le c ( b  n^{p_2})$ \just{introduce existential, B and c provided above}\\
		Then $a n^{p_1} \in \mathcal{O}(b n^{p_2})$ \just{definition of big-Oh}
	\end{assumption}{Then $[p_1 \le p_2] \implies [a n^{p_1} \in \mathcal{O}(b n^{p_2})]$ \just{introduce implication}}
\end{assumption}{Then $\forall a \in \mathbb{R^{+}}, \forall b \in \mathbb{R^{+}}, \forall p_1 \in \mathbb{N^{+}}, 	\forall p_2 \in \mathbb{N^{+}}, [p_1 \le p_2] \implies a n^{p_1} \in \mathcal{O}(b n^{p_2}) $\just{introduce universal}}\\


   \hspace*{13.5cm} $\blacksquare$
\end{pindent}


\end{enumerate}


\end{document}