\documentclass{article}

\usepackage{amssymb}



\begin{document}
\noindent{\LARGE Math 117, Winter 00: Homework 1}
\\ \\
\noindent {\it Remark.} The following symbols are used:

\noindent $\forall$ means "for all". For example, $\forall n>2$
means "for all $n$ greater than 2".

\noindent $\mathbb{N}$ is the set of natural numbers, $\{
1,2,3,...\}$.

\noindent $\mathbb{Z}$ is the set of integers, $\{ 0,\pm 1,\pm
2,...\}$.

\noindent $\in$ means "is an element of", so for example $n\in
\mathbb{N}$ means "$n$ is an element of $\mathbb{N}$", i.e. "$n$
is a natural number".
\\ \\

\noindent {\bf 2A/E1.} Prove that $\forall n\geq 4: n!\geq 2^n.$
\\

\noindent {\it Proof.} We have to start our induction at $n=4$.
Since $4!=24$ and $2^4=16$, $P(4)$ holds. Suppose $P(n)$ holds.
Then $$(n+1)!=(n+1)\times n!\geq (n+1)\times 2^n>2\times
2^n=2^{n+1}.$$

Thus, $P(n+1)$ also holds. Here the first inequality is the
induction assumption and the second inequality follows since
$n\geq 4$, so certainly $(n+1)>2$.
\\ \\

\noindent {\bf 2A/E4.} (i) Prove that $\forall n\geq 1$:
$$\frac{1}{1-x}=1+x+...+x^{n-1}+\frac{x^n}{1-x}.$$

(ii) Substituting $x=2$ in (i), prove that $\forall n\geq1$:
$$1+2+...+2^{n-1}=2^n-1.$$ {\it Proof.} (i) For $n=1$, the
statement is that $\frac{1}{1-x}=1+\frac{x}{1-x}$, which is true.
Suppose the statement holds for $n$. Then
$$1+x+...+x^{n-1}+x^n+\frac{x^{n+1}}{1-x}=1+x+...+x^{n-1}+\frac{x^n-x^{n+1}}{1-x}+\frac{x^{n+1}}{1-x}$$
$$=1+x+...+x^{n-1}+\frac{x^n}{1-x}=\frac{1}{1-x}.$$

(ii) We could do this directly by induction, but it is faster and
easier to substitute $x=2$ in (i). We get
$$\frac{1}{1-2}=1+2+...+2^{n-1}+\frac{2^n}{1-2}$$ $$\Rightarrow
-1=1+2+...+2^{n-1}-2^n$$ $$\Rightarrow 2^n-1=1+2+...+2^{n-1}.$$

{\newpage} \noindent {\bf 2A/E10.} The Tower of Hanoi
\\

Here is the main idea of this problem: if you know how many moves
you need to move $n$ disks from one pole to another, then you can
get the number of moves for $n+1$ disks from that as follows.
\\ \\
a) move the top $n$ disks to the middle pole using the third pole
as the "spare".
\\ \\
b) move the $(n+1)^{st}$ disk from the first pole to the third
pole.
\\ \\
c) move the $n$ disks from the middle pole to the third pole,
using the first one as the spare this time.
\\

So how many moves do you need? For 1 disk, you obviously need 1
move. If for $n$ disks you need $k$ moves, then by the above
explanation you need $2k+1$ moves for $n+1$ disks ($k$ for a), 1
for b), $k$ for c)). So for two disks you need $2+1=3$, for three
$2\times 3+1=7$, for four $2\times 7+1=15$ and so on. Looking at
this pattern, we claim:
\\

The number of moves needed to move $n$ disks is $2^n-1$.
\\ \\
{\it Proof.} For 1 disk we need 1 move, so the statement is true
for $n=1$.
\\

Suppose now the statement holds for $n$ disks. For $n+1$ disks, we
first move $n$ disks, then one disk, and then $n$ disks. The total
number of moves is thus $$(2^n-1)+1+(2^n-1)=2\times
2^n-1=2^{n+1}-1.$$

Question: How many moves does it take to move $n$ disks if there
are four poles? Five? Is there a general formula?
\\ \\

\noindent{\bf 2A/E14.} What's wrong with the Baby Theorem?
\\

When you do induction, you can only use the induction assumption
on the {\bf first} $n$ elements. In the proof in the book, the set
$R$ of the $n$ babies to the right includes the elements 2 through
$n+1$, and we can't use our induction assumption on the $n+1^{st}$
baby. {\bf Don't assume what you're trying to prove!!}

Alternatively, you could just say that in the case $n=2$, there is
no overlap, so you can't compare the set $L$ and the set $R$.

{\newpage}

\noindent{\bf 2B/E4.} Prove that the sum of the interior angles of
an $n$-sided convex polygon is $180^\circ \times (n-2)$.
\\ \\
{\it Proof.} It obviously doesn't make sense to talk about an
$n$-sided convex polygon if $n<3$, so we'll start at $n=3$. In
this case, we have a triangle, and the sum of the interior angles
is $180^\circ =180^\circ \times (3-2)$. So the statement holds for
$n=3$.

If it holds for all $n$-sided convex polygons, let's consider one
with $n+1$ sides (and vertices). Now take any three adjacent
vertices and connect the outer two with a line. What you get is an
$n$-sided polygon and a triangle. Also, to add up all the interior
angles of the $n+1$-sided polygon is the same as to add up all the
interior angles of the $n$-sided polygon and the triangle. Thus,
the sum of the interior angles of the $n+1$-sided polygon is
$$180^\circ \times (n-2)+180^\circ =180^\circ \times (n-1).$$
\\ \\

\noindent{\bf 19A/E1.} Prove that the sum of the elements in the
$n$th row of Pascal's triangle is $2^n$ for each $n$. How many
subsets of a set with $n$ elements are there?
\\

{\it Proof.} The $n$th row of Pascal's triangle consists of
$\left(\begin{array}{c}n \\ 0\end{array}
\right)$,$\left(\begin{array}{c}n \\ 1\end{array}
\right)$,...,$\left(\begin{array}{c}n \\ n\end{array} \right)$. By
the Binomial theorem, $$2^n=(1+1)^n=\left(\begin{array}{c}n \\
0\end{array} \right)+...+\left(\begin{array}{c}n \\ n\end{array}
\right).$$

By a theorem in the book (on page 294), if $S$ is a set with $n$
elements, then it has $\left(\begin{array}{c}n
\\ r\end{array} \right)$ subsets with $r$ elements. Since all
sizes between 0 and $n$ elements are possible for the subsets (0
would be the empty set and $n$ all of $S$), the total number of
subsets is the sum we just calculated, $2^n$. Try to prove this
directly by induction on the number $n$ of elements of the set
(not too hard).

\end{document}