\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amsthm,amssymb,fullpage}
\begin{document}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newtheorem{theorem}{Theorem}
\section*{CS 70 homework 2 submission}
Your full name: PUT YOUR NAME HERE
\\
Your login name: PUT YOUR LOGIN NAME HERE
\\
Homework 2
\\
Your section number: PUT YOUR SECTION NUMBER HERE
\\
Your list of partners: LIST THE PEOPLE YOU WORKED WITH HERE (OR ``none'')
\begin{enumerate}
\item
Prove or disprove each of the following statements.
For each proof, state which of
the proof types (as discussed in the Lecture Notes) you used.
\begin{enumerate}
\item For all natural numbers $n$, if $n$ is even then $n^5$ is even.
YOUR ANSWER GOES HERE.
\item For all natural numbers $n$, $n^2-n+3$ is odd.
YOUR ANSWER GOES HERE.
\item For all real numbers $x,y$, if $\frac{x+y}{2}\ge 10$
then $x\ge 10$ or $y\ge 10$.
YOUR ANSWER GOES HERE.
\item For all real numbers $r$, if $r$ is irrational then $r^2$ is irrational.
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
For $n \in \N$ with $n\ge 2$, define $s_n$ by
\[ s_n = (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) \times \dots
\times (1 - \frac{1}{n}). \]
Prove that $s_n = 1/n$ for every natural number $n\ge 2$.
YOUR ANSWER GOES HERE.
\item
Let $a_n = 3^{n+2} + 4^{2n+1}$.
Prove that 13 divides $a_n$ for every $n \in \N$.
YOUR ANSWER GOES HERE.
\item
Prove by induction the exact number of moves required to carry out this
task in general, if there are $n$ disks on the original needle.
YOUR ANSWER GOES HERE.
Assuming
that the priests can move a disk each second, roughly how many centuries
does the prophecy predict before the destruction of the World?
YOUR ANSWER GOES HERE.
\item
Is it always possible for Dave to get the pizzas in order via some
sequence of moves, no matter how many pizzas he starts with?
YOUR ANSWER GOES HERE.
Prove your answer.
YOUR ANSWER GOES HERE.
\item
Assign a grade of A (correct) or F (failure) to the following proofs.
\begin{enumerate}
\item
{\bf Claim:} For every $n \in \N$, $n^2+3n$ is odd.
\begin{proof}
The proof will be by induction on $n$.\\
\emph{Base case:} The number $n=1$ is odd.\\
\emph{Induction step:} Suppose $k \in \N$ and $k^2 + 3k$ is odd. Then,
\[ (k+1)^2 + 3(k+1) = (k^2 + 2k + 1) + (3k +3) = (k^2 + 3k) + (2k+4) \]
is the sum of an odd and an even integer. Therefore, $(k+1)^2 + 3(k+1)$
is odd.
Therefore, by the principle of mathematical induction,
$n^2+3n$ is odd for all natural numbers $n$.
\end{proof}
YOUR ANSWER GOES HERE.
\item
{\bf Claim:} For every real number $x$,
if $x$ is irrational, then $2008x$ is irrational.
\begin{proof}
Suppose $2008x$ is rational. Then $2008x=p/q$ for some integers $p,q$
with $q\ne 0$. Therefore $x=p/(2008q)$ where $p$ and $2008q$ are integers
with $2008q \ne 0$, so $x$ is rational.
Therefore, if $2008x$ is rational, then $x$ is rational.
By the contrapositive, if $x$ is irrational, then $2008x$ is irrational.
\end{proof}
YOUR ANSWER GOES HERE.
\item
{\bf Claim:} For every $n \in \N$, if $n\ge 4$, then $2^n < n!$.
\begin{proof}
The proof will be by induction on $n$.\\
\emph{Base case:} $2^4=16$ and $4! = 24$ and $16 < 24$,
so the statement is true for $n=4$.\\
\emph{Induction step:} Suppose $k \in \N$ and $2^k < k!$.
Then
\[ 2^{k+1} = 2 \times 2^k < 2 \times k! < (k+1) \times k! = (k+1)!, \]
so $2^{k+1} < (k+1)!$.
By the principle of mathematical induction, the statement is true for
all $n\ge 4$.
\end{proof}
YOUR ANSWER GOES HERE.
\item
{\bf Claim:} For all $x,y,n\in \N$, if $\max(x,y)=n$, then $x \le y$.
\begin{proof}
The proof will be by induction on $n$.\\
\emph{Base case:} Suppose that $n=0$. If $\max(x,y)=0$
and $x,y\in \N$, then $x=0$ and $y=0$, hence $x \le y$.\\
\emph{Inductive hypothesis:} Assume that, whenever
we have $\max(x,y)=k$, then $x \le y$ must follow.\\
\emph{Inductive step:} We must prove that if $\max(x,y)=k+1$, then $x \le y$.
Suppose $x,y$ are such that $\max(x,y)=k+1$.
Then it follows that $\max(x-1,y-1)=k$, so by the inductive
hypothesis, $x-1 \le y-1$.
In this case, we have $x\le y$, completing the induction step.
\end{proof}
YOUR ANSWER GOES HERE.
\end{enumerate}
\end{enumerate}
\end{document}