
\documentclass[11pt]{article}
\addtolength{\textwidth}{\oddsidemargin}  %i.e., left margin
\addtolength{\textwidth}{0.75in}
\addtolength{\textheight}{1in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}

\begin{document}
\begin{center}
Intro to Mathematical Reasoning (Math 300) -- 
Homework 5\footnote{Version 2/16/04}
\end{center}

\begin{enumerate}
\item Textbook, problem 3.2.3.
\item Textbook, problem 3.2.6.

\item Prove: For all real numbers $x \geq -1$ and for all nonnegative integers
$n$, $(1+x)^n \geq 1+nx$.
\item Prove that for all nonnegative integers $n$, $\sum_{i=1}^{2^n} \frac{1}{i} \geq 1+\frac{n}{2}$.  (It is strongly recommended that you test this out for
some small values of $n$ before trying to prove it.  Also, in your proof
you may use the following lemma without proof: For all positive integers $k$,
and all lists $b_1,\ldots,b_k$ of real numbers satisfying
$b_1 \geq b_2 \geq \cdots \geq b_{k-1} \geq b_k$, we have
$\sum_{j=1}^k b_j \geq kb_k$.)
\item Let $a,b$ be real numbers.  Let $c_1,c_2,c_3,\ldots$
be an infinite sequence of real numbers
such that for each positive integer $k$, $c_k=ak-b$.
For each positive integer $n$, let $s_n=\sum_{k=1}^n c_k$.
Prove that for each positive integer $n$, $s_n=\frac{a}{2}n^2+(\frac{a}{2}-b)n$.

\item
Let $a_0,a_1,a_2, \ldots $ be an infinite sequence of real numbers
such that for $n \geq 3$,
$a_n = a_{n-1}+2a_{n-2}$.  Prove that for each $n \geq 0$,
if $n$ is even then $a_n=\frac{1}{3}(2^n(a_0+a_1)+2a_0-a_1)$
and if $n$ is odd then 
$a_n=\frac{1}{3}(2^n(a_0+a_1)+a_1-2a_0)$.
\item Prove: For any integer $n$ and for any list $A_1,\ldots,A_n$ where
each $A_i$ is a set,
if for all $i \in \{1,2,\ldots, n\}$ and $j \in \{1,2,\ldots,n\}$,
we have $A_i \subseteq A_j$ or $A_j \subseteq A_i$ then
then there is a set $k \in \{1,2,\ldots,n\}$
such that $A_k \subseteq A_i$ for all $i \in \{1,2,\ldots,n\}$.
\end{enumerate}


\end{document}










