1.
State precisely the following. Be sure to set up any notation that is required.
-
The Principle of Strong Induction.
-
The Well-Ordering Property.
Exercises 3.2.3 Exercises
2.
Complete the steps below to prove that every amount of postage of 12 cents or more can be formed using 4-cent and 5-cent stamps.
-
“basis steps:”
-
What is the statement \(P(12)\text{?}\)
-
Prove \(P(12)\) is true.
-
In this case, the proof is simpler if we use strong induction. State and prove \(P(13)\text{,}\) \(P(14)\text{,}\) and \(P(15)\text{.}\)
-
-
“Inductive step:”
-
State the inductive hypothesis: “Fix \(k \geq \dots\text{.}\) Assume … for all \(\dots\leq j\leq k\text{.}\)”Be careful here. We gain the additional advantage of additional cases in the basis step by forcing \(k\) to be larger, and allowing \(j\) to go down as much as possible.
-
What is it we want to prove, assuming the inductive hypothesis? “We want to show ….”
-
Prove it. Be clear where we are using the inductive hypothesis. Verify that we are working in a range where the inductive hypothesis is assumed to hold.
-
Write “This completes the inductive step.”
-
-
State the conclusion: “By mathematical induction,…”
3.
Suppose \(a_1 = 10\text{,}\) \(a_2 = 5\text{,}\) and \(a_n = 2a_{n- 1} +
3a_{n - 2}\) for \(n \geq 3\text{.}\) Use strong induction to prove that \(5\) divides \(a_n\) for \(n \geq 1\text{.}\)
4.
Let \(n\) be a positive integer. Show that any \(2^n \times 2^n\) chess board with \(1\) square removed can be tiled using L-shaped pieces, where these pieces cover three squares at a time, as shown below. 
5.
Let \(f_n\) denote the \(n\)-th Fibonacci number. Prove that
\begin{equation*}
f_n = \frac{\phi^n - (1 - \phi)^n}{\sqrt{5}} \text{ where }
\phi = \frac{1 + \sqrt{5}}{2}.
\end{equation*}
Before starting the proof by induction show:
-
\(\displaystyle \phi^2 - \phi - 1 = 0\)
-
\(\displaystyle \phi^2 = \phi + 1\)
-
\((1 - \phi)^2 = 2 - \phi\text{.}\)
-
\(\displaystyle \phi(\phi+1)=\phi^3\)
6.
Prove that the power set \(\cP(S)\) of a finite set \(S\) has cardinality
\begin{equation*}
|\cP(S)| = 2^{|S|}.
\end{equation*}
(Hint: Use induction on the size \(|S|\) of \(S\text{.}\) Fix an element \(a\) in \(S\text{,}\) and count the subsets of \(S\) containing \(a\) and the subsets not containing \(a\text{.}\) Note: A direct proof of this is given in Theorem Theorem 2.1.4.4.)
7.
Prove that if a sequence \(\set{a_n}\) satisfies
\begin{equation*}
a_{n + 1} = \frac{a_n}{a_n + 1}
\end{equation*}
then
\begin{equation*}
a_n = \frac{a_0}{na_0 + 1}.
\end{equation*}
