\documentclass {exam}
\pagestyle {headandfoot}
\lfoot {\oddeven {}{Page \thepage \space of \numpages }}
\cfoot {}
\rfoot {\oddeven {Page \thepage \space of \numpages }{}}
\pointsinmargin \boxedpoints \addpoints
\newcommand \solution {\par \textbf {Solution:}\enspace }
\newcommand \onlyif {\mathbin {\rightarrow }}
\newcommand \st
 {\mathrel {\mathstrut \smash {\lower 0.5 ex \hbox {$\vdots $}}}}
\newcommand \at {\mathclose {;}\;}
\begin {document}
\noindent \textbf{MATH 112}\hfill
\textbf{Week 2 homework}\hfill
\textbf{2003 August 12}
\vskip 12pt plus 4pt minus 4pt
\begin {questions}
\question
Suppose that $f\colon A \to B$ and $g\colon B \to C$ are functions,
and consider their composition $g \circ f\colon A \to C$.
\begin {parts}
\part [1] \label {injective}
If $f$ and $g$ are one-to-one, does it follow that $g \circ f$ is one-to-one?
If not, give a counterexample.
\solution
Yes, it does follow.

Suppose that $x$ and $y$ are any distinct elements of $A$.
Because $f$ is one-to-one, $f(x)$ and $f(y)$ are distinct elements of $B$.
Then because $g$ is one-to-one,
$g(f(x))$ and $g(f(y))$ are distinct elements of $C$.
This means that $(g \circ f)(x)$ and $(g \circ f)(y)$
are distinct elments of $C$,
so $g \circ f$ is one-to-one.
\part [1] \label {surjective}
If $f$ and $g$ are onto, does it follow that $g \circ f$ is onto?
If not, give a counterexample.
\solution
Yes, it does follow.

Suppose that $c$ is any element of $C$.
Because $g$ is onto, $c = g(b)$ for some element $b$ of $B$.
Then because $f$ is onto, $b = f(a)$ for some element $a$ of $A$.
This means that $c = g(f(a)) = (g \circ f)(a)$, so $g \circ f$ is onto.
\part [1]
If $f$ and $g$ are invertible, does it follow that $g \circ f$ is invertible?
If not, give a counterexample.
\solution
Yes, it does follow.

Since $f$ and $g$ are invertible, they have inverses $f^{-1}$ and $g^{-1}$.
Notice that $f^{-1} \circ g^{-1}$ makes sense.
If $a$ is an element of $A$,
then $(f^{-1} \circ g^{-1})\bigl((g \circ f)(a)\bigr)
= f^{-1}\bigl(g^{-1}\bigl(g(f(a))\bigr)\bigr) = f^{-1}(f(a)) = a$;
and if $c$ is an element of $C$,
then $(g \circ f)\bigl((f^{-1} \circ g^{-1})(c)\bigr)
= g\bigl(f\bigl(f^{-1}(g^{-1}(c))\bigr)\bigr) = g(g^{-1}(c)) = c$.
This means that $f^{-1} \circ g^{-1}$ is the inverse of $g \circ f$,
so of course $g \circ f$ is invertible.
You can also prove this by using parts \ref{injective} and \ref{surjective},
since a function is invertible if and only if it's both one-to-one and onto.
\part [2] \label {one-to-one}
Show that, if $g \circ f$ is one-to-one, then $f$ is one-to-one.
Give an example where $g \circ f$ is one-to-one but $g$ is not.
\solution
Suppose that $g \circ f$ is one-to-one,
and suppose that $x$ and $y$ are any elements of $A$.
If $f(x) = f(y)$, then of course $g(f(x)) = g(f(y))$.
This means that $(g \circ f)(x) = (g \circ f)(y)$,
so $x = y$ since $g \circ f$ is one-to-one.
This shows that $f$ is one-to-one.

