1.
State precisely the Principle of Mathematical Induction. Be sure to set up any notation that is required.
Exercises 3.1.3 Exercises
2.
Complete the steps below to prove that for every positive integer \(n\text{,}\)
\begin{equation*}
1 \cdot 2 + 2 \cdot 3 + \dots + n(n + 1) = \frac{n(n + 1)(n +
2)}{3}.
\end{equation*}
I have written in quotes part of what you need to write. You should complete the proof.
- Introduction
- Basis step
-
Prove \(P(1)\) is true.
- Inductive step
-
Prove it. Be clear where you are using the inductive hypothesis.
- Conclusion
3.
For each positive integer \(n\text{,}\) let \(P(n)\) be the proposition
\begin{equation*}
2^0 + 2^1 + 2^2 + \dots + 2^n = 2^{n + 1} - 1.
\end{equation*}
Prove \(P(n)\) is true for all positive integers \(n\) by induction.
4.
Prove this extension of De Morgan’s law. Let \(p_1, p_2, \cdots, p_n\) be propositions. Prove that
\begin{equation*}
\lnot(p_1\lor p_2\lor \cdots\lor p_n) \equiv\lnot p_1\land \lnot p_2\land \cdots\land\lnot p_n.
\end{equation*}
5.
Let \(P(n)\) be the proposition “\(n^2 + 5n + 1\) is even.” Fix \(k \geq 0\text{.}\) Assume \(P(k)\) is true so that \(k^2 + 5k + 1\) is even. We want to show \((k + 1)^2 + 5(k + 1) + 1\) is even. We compute
\begin{align*}
(k + 1)^2 + 5(k + 1) + 1 \amp = k^2 + 2k + 1 + 5k + 5 + 1 \\
\amp = (k^2 + 5k + 1) + 2(k + 3).
\end{align*}
Since \(k^2 + 5k + 1\) is even by inductive hypothesis and \(2(k + 3)\) is visibly even, \((k + 1)^2 + 5(k + 1) + 1\) is even.
6.
We proceed by induction on \(n\text{.}\)
Inductive step: Fix \(k \geq 1\text{.}\) Assume \(P(k)\) is true. that is , assume \(2^k\leq k + 1\text{.}\)
\begin{align*}
2^{k + 1} \amp \leq (k + 1) + 1 \\
2 \cdot 2^k \amp \leq k + 2 \\
2^k \amp \leq \frac{k}{2} + 1\leq k + 1,
\end{align*}
which is true by inductive hypothesis. Thus by induction, \(2^n\leq n + 1\) for all \(n \geq 1\text{.}\)
7.
Fix real numbers \(a\) and \(r\text{,}\) with \(r \neq 1\text{.}\) Prove that for every positive integer \(n\text{,}\)
\begin{equation*}
a + ar^1 + ar^2+ \dots + ar^n = \frac{ar^{n + 1} - a}{r - 1}.
\end{equation*}
8.
If you have had calculus, prove the power rule for positive exponents. Specifically, prove that for every positive integer \(n\text{,}\)
\begin{equation*}
\frac{d}{dx}(x^n) = nx^{n - 1}.
\end{equation*}
(Hint: Use induction on \(n\) and the Product rule, writing \(x^n = x \cdot x^{n - 1}\text{.}\))
9.
Prove that for every positive integer \(n\text{,}\)
\begin{equation*}
1 + 2 + \dots + n = \frac{n(n + 1)}{2}.
\end{equation*}
10.
Prove that for every positive integer \(n\text{,}\)
\begin{equation*}
1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}.
\end{equation*}
11.
Prove for every positive integer \(n\text{,}\)
\begin{equation*}
1^3 + 2^3 + 3^3 + \cdots + n^3 =\left(\frac{n(n + 1)}{2}\right)^2.
\end{equation*}
12.
Prove that for every positive integer \(n\text{,}\)
\begin{equation*}
1\cdot 1! + 2\cdot 2! + \cdots + n\cdot n! = (n + 1)!
- 1.
\end{equation*}
13.
14.
Prove that \(11^n - 4^n\) is divisible by \(7\text{,}\) for all \(n \geq 0\text{.}\) Redo the proof using congruences instead of induction.
15.
Prove that for every positive integer \(n\text{,}\)
\begin{equation*}
\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \dots + \frac{1}{n\cdot (n + 1)} =
\frac{n}{n + 1}.
\end{equation*}
