\documentclass{article}

\usepackage{amsmath, amssymb, amsthm}
\usepackage[margin=0.5in]{geometry}

\newcommand{\scs}[1]{\begin{scshape}#1\end{scshape}}
%\newcommand{\inv}{^{-1}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}

\newtheorem*{proposition}{Proposition}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{problem}{}
\newtheorem*{solution}{Solution}

\newcommand{\sol}[1]{\begin{solution}#1\end{solution}}
\newcommand{\prob}[1]{\begin{problem}#1\end{problem}}
\newcommand{\dfn}[1]{\begin{definition}#1\end{definition}}

\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\m}[1][n]{\left(\text{mod}\ #1\right)}

\newcommand{\vsp}{\vspace{.1in}}

\begin{document} \pagestyle{empty} \begin{flushleft}


\scs{Name(s):} Solutions

\scs{Math 301 \hfill Induction, Round Two \hfill \today}

\prob{Find the flaw(s) in the following induction proof.
\begin{proposition}
All dogs are the same color.
\end{proposition}

\begin{proof}[Proof by induction]

The proposition may be interpreted as saying that every set of $n$ dogs contains dogs of only one color.
We procede by induction on the number $n$.

\vsp

Base case: $n=1$.
This means that we have a set of just one dog. 
Obviously, if there's just one dog, then all dogs in the set are the same color.

\vsp

Iductive step: let $k \in \NN$ and suppose that any set of $k$ dogs consists of dogs of just one color.
Let $A$ be a set of $k+1$ dogs.
Let $a$ be one of the dogs in $A$.
Then the set $A-\{a\}$ is a set of $k$ dogs and hence they are all the same color (by the inductive hypothesis).
Let $b$ be another dog in $A$.
Similarly, $A-\{b\}$ is a set of $k$ dogs and thus all of these dogs are the same color.
Because $a \in A-\{b\}$ and $b \in A - \{a\}$ it follows that dog $a$ and dog $b$ are the same color as all the other dogs in $A$.
Hence $A$ consists of dogs of only one color.

\vsp

Therefore, by induction, all dogs are the same color.

\end{proof}
}

\sol{
The problem here is that the inductive step works only for a set $A$ with cardinality 3 or greater.
In fact, it is not true that every set of two dogs contains dogs of only one color, so it makes sense that this does not follow from the base case.
}


\prob{
Use induction to prove that for any non-negative integer $n$,
any set with $n$ elements has $2^n$ subsets.
}

\begin{proof}[Proof by induction]
Base case: $n=0$.
The only set with zero elements is $\emptyset$.
The only subsets of $\emptyset$ is $\emptyset$.
Hence every subset with zero elements has $2^0=1$ subset.

\vsp

Now suppose that $k$ is a non-negative integer and every set with $k$ elements has $2^k$ subsets.
Let $A$ be a set with $k+1$ elements.
Let $a \in A$ (we know that $A$ has at least one element because $k+1 \geq 1$).
Then $A - \{a\}$ is a set with $k$ elements and by hypothesis this set has $2^k$ subsets.
These are exactly the subsets of $A$ that do not contain $a$.
It remains to count the number of subsets of $A$ that do contain $a$.
Each such subset is a subset of $A-\{a\}$ with the element $a$ added in.
Thus there are $2^k$ subsets of $A$ that contain the element $a$.
Therefore $A$ has $2^k + 2^k = 2^{k+1}$ subsets in total.

\vsp

Therefore, by induction, a set with $n$ elements has $2^n$ subsets.

\end{proof}

\prob{
Prove that for any $n \in \NN$, $\displaystyle
1(2) + 2(3) + 3(4) + \dots + n(n+1) = \frac{n(n+1)(n+2)}{3}. $
}

\begin{proof}[Proof by induction]
Base case: $n=1$.
Then $1(2) = \frac{1(2)(3)}{3}$, so the base case holds.

Now let $k \in \NN$ and suppose that $1(2) + 2(3) + 3(4) + \dots + k(k+1) = \frac{k(k+1)(k+2)}{3}. $
Then \begin{align*}
1(2) + 2(3) + 3(4) + \dots + k(k+1) +(k+1)(k+2)
&= \frac{k(k+1)(k+2)}{3} +(k+1)(k+2) \\
&= \frac{k(k+1)(k+2)}{3} +\frac{3(k+1)(k+2)}{3} \\
&= \frac{(k+1)(k+2)(k+3)}{3}
\end{align*}

Therefore, by induction, $1(2) + 2(3) + 3(4) + \dots + n(n+1) = \frac{n(n+1)(n+2)}{3}$ for every $n\in \NN$.
\end{proof}

\prob{
Prove that for any $n \in \NN$, $\displaystyle
\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{n^2} \leq 2-\frac{1}{n}. $
}

\begin{proof}[Proof by induction]
Base case: $n=1$.
Then $\frac{1}{1} = 2-\frac{1}{1}$, so the base case holds.

\vsp

Now let $k\in \NN$ and suppose that $\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{k^2} \leq 2-\frac{1}{k}$.
Then \begin{align*}
\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{k^2} + \frac{1}{(k+1)^2} 
&\leq 2 - \frac{1}{k} +\frac{1}{(k+1)^2} \\
&= 2 - \frac{(k+1)^2 - k}{k(k+1)^2} \\
&= 2 - \frac{k^2 + k + 1}{k(k+1)^2} \\
&= 2 - \frac{k(k+1)}{k(k+1)^2} -\frac{1}{k(k+1)^2} \\
&\leq 2 - \frac{k(k+1)}{k(k+1)^2} \\
&= 2 - \frac{1}{k+1}.
\end{align*}

Therefore, by induction, $\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{n^2} \leq 2-\frac{1}{n}$ for all $n \in \NN.$
\end{proof}

\end{flushleft}
\end{document}