For the example,
let $A$ be $\{0,1\}$, let $B$ be $\{3,4,5\}$, and let $C$ be $\{6,7,8\}$.
Then let $f(0)$ be $3$ and $f(1)$ be $4$;
let $g(3)$ be $6$, $g(4)$ be $7$, and $g(5)$ be $7$.
Then $g \circ f$ is one-to-one, but $g$ isn't.
The example in part \ref{invertible} would also work.
\part [2] \label {onto}
Show that, if $g \circ f$ is onto, then $g$ is onto.
Give an example where $g \circ f$ is onto but $f$ is not.
\solution
Suppose that $g \circ f$ is onto,
and suppose that $c$ is any element of $C$.
Because $g \circ f$ is onto,
$c = (g \circ f)(a)$ for some element $a$ of $A$.
This means that $c = g(f(a))$, so $g$ is onto.

For the example,
let $A$ be $\{0,1,2\}$, let $B$ be $\{3,4,5\}$, and let $C$ be $\{6,7\}$.
Then let $f(0)$ be $3$, $f(1)$ be $4$, and $f(2)$ be $4$;
let $g(3)$ be $6$, $g(4)$ be $7$, and $g(5)$ be $7$.
Then $g \circ f$ is onto, but $f$ isn't.
The example in part \ref{invertible} would also work.
\part [2] \label {invertible}
Show that, if $g \circ f$ is invertible,
then $f$ is one-to-one and $g$ is onto.
Give an example where $g \circ f$ is invertible,
but $f$ is not onto and $g$ is not one-to-one.
\solution
Suppose that $g \circ f$ is invertible, so that $(g \circ f)^{-1}$ exists.
Then suppose that $x$ and $y$ are any elements of $A$.
Then $x = (g \circ f)^{-1}\bigl((g \circ f)(x)\bigr)
= (g \circ f)^{-1}\bigl(g(f(x))\bigr)$
and $y = (g \circ f)^{-1}\bigl((g \circ f)(y)\bigr)
= (g \circ f)^{-1}\bigl(g(f(y))\bigr)$.
Thus if $f(x) = f(y)$, then $x = y$,
so $f$ is one-to-one.
Next, suppose that $c$ is any element of $C$.
Then $c = (g \circ f)\bigl((g \circ f)^{-1}(c)\bigr)
= g\bigl(f\bigl((g \circ f)^{-1}(c)\bigr)\bigr)$,
so $g$ is onto.
You can also prove this by using parts \ref{one-to-one} and \ref{onto},
since an invertible function is both one-to-one and onto.

For the example,
let $A$ be $\{0,1\}$, let $B$ be $\{3,4,5\}$, and let $C$ be $\{6,7\}$.
Then let $f(0)$ be $3$ and $f(1)$ be $4$;
let $g(3)$ be $6$, $g(4)$ be $7$, and $g(5)$ be $7$.
Then $g \circ f$ is invertible, but $f$ isn't onto and $g$ isn't one-to-one.
\end {parts}
\question [0]
Let $f$ be a function from $A$ to $B$.
Suppose that if $f^{-1}(S) = f^{-1}(T)$, then $S = T$,
whenever $S$ and $T$ are subsets of $B$.
Such a function is called an \textbf{epimorphism}.
Show that epimorphisms and surjections are the same thing;
that is, every epimorphism is a surjection,
and evey surjection is an epimorphism.
\solution
First suppose that $f$ is a surjection.
Let $S$ and $T$ be any subsets of $B$,
and suppose that $f^{-1}(S) = f^{-1}(T)$.
Given any element $b$ of $B$,
$b = f(a)$ for some element $a$ of $A$ since $f$ is a surjection.
Thus if $b \in S$, then $a \in f^{-1}(S)$,
so $a \in f^{-1}(T)$, so $f(a) \in T$.
That is, $S$ is a subset of $T$.
On the other hand, if $b \in T$, then $a \in f^{-1}(T)$,
so $a \in f^{-1}(S)$, so $f(a) \in S$.
That is, $T$ is a subset of $S$.
Therefore, $S = T$, so $f$ is an epimorphism.

