<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{article}
\usepackage{fullpage,amsmath}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{mathtools}

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



\title{CSC165, Summer 2014\\
Assignment 5\\
Weight: 8\% \\
Due Jul. 25th, 2:00 p.m.}
\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 &lt; a &lt; 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.)

	\item  Prove that
		$$\forall n \in \mathbb{N}, [n&gt;2 \implies n! &lt; 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.)

	\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.)

\item What is a tight upper bound on the  number of comparison operations (i.e., $==$, $&lt;$, $&lt;=$, $&gt;$, $&gt;=$  ) 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.


	\end{enumerate}
	\item Prove that
		$$\exists k \in \mathbb{N}, \forall n \in \mathbb{N}, [n &gt; 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 &lt; 1$ if $n \ge 4$. Justify every step, and use the detailed structured proof format.


	\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.



\end{enumerate}


\end{document}
</pre></body></html>