Exercises §1 — Ross, Elementary Analysis, 2nd Edition
Exercise 1.1. Prove \[ 1^2 + 2^2 + \cdots + n^2 = \tfrac{1}{6} n(n+1)(2n+1) \qquad \text{for all } n \in \mathbb{N}. \]
Proof. By induction on \(n\).
Base: \(n = 1\). \[ \tfrac{1}{6}(1)(1+1)(2(1)+1) = \tfrac{1}{6}(1)(2)(3) = 1 = 1^2. \quad\checkmark \]
Inductive Hypothesis. Assume the equation holds for \(n\). We’ll show this implies it holds for \((n+1)\), meaning \[ 1^2 + 2^2 + \cdots + (n+1)^2 = \tfrac{1}{6}(n+1)(n+2)(2n+3). \]
Add \((n+1)^2\) to both sides of the equation:
\[ \begin{aligned} 1^2 + 2^2 + \cdots + n^2 + (n+1)^2 &= \tfrac{1}{6}\bigl[n(n+1)(2n+1)\bigr] + (n+1)^2 \\ &= \tfrac{1}{6}\bigl[(n^2 + n)(2n+1)\bigr] + (n+1)^2 \\ &= \tfrac{1}{6}\bigl[2n^3 + n^2 + 2n^2 + n\bigr] + (n+1)^2 \\ &= \tfrac{1}{6}\bigl[2n^3 + 3n^2 + n + 6(n+1)^2\bigr] \\ &= \tfrac{1}{6}\bigl[2n^3 + 3n^2 + n + 6n^2 + 12n + 6\bigr] \\ &= \tfrac{1}{6}\bigl[2n^3 + 9n^2 + 13n + 6\bigr] \\ &= \tfrac{1}{6}(n+1)(n+2)(2n+3). \qquad\square \end{aligned} \]
Exercise 1.6. Prove \(11^n - 4^n\) is divisible by \(7\) when \(n\) is a positive integer.
Proof. By strong induction on \(n \in \mathbb{N}\).
Base. \[ \begin{aligned} n = 1 &:\ 11 - 4 = 7 \Rightarrow 7 \mid 7. \quad\checkmark \\ n = 2 &:\ 11^2 - 4^2 = 121 - 16 = 105 = 7(15). \quad\checkmark \end{aligned} \]
Inductive Hypothesis. Assume \(11^j - 4^j\) is divisible by \(7\) for all \(1 \le j \le n\), where \(n \ge 2\) (strong induction). We want to show \(11^{n+1} - 4^{n+1}\) is also divisible by \(7\).
Using the identity \(x^{n+1} - y^{n+1} = (x^n - y^n)(x+y) - xy\,(x^{n-1} - y^{n-1})\) with \(x = 11\), \(y = 4\):
\[ \begin{aligned} 11^{n+1} - 4^{n+1} &= (11^n - 4^n)(11 + 4) - 4(11)\bigl[11^{n-1} - 4^{n-1}\bigr] \\ &= 7k(15) - 4(11)(7m) && [k, m \in \mathbb{Z} \text{ by IH}] \\ &= 7(15k) - 7(44m) \\ &= 7\bigl[15k - 44m\bigr] && [\,15k - 44m \in \mathbb{Z}\,] \end{aligned} \]
\[ \Rightarrow\ 11^{n+1} - 4^{n+1} \text{ is divisible by } 7. \qquad\square \]
Exercise 1.12. \[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \quad\text{for } k = 0, 1, \dots, n,\ \ n! = 1 \cdot 2 \cdots n,\ \ n \in \mathbb{N},\ \ 0! = 1. \]
The Binomial Theorem states: \[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k} = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \cdots + \binom{n}{n-1}ab^{n-1} + \binom{n}{n}b^n. \]
That is, \[ (a+b)^n = a^n + n a^{n-1} b + \tfrac{1}{2} n(n-1) a^{n-2} b^2 + \cdots + n a b^{n-1} + b^n. \]
(a) Verify for \(n = 1, 2, 3\).
\(n = 1\): \[ (a+b)^1 = \binom{1}{0}a + \binom{1}{1}b = a + b. \quad\checkmark \]
\(n = 2\): \[ (a+b)^2 = \binom{2}{0}a^2 + \binom{2}{1}ab + \binom{2}{2}b^2 = a^2 + 2ab + b^2. \quad\checkmark \]
\(n = 3\): \[ (a+b)^3 = \binom{3}{0}a^3 + \binom{3}{1}a^2 b + \binom{3}{2}a b^2 + \binom{3}{3}b^3 = a^3 + 3a^2 b + 3 a b^2 + b^3. \quad\checkmark \]
(b) Show \[ \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} \qquad \text{for } k = 1, 2, \dots, n. \]
\[ \begin{aligned} \binom{n}{k} + \binom{n}{k-1} &= \frac{n!}{k!\,(n-k)!} + \frac{n!}{(k-1)!\,(n-k+1)!} \\ &= \frac{n!\,(n+1-k)}{k!\,(n+1-k)!} + \frac{n!\,k}{k!\,(n+1-k)!} \\ &= \frac{n!\,(n+1-k) + n!\,k}{k!\,(n+1-k)!} \\ &= \frac{n!\,(n+1)}{k!\,(n+1-k)!} \\ &= \frac{(n+1)!}{k!\,(n+1-k)!} \\ &= \binom{n+1}{k}. \qquad\square \end{aligned} \]
(c) Proof of the Binomial Theorem by induction on \(n\). Part (a) is the base case (\(n = 1\) verified).
Inductive Hypothesis. Assume \((a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k}\) holds for \(n\). We’ll show it holds for \(n+1\).
\[ \begin{aligned} (a+b)^{n+1} &= (a+b)(a+b)^n \\ &= (a+b) \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k} \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^{k} + \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k+1} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k} b^{k} + \sum_{k=1}^{n} \binom{n}{k-1} a^{n+1-k} b^{k} + b^{n+1} \\ &= a^{n+1} + \sum_{k=1}^{n} \left[\binom{n}{k} + \binom{n}{k-1}\right] a^{n+1-k} b^{k} + b^{n+1} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k} a^{n+1-k} b^{k} + b^{n+1} && [\text{by (b)}] \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^{k}. \qquad\square \end{aligned} \]