On the other hand, suppose that $f$ is \textit{not} a surjection.
That is, for some element $b$ of $B$,
$b$ does not belong to the range of $f$.
In other words, $f^{-1}(\{b\})$ is empty.
So let $S$ be $\{b\}$, and let $T$ be the empty set.
Then $f^{-1}(S)$ and $f^{-1}(T)$ are both empty,
even though $S$ and $T$ are distinct.
Therefore, $f$ is not an epimorphism either.

[\textsl{Very few people got anywhere on this problem,
so I made it extra credit.}]
\question [3]
Suppose that $p$ implies $q$.
That is, if you know $p$, then you can deduce $q$.
What is the \textbf{converse} of this implication?
What is the \textbf{contrapositive}?
Which of these can you assume to be correct?

\solution
The converse says that $q$ implies $p$.
The contrapositive says that $\neg{q}$ implies $\neg{p}$.
If the original implication is correct,
then the contrapositive is also correct.
\question [2] \label {disjunctive} [\textsl{Disjunctive syllogism.}]
Show that $p \vee q$ and $\neg{p}$ together imply $q$.
That is, if you know $p \vee q$ and you know $\neg{p}$,
then you can deduce $q$.
\solution
Since you know $p \vee q$,
use $\vee$ elimination and consider $p$ and $q$ separately.
In the case of $p$, combine this with $\neg{p}$
and use $\neg$ elimination to derive a contradiction $F$.
Then use $F$ elimination on this to derive whatever you want,
in this case $q$.
In the case of $q$, you have $q$ right away.
In either case, you have $q$,
so $\vee$ elimination gives you $q$ absolutely.

\begin {tabular}{rl}
\qquad \qquad \qquad $p \vee q$ & Given \\
\multicolumn{2}{c}{\begin {tabular}{|rl|rl|}
\hline
$p$ & Hypothesis & $q$ & Hypothesis \\
$\neg{p}$ & Given & & \\
$F$ & $\neg$ elimination & & \\
$q$ & $F$ elimination & & \\
\hline
\end {tabular}} \\
$q$ & $\vee$ elimination \\
\end {tabular}

[\textsl{You can also solve this with a truth table,
by showing that $\bigl((p \vee q) \wedge \neg{p}\bigr) \onlyif q$
is a tautology.}]
\question [2] [\textsl {Resolution.}]
Show that $p \vee q$ and $\neg{p} \vee r$ together imply $q \vee r$.
\solution
Since you know $p \vee q$,
use $\vee$ elimination and consider $p$ and $q$ separately.
In the case of $p$, combine this with $\neg{p} \vee r$
and use $\vee$ elimination again to consider $\neg{p}$ and $r$ separately.
In the subcase of $\neg{p}$, combine this with $p$
and use $\neg$ elimination to derive a contradiction $F$.
Then use $F$ elimination on this to derive whatever you want,
in this case $q \vee r$.
In the subcase of $r$,
use $\vee$ introduction (on the right) to get $q \vee r$.
In either subcase, you have $q \vee r$,
so $\vee$ elimination gives you $q \vee r$ in the case of $p$.
In the case of $q$, use $\vee$ introduction (on the left) to get $q \vee r$.
In either case, you have $q \vee r$,
so $\vee$ elimination gives you $q \vee r$ absolutely.

\catcode `\@ 11
\begin {tabular}{rl}
\qquad \qquad \qquad \qquad \qquad \qquad \qquad $p \vee q$ & Given \\
\multicolumn{2}{c}{\begin {tabular}{|rl|rl|}
\hline
$p$ & Hypothesis & $q$ & Hypothesis \\
\qquad \qquad \qquad \quad $\neg{p} \vee r$ & Given &
$q \vee r$ & $\vee$ introduction \\
\omit \vline \@multispan{2}{ }{\begin {tabular}{|rl|rl|}
\hline
$\neg{p}$ & Hypothesis & r & Hypothesis \\
$p$ & Above & $q \vee r$ & $\vee$ introduction\\
$F$ & $\neg$ elimination & & \\
$q \vee r $ & $F$ elimination & & \\
\hline
\end {tabular}} \vline & & \\
$q \vee r$ & $\vee$ elimination & & \\
\hline
\end {tabular}} \\
$q \vee r$ & $\vee$ elimination \\
\end {tabular}
\catcode `\@ 12

