% 
% hw2.tex
%
%   This is LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}
\usepackage{mathtools}
\usepackage{amsthm,amsmath, amssymb}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}

\renewcommand{\labelitemi}{$\bullet$}
\renewcommand{\labelitemii}{$\bullet$}

\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Homework 6: due 2/19/2019\\[2ex]
       \rm\normalsize ECS 20 (Winter 2019)}
%\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle
%\section*{\underline{Homework 4 - For 10/26/2017}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1: total 20 points (5 points for each of a to d)} 
\begin{itemize}
\item[a)] Show that $2x-10$ is $\Theta(x)$.
\item[b)] Show that $4x^2 + 8x - 6$ is $\Theta(x^2)$.
\item[c)] Show that $\lfloor x + \frac{2}{7} \rfloor$ is $\Theta(x)$.
\item[d)] Show that $\log_{4}(x)$ is $\Theta (\log_{7}(x))$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2: 10 points} 
 Show that $x^2$ is $\mathcal{O}(x^4)$ but that  $x^4$ is not $\mathcal{O}(x^2)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3: 10 points} 

Let $a$, and $b$ be two strictly positive integers and let $x$ be a real number. Show that:
\begin{eqnarray*}
\floor*{ \frac{ \floor*{ \frac{x}{a}}}{b} } = \floor*{\frac{x}{ab}}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4: 10 points}

Let $x$ be a positive real number. Solve $\lfloor x \lfloor x \rfloor \rfloor = 5$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5: 10 points}

Let $n$ be a natural number. Show that if $n$ is a perfect square, then $2n$ is not a perfect square.

\noindent \textit{(Reminder: a natural number $a$ is a perfect square if there exists a natural number $k$ such that $n=k^2$.)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Extra Credit: 5 points}

Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ that satisfy:

$\forall (x,y) \in \mathbb{R}^2, f(x)f(y) + f(x+y) = xy$

\end{document}

