1.2
Exercises from Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.
1
Define the following sequence \(a_n\) of integers for \(n \ge 1\).
\[\begin{split}
a_n :=
\begin{cases}
a_1 &= 1 \\
a_{n + 1} &= 2a_n + 1 && n \ge 2 \\
\end{cases}
\end{split}\]
Compute the values of \(a_i\) for \(i = 1, \dots, 5\). Prove by induction that for all \(n \ge 1\), \(a_n + 1\) is a power of \(2\).
\[\begin{split}
\begin{align*}
a_1 &= 1 \\
a_2 &= 2a_1 + 1 = 2(1) + 1 = 3 \\
a_3 &= 2a_2 + 1 = 2(3) + 1 = 7 \\
a_4 &= 2a_3 + 1 = 2(7) + 1 = 15 \\
a_5 &= 2a_4 + 1 = 2(15) + 1 = 31 \\
\vdots
\end{align*}
\end{split}\]
\(Claim\)
Let \(n\) be a positive integer.
One greater than each term in \(a_n\) is a power of \(2\).
\[
\forall n \in \mathbb{P} \,\,
[\,\,
\exists \ell \in \mathbb{P} \,\,
(\,\,
2^\ell = a_n + 1
\,\,)
\,\,]
\]
\(Proof\)
Base Case
\(a_1 = 1 \iff a_1 + 1 = 2\)
Induction Step
Induction Hypothesis: Let \(a_k + 1 = 2^m\) for some positive integers \(k\) and \(m\).
\(a_k + 1 = 2^m \iff a_k = 2^m - 1\).
\(a_{k + 1} + 1 = 2a_k + 2 = 2(2^m - 1) + 2 = 2^{m + 1} - 2 + 2 = 2^{m + 1}\).
\(\therefore a_{k + 1} + 1 = 2^{m + 1}\).
Therefore \(a_n + 1\) is a power of two for any positive integer \(n\).
\(\blacksquare\)
2
\(Claim\)
\[
\forall n \in \mathbb{P} \,\,
\left[\,\,
1 + 2^2 + \dots + n^2
= \frac{n(n + 1)(2n + 1)}{6}
= \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n
\,\,\right]
\]
\(Proof \,\, by \,\, induction\)
Base Case
\(1 = \frac{(1) \cdot ((1) + 1) \cdot (2(1) + 1)}{6} = \frac{1}{3} (1)^3 + \frac{1}{2} (1)^2 + \frac{1}{6} (1)\)
Induction Step
Induction Hypothesis: Let it be the case that \(1 + 2^2 + \dots + k^2 = \frac{k(k + 1)(2k + 1)}{6} = \frac{1}{3} k^3 + \frac{1}{2} k^2 + \frac{1}{6} k\) for some positive integer \(k\).
\[\begin{split}
\begin{align*}
& \textcolor{green}{1 + 2^2 + \dots + k^2 + (k + 1)^2} \\
= & \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 \\
= & \frac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6} \\
= & \frac{(k + 1)(k(2k + 1) + 6(k + 1))}{6} \\
= & \frac{(k + 1)(2k^2 + k + 6k + 6)}{6} \\
= & \frac{(k + 1)(2k^2 + 7k + 6)}{6} \\
= & \frac{(k + 1)(k + 2)(2k + 3)}{6} \\
= & \textcolor{green}{\frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6}} \\
= & \frac{(k^2 + 3k + 2)(2k + 3)}{6} \\
= & \frac{2k^3 + 3k^2 + 6k^2 + 9k + 4k + 6}{6} \\
= & \frac{2k^3}{6} + \frac{3k^2}{6} + \frac{6k^2}{6} + \frac{9k}{6} + \frac{4k}{6} + \frac{6}{6} \\
= & \frac{2k^3}{6} + \frac{6k^2}{6} + \frac{6k}{6} + \frac{2}{6} + \frac{3k^2}{6} + \frac{6k}{6} + \frac{3}{6} + \frac{k}{6} + \frac{1}{6} \\
= & \frac{2}{6} \left( k^3 + 3k^2 + 3k + 1 \right) + \frac{3}{6} \left( k^2 + 2k + 1 \right) + \frac{1}{6} \left( k + 1 \right) \\
= & \textcolor{green}{\frac{2}{6} (k + 1)^3 + \frac{3}{6} (k + 1)^2 + \frac{1}{6} (k + 1)} \\
\end{align*}
\end{split}\]
Therefore \(1 + 4 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6} = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n\) for any positive integer \(n\).
\(\blacksquare\)
4
The sum of the first \(n\) positive integers is given by a quadratic polynomial in \(n\).
\[
\forall n \in \mathbb{P} \,\,
\left[ \,\,
1 + 2 + \dots + n
= \frac{n(n + 1)}{2}
= \frac{1}{2} n^2 + \frac{1}{2} n
\,\, \right]
\]
The sum of the squares of the first \(n\) positive integers is given by a cubic polynomial in \(n\).
\[
\forall n \in \mathbb{P} \,\,
\left[\,\,
1 + 2^2 + \dots + n^2
= \frac{n(n + 1)(2n + 1)}{6}
= \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n
\,\,\right]
\]
\[\begin{split}
\begin{align*}
\frac{n(n + 1)}{2} &= \frac{1}{2} n^2 + \frac{1}{2} n \\
\frac{n(n^2 - 1)}{3} + \frac{n(n + 1)}{2} &= \frac{1}{2} n^2 + \frac{3}{6} n + \left( \frac{1}{3} n^3 - \frac{2}{6} n \right) \\
\end{align*}
\end{split}\]
The sum of the cubes of the first \(n\) positive integers is given by a quartic polynomial in \(n\). Find this polynomial. [Hint: suppose that the polynomial is of the form \(an^4 + bn^3 + cn^2 + dn + e\) for certain constants \(a, \dots, e\), then express the sum of the first \(n + 1\) cubes in two different ways.]
\[
\forall n \in \mathbb{P} \,\,
\left[\,\,
1 + 2^3 + \dots + n^3
= \,\, ?
\,\,\right]
\]
\[\begin{split}
\begin{align*}
n = 1 && 1 &= 1^3
&& = \frac{1}{4} 1^4 + \frac{1}{2} 1^3 + \frac{1}{4} 1^2
&& = \left( \frac{1}{2} 1^2 + \frac{1}{2} 1 \right)^2 \\
&& & && = 1
&& = \textcolor{green}{(1)^2} \\
n = 2 && 9 &= 1^3 + 2^3
&& = \frac{1}{4} 2^4 + \frac{1}{2} 2^3 + \frac{1}{4} 2^2
&& = \left( \frac{1}{2} 2^2 + \frac{1}{2} 2 \right)^2 \\
&& & && = \frac{1}{4} 16 + \frac{1}{2} 8 + \frac{1}{4} 4
&& = 3^2 \\
&& & && = 4 + 2 + 1 + 0
&& = \textcolor{green}{(1 + 2)^2} \\
n = 3 && 36 &= 1^3 + 2^3 + 3^3
&& = \frac{1}{4} 3^4 + \frac{1}{2} 3^3 + \frac{1}{4} 3^2
&& = \left( \frac{1}{2} 3^2 + \frac{1}{2} 3 \right)^2 \\
&& & && = \frac{1}{4} 81 + \frac{1}{2} 27 + \frac{1}{4} 9
&& = 6^2 \\
&& & && = 20 + 13 + 2 + 1
&& = \textcolor{green}{(1 + 2 + 3)^2} \\
n = 4 && 100 &= 1^3 + 2^3 + 3^3 + 4^3
&& = \frac{1}{4} 4^4 + \frac{1}{2} 4^3 + \frac{1}{4} 4^2
&& = \left( \frac{1}{2} 4^2 + \frac{1}{2} 4 \right)^2 \\
&& & && = \frac{1}{4} 256 + \frac{1}{2} 64 + \frac{1}{4} 16
&& = 10^2 \\
&& & && = 64 + 32 + 4 + 0
&& = \textcolor{green}{(1 + 2 + 3 + 4)^2} \\
n = 5 && 225 &= 1^3 + 2^3 + 3^3 + 4^3 + 5^3
&& = \frac{1}{4} 5^4 + \frac{1}{2} 5^3 + \frac{1}{4} 5^2
&& = \left( \frac{1}{2} 5^2 + \frac{1}{2} 5 \right)^2 \\
&& & && = \frac{1}{4} 625 + \frac{1}{2} 125 + \frac{1}{4} 25
&& = 15^2 \\
&& & && = 156 + 31 + 6 + 1
&& = \textcolor{green}{(1 + 2 + 3 + 4 + 5)^2} \\
\end{align*}
\end{split}\]
\[\begin{split}
\forall n \in \mathbb{P} \,\,
\left[\,\,
\begin{align*}
1 + 2^3 + \dots + n^3
&= (1 + 2 + \dots + n)^2 \\
&= \frac{n^2(n + 1)^2}{4} \\
&= \left( \frac{1}{2} n^2 + \frac{1}{2} n \right)^2 \\
&= \frac{1}{4} n^4 + \frac{1}{2} n^3 + \frac{1}{4} n^2 \\
\end{align*}
\,\,\right]
\end{split}\]
5
\(Claim\)
\[
\forall n \in \mathbb{P} \,\,
\left[\,\,
\frac{1}{3} + \frac{1}{15} + \dots + \frac{1}{(2n - 1)(2n + 1)} = \frac{n}{2n + 1}
\,\,\right]
\]
\[\begin{split}
\begin{align*}
n = 1 && \frac{1}{3} &= \frac{1}{3} = \frac{(1)}{2(1) + 1} \\
n = 2 && \frac{1}{3} + \frac{1}{15} &= \frac{2}{5} = \frac{(2)}{2(2) + 1} \\
n = 3 && \frac{1}{3} + \frac{1}{15} + \frac{1}{35} &= \frac{3}{7} = \frac{(3)}{2(3) + 1} \\
n = 4 && \frac{1}{3} + \frac{1}{15} + \frac{1}{35} + \frac{1}{63} &= \frac{4}{9} = \frac{(4)}{2(4) + 1} \\
n = 5 && \frac{1}{3} + \frac{1}{15} + \frac{1}{35} + \frac{1}{63} + \frac{1}{99} &= \frac{5}{11} = \frac{(5)}{2(5) + 1} \\
\end{align*}
\end{split}\]
\(Proof \,\, by \,\, induction\)
Base Case
\(\frac{1}{(2(1) - 1)(2(1) + 1)} = \frac{1}{3} = \frac{(1)}{(2(1) + 1)}\)
Induction Step
Induction Hypothesis: Let \(\frac{1}{3} + \frac{1}{15} + \dots + \frac{1}{(2k - 1)(2k + 1)} = \frac{k}{(2k + 1)}\) for some positive integer \(k\).
\[\begin{split}
\begin{align*}
& \textcolor{green}{\frac{1}{3} + \frac{1}{15} + \dots + \frac{1}{(2k - 1)(2k + 1)} + \frac{1}{(2(k + 1) - 1)(2(k + 1) + 1)}} \\
= & \frac{k}{(2k + 1)} + \frac{1}{(2(k + 1) - 1)(2(k + 1) + 1)} \\
= & \frac{k}{(2k + 1)} + \frac{1}{(2k + 1)(2k + 3)} \\
= & \frac{k(2k + 3) + 1}{(2k + 1)(2k + 3)} \\
= & \frac{2k^2 + 3k + 1}{(2k + 1)(2k + 3)} \\
= & \frac{\cancel{(2k + 1)}(k + 1)}{\cancel{(2k + 1)}(2k + 3)} \\
= & \frac{k + 1}{(2k + 3)} \\
= & \textcolor{green}{\frac{(k + 1)}{(2(k + 1) + 1)}} \\
\end{align*}
\end{split}\]
Therefore \(\frac{1}{3} + \frac{1}{15} + \dots + \frac{1}{(2n - 1)(2n + 1)} = \frac{n}{2n + 1}\) for any positive integer \(n\).
\(\blacksquare\)
6
Find a formula for the sum of the first \(n\) positive integers.
\[\begin{split}
\begin{align*}
n = 1 && 1 \\
&& = 2(0) + 1 \\
&& = 1 \\
n = 3 && 3 + 1 \\
&& = 2(1) + 1 + 2(0) + 1 \\
&& = 2(1) + 2(0) + 2 \\
&& = 2(1 + 0) + 2 \\
&& = 4 \\
n = 5 && 5 + 3 + 1 \\
&& = 2(2) + 1 + 2(1) + 1 + 2(0) + 1 \\
&& = 2(2) + 2(1) + 2(0) + 3 \\
&& = 2(2 + 1 + 0) + 3 \\
&& = 9 \\
n = 7 && 7 + 5 + 3 + 1 \\
&& = 2(3) + 1 + 2(2) + 1 + 2(1) + 1 + 2(0) + 1 \\
&& = 2(3) + 2(2) + 2(1) + 2(0) + 4 \\
&& = 2(3 + 2 + 1 + 0) + 4 \\
&& = 16 \\
n = 9 && 9 + 7 + 5 + 3 + 1 \\
&& = 2(4) + 1 + 2(3) + 1 + 2(2) + 1 + 2(1) + 1 + 2(0) + 1 \\
&& = 2(4) + 2(3) + 2(2) + 2(1) + 2(0) + 5 \\
&& = 2(4 + 3 + 2 + 1 + 0) + 5 \\
&& = 25 \\
\end{align*}
\end{split}\]
\[
\forall n \in \mathbb{P} \,\,
[\,\,
1 + 3 + \dots + (2n - 1) = n^2
\,\,]
\]
7
Prove that if \(x\) is not equal to \(1\) and \(n\) is any positive integer then \(1 + x + x^2 + \dots + x^n = \frac{1 - x^{n + 1}}{1 - x}\).
\(Claim\)
\[
\forall n \in \mathbb{P} \,\,
\forall x \in \mathbb{R} \,\,
\left[\,\,
(x \ne 1) \implies
\left( 1 + x + x^2 + \dots + x^n = \frac{1 - x^{n + 1}}{1 - x} \right)
\,\,\right]
\]
\(Proof \,\, by \,\, induction\)
Base Case
\(1 + x = \frac{1 - x^{(1) + 1}}{1 - x} = \frac{1 - x^2}{1 - x} = \frac{\cancel{(1 - x)}(1 + x)}{\cancel{1 - x}}\).
Induction Step
Induction Hypothesis: Let it be the case that \(1 + x + x^2 + \dots + x^k = \frac{1 - x^{k + 1}}{1 - x}\) for some positive integer \(k\).
\[\begin{split}
\begin{align*}
& \textcolor{green}{1 + x + x^2 + \dots + x^k + x^{k + 1}} \\
= & \frac{1 - x^{k + 1}}{1 - x} + x^{k + 1} \\
= & \frac{1 - x^{k + 1} + x^{k + 1}(1 - x)}{1 - x} \\
= & \frac{1 \cancel{- x^{k + 1}} \cancel{+ x^{k + 1}} - x^{k + 2}}{1 - x} \\
= & \frac{1 - x^{k + 2}}{1 - x} \\
= & \textcolor{green}{\frac{1 - x^{(k + 1) + 1}}{1 - x}} \\
\end{align*}
\end{split}\]
Therefore \(1 + x + x^2 + \dots + x^n = \frac{1 - x^{n + 1}}{1 - x}\) holds for any positive integer \(n\).
\(\blacksquare\)
8
Show that for every positive integer \(n\), \(n^5 - n\) is divisible by \(5\).
\(Claim\)
\[
\forall n \in \mathbb{P} \,\,
[\,\,
5 \mid n^5 - n
\,\,]
\]
\(Proof \,\, by \,\, induction\)
Base Case
Induction Step
Induction Hypothesis: Let it be the case that \(5 \mid k^5 - k\) for some positive integer \(k\).
\[\begin{split}
\begin{align*}
& (k + 1)^5 - (k + 1) \\
= & (k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1) - k - 1 \\
= & k^5 + 5k^4 + 10k^3 + 10k^2 + 5k - k \\
= & (k^5 - k) + (5k^4 + 10k^3 + 10k^2 + 5k) \\
= & (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k) \\
\end{align*}
\end{split}\]
Since
\(5 \mid k^5 - k\)
\(5 \mid 5(k^4 + 2k^3 + 2k^2 + k)\)
\(5\) divides their sum.
Therefore \(5 \mid n^5 - n\) for any positive integer \(n\).
\(\blacksquare\)
Show that for every positive integer \(n\), \(3^{2n} - 1\) is divisible by \(8\).
\(Claim\)
\[
\forall n \in \mathbb{P} \,\,
[\,\,
8 \mid 3^{2n} - 1
\,\,]
\]
\(Proof \,\, by \,\, induction\)
Base Case
\(8 \mid 3^{2(1)} - 1 = 8\)
Induction Step
Induction Hypothesis: Let it be the case that \(8 \mid 3^{2k} - 1\) for some positive integer \(k\).
\[\begin{split}
\begin{align*}
& 3^{2(k + 1)} - 1 \\
= & 3^{2k + 2} - 1 \\
= & 3^{2k}3^2 - 3^2 + 3^2 - 1 \\
= & 3^2(3^{2k} - 1) + 3^2 - 1 \\
= & 3^2(3^{2k} - 1) + 8 \\
\end{align*}
\end{split}\]
Since
\(8 \mid 3^2(3^{2k} - 1)\)
\(8 \mid 8\)
\(8\) divides their sum.
Therefore \(8 \mid 3^{2n} - 1\) for any positive integer \(n\).
\(\blacksquare\)
9
Given that \(x_0 = 2\), \(x_1 = 5\), and \(x_{n + 2} = 5x_{n + 1} - 3x_n\) for \(n\) greater than or equal to \(0\), prove that \(2^nx_n = (5 + \sqrt{13})^n + (5 - \sqrt{13})^n\).
Let \(x\) be a sequence defined as follows.
\[\begin{split}
x_n :=
\begin{cases}
x_0 &= 2 \\
x_1 &= 5 \\
x_{n + 2} &= 5x_{n + 1} - 3x_n && n \in \mathbb{N} \\
\end{cases}
\end{split}\]
\(Claim\)
\[
\forall n \in \mathbb{N} \,\,
[\,\,
2^nx_n = (5 + \sqrt{13})^n + (5 - \sqrt{13})^n
\,\,]
\]
\(Proof \,\, by \,\, induction\)
\[\begin{split}
\begin{align*}
x_0 = 2 && 2^0 x_0 &= (5 + \sqrt{13})^0 + (5 - \sqrt{13})^0 \\
&& 2 &= 1 + 1 \\
x_1 = 5 && 2^1 x_1 &= (5 + \sqrt{13})^1 + (5 - \sqrt{13})^1 \\
&& 10 &= 5 + 5 \\
\end{align*}
\end{split}\]
Induction Step
Induction Hypothesis: Let it be the case that \(2^{k + 1}x_{k + 1} = (5 + \sqrt{13})^{k + 1} + (5 - \sqrt{13})^{k + 1}\) for some positive integer \(k\).
\[\begin{split}
\begin{align*}
& \textcolor{green}{2^{k + 2}x_{k + 2}} \\
= & 2 \cdot 2^{k + 1}(5x_{k + 1} - 3x_k) \\
= & 10 \cdot 2^{k + 1} x_{k + 1} - 6 \cdot 2^{k + 1} x_k \\
= & 10 \cdot 2^{k + 1} x_{k + 1} - 12 \cdot 2^k x_k \\
= & 10 ((5 + \sqrt{13})^{k + 1} + (5 - \sqrt{13})^{k + 1}) - 12 ((5 + \sqrt{13})^k + (5 - \sqrt{13})^k) \\
= & 10 (5 + \sqrt{13})^{k + 1} + 10 (5 - \sqrt{13})^{k + 1} - 12 (5 + \sqrt{13})^k - 12 (5 - \sqrt{13})^k \\
= & 10 (5 + \sqrt{13})^k(5 + \sqrt{13}) + 10 (5 - \sqrt{13})^k(5 - \sqrt{13}) - 12 (5 + \sqrt{13})^k - 12 (5 - \sqrt{13})^k \\
= & [ 10 (5 + \sqrt{13})^k(5 + \sqrt{13}) - 12 (5 + \sqrt{13})^k ] + [ 10 (5 - \sqrt{13})^k(5 - \sqrt{13}) - 12 (5 - \sqrt{13})^k ] \\
= & (5 + \sqrt{13})^k [ 10 (5 + \sqrt{13}) - 12 ] + (5 - \sqrt{13})^k [ 10 (5 - \sqrt{13}) - 12 ] \\
= & (5 + \sqrt{13})^k [ 38 + 10 \sqrt{13} ] + (5 - \sqrt{13})^k [ 38 - 10 \sqrt{13} ] \\
= & (5 + \sqrt{13})^k [ 25 + 10 \sqrt{13} + 13 ] + (5 - \sqrt{13})^k [ 25 - 10 \sqrt{13} + 13 ] \\
= & (5 + \sqrt{13})^k (5 + \sqrt{13})^2 + (5 - \sqrt{13})^k (5 - \sqrt{13})^2 \\
= & \textcolor{green}{(5 + \sqrt{13})^{k + 2} + (5 - \sqrt{13})^{k + 2}} \\
\end{align*}
\end{split}\]
Therefore \(2^nx_n = (5 + \sqrt{13})^n + (5 - \sqrt{13})^n\) for any positive integer \(n\).
\(\blacksquare\)
via first-order recurrence relation and geometric sequence
\(
x_{n + 2} - ax_{n + 1} = b(x_{n + 1} - ax_n) \\
x_{n + 2} = bx_{n + 1} - abx_n + ax_{n + 1} \\
x_{n + 2} = ax_{n + 1} + bx_{n + 1} - abx_n \\
x_{n + 2} = (a + b)x_{n + 1} - (ab)x_n \\
a + b = 5 = B \\
ab = 3 = C \\
x_1 + x_2 = -\frac{b}{a} = 5 \\
x_1 \cdot x_2 = \frac{c}{a} = 3 \\
x^2 - (a + b)x + (ab) = 0 \\
\frac{-5 \pm \sqrt{13}}{2} \\
\)
10
Show that the principle of induction implies the well-ordering principle. [Hint: let \(X\) be a set of positive integers which contains no least element; we must show that \(X\) is empty. Define \(L\) to be the set of all positive integers \(n\) such that \(n\) is not greater than or equal to any element in \(X\). Show by induction that \(L\) is the set of all positive integers, and hence that \(X\) is indeed empty.]
11
Consider the assertion: \((*)\) ‘for every prime number \(n\), \(2^n - 1\) is a prime number’ (a positive integer is prime if it cannot be written as a product of two strictly smaller positive integers). Taking \(n\) to be \(2, 3, 5\) in turn, the corresponding values of \(2^n - 1\) are \(3, 7, 31\) and these certainly are prime. Is \((*)\) true?
\(Claim\)
\[
\lnot \forall n \in \mathbb{P} \,\,
[\,\,
Prime(n) \implies Prime(2^n - 1)
\,\,]
\]
\(Proof \,\, by \,\, counterexample\)
\[\begin{split}
\begin{align*}
n = 2 && 3 &= 2^2 - 1 \\
n = 3 && 7 &= 2^3 - 1 \\
n = 5 && 31 &= 2^5 - 1 \\
n = 7 && 127 &= 2^7 - 1 \\
n = 11 && 23 \times 89 = 2047 &= 2^{11} - 1 \\
\end{align*}
\end{split}\]
\(\blacksquare\)