[\textsl{You can also solve this with a truth table,
by showing that $\bigl((p \vee q) \wedge (\neg{p} \vee r)\bigr)
\onlyif (q \vee r)$
is a tautology.}]
\question [2] [\textsl {Modus tollens.}]
Show that $p \onlyif q$ and $\neg{q}$ together imply $\neg{p}$.

\solution
By $\neg$ introduction, you always know $p \vee \neg{p}$,
so apply $\vee$ elimination to that
by considering $p$ and $\neg{p}$ separately.
In the case of $p$, combine this with $p \onlyif q$
and use $\onlyif$ elimination (modus ponens) to deduce $q$.
Then combine this with $\neg{q}$
and use $\neg$ elimination to derive a contradiction $F$.
Then use $F$ elimination on this to derive whatever you want,
in this case $\neg{p}$.
In the case of $\neg{p}$, you have $\neg{p}$ right away.
In either case, you have $\neg{p}$,
so $\vee$ elimination gives you $\neg{p}$ absolutely.

\begin {tabular}{rl}
\qquad \qquad \qquad $p \vee \neg{p}$ & $\neg$ introduction \\
\multicolumn{2}{c}{\begin {tabular}{|rl|rl|}
\hline
$p$ & Hypothesis & $\neg{p}$ & Hypothesis \\
$p \onlyif q$ & Given & & \\
$q$ & $\onlyif$ elimination & & \\
$\neg{q}$ & Given & & \\
$F$ & $\neg$ elimination & & \\
$\neg{p}$ & $F$ elimination & & \\
\hline
\end {tabular}} \\
$\neg{p}$ & $\vee$ elimination \\
\end {tabular}

[\textsl{You can also solve this with a truth table,
by showing that $\bigl((p \onlyif q) \wedge \neg{q}\bigr) \onlyif \neg{p}$
is a tautology.}]
\question [2] [\textsl {Hypothetical syllogism.}]
Show that $p \onlyif q$ and $q \onlyif r$ together imply $p \onlyif r$.

Hypothetically assume $p$.
Combine that with $p \onlyif q$ and use $\onlyif$ elimination to deduce $q$.
Then combine that with $q \onlyif r$
and use $\onlyif$ elimination to deduce $r$.
Then $\onlyif$ introduction gives you $p \onlyif r$ absolutely.

\begin {tabular}{rl}
\multicolumn{2}{c}{\begin {tabular}{|rl|}
\hline
$p$ & Hypothesis \\
$p \onlyif q$ & Given \\
$q$ & $\onlyif$ elimination \\
$q \onlyif r$ & Given \\
$r$ & $\onlyif$ elimination \\
\hline
\end {tabular}} \\
\ $p \onlyif r$ & $\onlyif$ introduction \\
\end {tabular}

[\textsl{You can also solve this with a truth table,
by showing that $\bigl((p \onlyif q) \wedge (q \onlyif r)\bigr)
\onlyif (p \onlyif r)$
is a tautology.}]
\question [3]
Show that $\forall{x}\, P(x) \vee \forall{y}\, Q(y)$
implies $\forall{x}\, \bigl(P(x) \vee Q(x)\bigr)$.
Is the converse also correct?

