\documentclass[11pt]{article} % 

\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\newcommand{\cP}{{\cal P}}
\newcommand{\N}{{\bf N}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\R}{{\bf R}}
\newcommand{\Q}{{\bf Q}}
\newcommand{\points}[1]{{\it (#1 Points)}}
\newcommand{\tpoints}[1]{{\bf #1 Total points.}}

\begin{document} 
\openup 1 \jot

\noindent
{\bf Math 214 Foundations of Mathematics Homework 5 \hfill
Your Name}

\medskip
Ten  points for each problem. 

\begin{enumerate}
\item For each of the following sets, determine whether it is well-ordered and show your reasons. 

\medskip
\centerline{(a) \ $S=\{n\in \N: n \hbox{ is even}\}$.
\qquad (b) \ $T=\{x\in \Q: x \ge 0 \}$. }


\item  (a) Prove that  $\sum_{k=0}^n (2 k + 1) = (n+1)^2$
for all $n \in \N$.


(b) Prove that $\sum_{k=1}^{n} \frac{1}{(k+2)(k+3)}=\frac{n}{3n+9}$ for every positive integer $n$. 


\item  (a) Determine (with proof) the set of integers $n$
such that  $n \geq 3$, $n^3 \leq 3^n$. 

(b)  Prove that $1 + \frac{1}{4} + \cdots + \frac{1}{n^2} \le 2 - \frac{1}{n}$ for all $n \in \N$.

\item  (a) Prove that $7|(3^{2n}-2^n)$ for all $n\in \N$.

(b)  Prove that $12| (n^4-n^2)$ for all  $n \in \N\cup \{0\}$.

\item A sequence $\{a_n\}$ is defined recursively by $a_1=1, a_2=4, a_3=9$, and 
$$a_n=a_{n-1}-a_{n-2}+a_{n-3}+2(2n-3)$$ for $n\ge 4$.  
Conjecture a formula for $a_n$ and prove that your conjecture is correct. 



\item (Extra 10 points)
Show that an positive integer is a multiple of $9$ if and only if the sum of all digits of the integer 
is a multiple of $9$. 

[Hint: Prove that $10^n \equiv 1 (\hbox{ mod }  9)$.]


\end{enumerate}
\end{document}


