\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{2: More Counting}{Due Friday, Week 1}

Do \textbf{two} of the \textbf{three} problems below!   Prove all of your claims.  If you've seen some of these problems before, try the ones you have not seen first.


\begin{enumerate}
\item   Find the flaw in the following proof:
\begin{theorem}
All ponies are the same color.
\end{theorem}
\textbf{Proof}.  We proceed by induction.  Specifically, let $P(n)$ be the claim ``In any collection of $n$ ponies, all of these ponies are the same color.''  

Base case: we want to prove $P(1)$.  But $P(1)$ is trivially true; in any collection made of one pony, all of the ponies in that set are the same color.

Inductive case: we want to prove that $P(n) \Rightarrow P(n+1)$.  In other words, we want to prove that whenever $P(n)$ is true, $P(n+1)$ is also true.  To do this: assume that $P(n)$ is true, i.e.\ that in any set of $n$ ponies, all of those ponies are the same color.  With this assumption, we want to prove that $P(n+1)$ is true: i.e. that in any set of $n+1$ ponies, all of these ponies are also the same color.

To do this: take any set of $n+1$ ponies, and write them as the set $\{p_1, \ldots p_{n+1}\}$.  Break this set up into two subsets of size $n$: the subset $\{p_1, \ldots p_n\}$ and the subset $\{p_2, \ldots p_{n+1}\}$.  These are both sets of size $n$: by our inductive hypothesis, they are both the same color.  But these sets share the ponies $p_2,\ldots p_n$ in common!  Therefore, whatever color our first set  $\{p_1, \ldots p_n\}$ is \textbf{must be} the same color as the second set  $\{p_2, \ldots p_{n+1}\}$, because they overlap!  Therefore, all of our $n+1$ ponies are the same color, and we've proven that $P(n+1)$ is true (given our assumption $P(n)$.)

So: we've proven that $P(1)$ is true, and that $P(n) \Rightarrow P(n+1)$.  Therefore, by induction, we've proven that our claim $P(n)$ is true for all $n$; if we let $n$ be the total number of ponies in existence, this proves our claim.

\item  Prove that every fourth Fibonacci number is a multiple of 3.  (Hint: show that $f_{4k+4} = 5f_{4k} + 3f_{4k-1}$, for any $k$.)

\item  A \textbf{lattice path} in the plane $\mathbb{R}^2$ is a path joining integer points via steps of length 1 either upward or rightward.  Show that for any $a,b \in \mathbb{N}$, the number of lattice paths from $(0,0)$ to the point $(a,b)$ is $\binom{a+b}{a}$.


\end{enumerate}










\end{document}