\solution
Consider an arbitrary variable $z$.
Use $\vee$ elimination on $\forall{x}\, P(x) \vee \forall{y}\, Q(y)$
and consider $\forall{x}\, P(x)$ and $\forall{y}\, Q(y)$ separately.
In the case of $\forall{x}\, P(x)$,
replace $x$ with $z$ and use $\forall$ elimination to get $P(z)$.
Then use $\vee$ introduction (on the left) to get $P(z) \vee Q(z)$.
In the case of $\forall{y}\, P(y)$,
replace $y$ with $z$ and use $\forall$ elimination to get $Q(z)$.
Then use $\vee$ introduction (on the right) to get $P(z) \vee Q(z)$.
In either case, you have $P(z) \vee Q(z)$,
so $\vee$ elimination gives you $P(z) \vee Q(z)$ absolutely.
Since $z$ was arbitrary,
$\forall$ introduction gives you $\forall{z}\, \bigl(P(z) \vee Q(z)\bigr)$,
which is the same as $\forall{x}\, \bigl(P(x) \vee Q(x)\bigr)$.

\catcode `\@ 11
\begin {tabular}{rl}
\multicolumn{2}{c}{\begin {tabular}{|rl|}
\hline
$z$ & Arbitrary \\
\qquad \qquad \qquad $\forall{x}\, P(x) \vee \forall{y}\, Q(y)$ & Given \\
\omit \vline \@multispan{2}{ }{\begin {tabular}{|rl|rl|}
\hline
$\forall{x}\, P(x)$ & Hypothesis & $\forall{y}\, Q(y)$ & Hypothesis \\
$P(z)$ & $\forall$ elimination & $Q(z)$ & $\forall$ elimination \\
$P(z) \vee Q(z)$ & $\vee$ introduction &
$P(z) \vee Q(z)$ & $\vee$ introduction \\
\hline
\end {tabular}} \vline \\
$P(z) \vee Q(z)$ & $\vee$ elimination \\
\hline
\end {tabular}} \\
\qquad \qquad \qquad \quad $\forall{z}\, \bigl(P(z) \vee Q(z)\bigr)$ &
$\forall$ introduction \\
\end {tabular}
\catcode `\@ 12

The converse is \textit{not} correct.
For a counterexample, let the domain of discourse be the natural numbers,
let $P(x)$ mean that $x$ is even, and let $Q(x)$ mean that $x$ is odd.
Then $\forall{x}\, \bigl(P(x) \vee Q(x)\bigr)$ is true,
because every natural number is either even or odd.
But $\forall{x}\, P(x) \vee \forall{y}\, Q(y)$ is false,
because not every natural number is even and not every natural number is odd.
\question
Prove that the square of an even number is even:
\begin {parts}
\part [2] \label {direct}
using a direct proof.
\solution
Suppose that the number $n$ is even.
That is (by the definition of even numbers), for some integer $k$, $n = 2k$.
(We implicitly use $\exists$ elimination to speak of $k$ directly.)
Then $n^{2} = (2k)^2 = 2^{2}k^{2} = (2 \cdot 2)k^{2} = 2(2k^{2})$;
the laws of arithmetic used here are
substitution of equal numbers in an expression,
distribution of exponentiation over multiplication,
the definition of squares in terms of multiplication,
and the associative law of multiplication.
Thus $n^{2} = 2(2k^{2})$ by transitivity of equality,
so $n = 2l$ for some $l$ (specifically $l := 2k^{2}$),
by $\exists$ introduction.
In other words (by the definition of even numbers), $n^{2}$ is even.
\part [2] \label {indirect}
using an indirect proof.
\solution
We look at the contrapositive.

So suppose that $n^{2}$ is not even.
Now, it's a property of numbers that every integer is even or odd.
Since $n^{2}$ is not even,
disjunctive syllogism (problem \ref{disjunctive}) shows that $n^{2}$ is odd.
That is, $n^{2} = 2k + 1$ for some $k$.
By the law of the excluded middle ($\neg$ introduction),
either $n$ is even or $n$ is not even.
Consider the case where $n$ is even.
That is, $n = 2l$ for some $l$.
Then by the same arithmetical argument as in part \ref{direct},
$n^{2} = 2(2l^{2})$.
So by the symmetry of equality, $2k + 1 = 2(2l^{2})$;
subtracting $2k$ from both sides of the equation and factoring out $2$,
you get $1 = 2(2l^{2} - k)$.
Dividing by $2$, $\frac{1}{2} = 2l^{2} - k$,
which is impossible because $\frac{1}{2}$ is not an integer.
Thus by disjunctive syllogism again, $n$ must not be even.
Therefore, whenever $n^2$ is not even, neither is $n$,
which indirectly proves that $n^2$ is even when $n$ is.
\part [2]
using a proof by contradiction.
\solution
We assume that the conclusion is false and derive a contradiction.

So suppose that $n$ is even but $n^{2}$ is not even.
As in part \ref{indirect}, it follows that $n^{2}$ is odd.
Since $n$ is even,
the same reasoning as in part \ref{indirect}
(where that was only one of two possibilities)
leads to the same contradiction.
But now, this contradiction ends the proof;
we have a proof by contradiction
that whenever $n$ is even, $n^{2}$ is also even.
\end {parts}
Mention all properties of numbers and all rules of inference
that you use in your proof.

[\textsl{Almost nobody mentioned any of these,
so I concluded that the instructions were unclear
and didn't take off points for leaving them out,
as long as the reasoning in each proof was correct.}]
\question [3]
Prove that if $n$ is an integer not divisible by $3$,
then $n^{2} - 1$ is divisible by $3$.
Mention all properties of numbers and all rules of inference
that you use in your proof.
\solution
Suppose that $n$ is not divisible by $3$.
That is, it is false that $n = 3k$ for some $k$.
By properties of division by $3$,
$n$ is either
$3l$ for some $l$, $3l + 1$ for some $l$, or $3l + 2$ for some $l$.
But the case where $n = 3l$ for some $l$ contradicts the beginning assumption,
since the variables $k$ and $l$ are just dummy variables
in a $\exists$ expression.
So by disjunctive syllogism (problem \ref{disjunctive}),
we only need consider the other possibilities.

In the case where $n = 3l + 1$,
then $n^{2} - 1 = (3l + 1)^{2} - 1 = \bigl((3l)^{2} + 2(3l)1 + 1^{2}\bigr) - 1
= 3^{2}l^{2} + 3(2l) + 1 - 1 = 3(3l^{2}) + 3(2l) + 0 = 3(3l^{2} + 2l)$,
where I've used the expansion of a square of a sum,
the distribution of exponentiation over multiplication,
the associative laws of multiplication and addition,
the identity property of $1$ under multiplication,
certain numerical facts ($1^{2} = 1$ and $1 - 1 = 0$),
the distribution of multiplication over addition,
and the identity property of $0$ under addition.
Thus, $n^{2} - 1 = 3m$ for some $m$, specifically $m := 3l^{2} + 2l$;
this is $\exists$ introduction.
In other words, $n^{2} - 1$ is divisible by $3$.

On the other hand, in the case where $n = 3l + 2$,
then $n^{2} - 1 = (3l + 2)^{2} - 1 = \bigl((3l)^{2} + 2(3l)2 + 2^{2}\bigr) - 1
= 3^{2}l^{2} + 3(2 \cdot 2)l + 4 - 1 = 3(3l^{2}) + 3(4l) + 3
= 3(3l^{2}) + 3(4l) + 3(1) = 3(3l^{2} + 4l + 1)$,
where I've used the same properties of arithmetic as before,
only with different numerical facts
($2 \cdot 2 = 4$, $2^{2} = 4$, and $4 - 1 = 3$).
Then once more, $n^{2} - 1 = 3m$ for some $m$,
this time for $m := 3l^{2} + 4l + 1$.
In other words, $n^{2} - 1$ is again divisible by $3$.

Since $n^{2} - 1$ is divisible by $3$
in either of the cases that I must consider,
I can conclude that $n^{2} - 1$ must be divisible by $3$,
whenever $n$ is not.
\question [4] [\textsl {Telescoping sums.}]
Prove by induction that
\begin {displaymath}
\sum_{i=1}^{n} (a_{i} - a_{i-1}) = a_{n} - a_{0}\mbox{.}
\end {displaymath}
[Hint: \textsl{Use the recursive definition of summation (\/$\sum$).}]
\solution
For the base of the induction, consider the case where $n = 0$.
In this case, $\sum_{i=1}^{0} (a_{i} - a_{i-1}) = 0$
by the base of the recursive definition of $\sum_{i=1}^{n}$.
On the other hand, certainly $a_{0} - a_{0} = 0$.
Thus, the base case is correct.
[\textsl{You might prefer a base case starting with $n = 1$,
where $\sum_{i=1}^{1} (a_{i} - a_{i-1}) = a_{1} - a_{1-1}$;
this is OK too.}]

So now assume, as an inductive hypothesis,
that $\sum_{i=1}^{n} (a_{i} - a_{i-1}) = a_{n} - a_{0}$
for some particular value of $n$.
Then $\sum_{i=1}^{n+1} (a_{i} - a_{i-1})
= \sum_{i=1}^{n} (a_{i} - a_{i-1}) + (a_{n+1} - a_{(n+1)-1})$
by the recursive step in the definition of $\sum$.
By the inductive hypothesis,
this equals $(a_{n} - a_{0}) + (a_{n+1} - a_{n}) = a_{n+1} - a_{0}$,
which is the correct value for $n + 1$.

Therefore by induction on $n$,
$\sum_{i=1}^{n} (a_{i} - a_{i-1}) = a_{n} - a_{0}$
for every natural number $n$.
[\textsl{If your base case was $n = 1$,
then you've only proved it for positive $n$.
But that's OK, since $n = 0$ is easy to do separately,
and I didn't explicitly specify that you had to include that case.}]
\question [4]
Prove by induction that
the sum of the first $n$ \textit{odd} positive integers is $n^{2}$.
[Hint: \textsl{Use summation
and a formula for the\/ $k$th odd positive integer.}]
\solution
The $k$th positive integer is $2k - 1$,
so we want to prove that $\sum_{k=1}^{n} (2k - 1) = n^{2}$.
[\textsl{You could also start with the $0$th positive integer,
using the formula $2k + 1$
and proving that $\sum_{k=0}^{n-1} (2k + 1) = n^{2}$.
It works out essentially the same.}]

For the base of the induction, consider the case where $n = 0$.
In this case, $\sum_{k=1}^{0} (2k - 1) = 0$
by the base case of the recursive definition of $\sum$.
On the other hand, $0^{2} = 0$, so the base case is correct.

For the inductive step,
assume that $\sum_{k=1}^{n} (2k - 1) = n^{2}$
for some particular value of $n$.
Then\break $\sum_{k=1}^{n+1} (2k - 1)
= \sum_{k=1}^{n} (2k - 1) + (2(n + 1) - 1)$
by the recursive step in the definition of $\sum$.
By the inductive hypothesis,
this is $n^{2} + 2n + 2 - 1 = (n + 1)^{2}$,
which is the correct value for $n + 1$.

Therefore by induction on $n$, $\sum_{k=1}^{n} (2k - 1) = n^{2}$, as desired.
\question [3]
Prove by induction
that the sum of the angles of a polygon with $n$ sides is $(n - 2)180^{\circ}$,
for $n \ge 3$ an integer.
You may use the fact from geometry
that the sum of the angles of a triangle is $180^{\circ}$.
[Hint: \textsl{You can divide a polygon with\/ $n$ sides
into a triangle and a polygon with\/ $n - 1$ sides,
if\/ $n - 1 \ge 3$.}]
\solution
I only want the result for $n \ge 3$, so the base case is $n = 3$.
In this case, a polygon with $3$ sides is a triangle,
the sum of whose angles is $180^{\circ}$.
Since $(3 - 2)180^{\circ} = 180^{\circ}$, this case is correct.

Now assume inductively
that the sum of the angles of any polygon with $n$ sides
is $(n - 2)180^{\circ}$.
Given a polygon $P$ with $n + 1$ sides,
draw a line from one vertex to another vertex $2$ sides away
to divide $P$ into a triangle $T$ and an $n$-gon $Q$.
Then the sum of the angles of $P$
is the sum of the angles of $T$ added to the sum of the angles of $Q$.
The former is $180^{\circ}$,
while the latter is, by the inductive hypothesis, $(n - 2)180^{\circ}$.
Adding these, we get $(n - 1)180^{\circ} = ((n + 1) - 2)180^{\circ}$,
which is the desired formula for an $(n + 1)$-gon.

Therefore by induction on $n$,
the sum of the angles of any polygon with $n$ sides is $(n - 2)180^{\circ}$,
for any value of $n$ that is at least $3$.
\question [4]
If $F_{n}$ is the $n$th Fibonacci number,
show that $F_{n-1}F_{n+1} - F_{n}^{2} = (-1)^{n}$.
\solution
In this class, the Fibonacci numbers begin with $F_{0} = 0$,
so this formula makes sense whenever $n \ge 1$.
Thus $n = 1$ is the base case.
[\textsl{Many people started with $n = 2$, which I accepted.}]

In this case,
$F_{1-1}F_{1+1} - F_{1}^{2} = F_{0}F_{0+2} - F_{1}^{2}
= F_{0}(F_{0} + F_{1}) - F_{1}^{2} = 0(0 + 1) - 1^{2} = -1 = (-1)^{1}$.
Thus the base case is correct.
But I had to use not only the base cases
(both $F_{0}$ and $F_{1}$) for the Fibonacci numbers,
but also the recursive step (to get $F_{0+2}$) as well.

For the inductive step,
assume that $F_{n-1}F_{n+1} - F_{n}^{2} = (-1)^{n}$
for some particular value of $n$.
Then \begin {eqnarray*}
F_{(n+1)-1}F_{(n+1)+1} - F_{n+1}^{2} &
= & F_{n}F_{n+2} - F_{(n-1)+2}F_{n+1} \\
& = & F_{n}(F_{n} + F_{n+1}) - (F_{n-1} + F_{(n-1)+1})F_{n+1} \\
& = & F_{n}F_{n} + F_{n}F_{n+1} - F_{n-1}F_{n+1} - F_{n}F_{n+1} \\
& = & F_{n}^{2} - F_{n-1}F_{n+1} \\
& = & -(F_{n-1}F_{n+1} - F_{n}^{2})\mbox{,}
\end {eqnarray*}
where I have used the recursive step twice,
once for $F_{n+2}$ and once for $F_{(n-1)+2}$.
(Notice that the latter works since $n \ge 1$ at least,
even though the recursive step doesn't apply to $F_{(n-1)+2}$ when $n = 0$,
according to our definition.)
Then by the inductive step,
this is $-(-1)^{n} = (-1)^{n}(-1)$,
which by the recursive step for the definition of exponentiation
equals $(-1)^{n+1}$.

This is just what we want for the case $n + 1$,
so the formula has been proved by induction whenever $n \ge 1$.
\question [3]
Give a recursive definition
of the set of all polynomials in a single variable $x$.
\solution
First let $S_{0}$ be the set of all constant polynomials.
Then there are several choices for $S_{n+1}$ that will work.
Some are:
\begin {parts}
\part $S_{n+1} := \{px + c \st p \in S_{n}\at c \in S_{0}\}$;
\part $S_{n+1} := \{cx^{n+1} + p \st c \in S_{0}\at p \in S_{n}\}$;
\part $S_{n+1} := \{px + q \st p,q \in S_{n}\}$.
\end {parts}
[\textsl{Anything that worked got full credit.}]
\end {questions}
\end {document}
