Solutions to proof questions are not unique! There may be many different ways to prove any one statement. Remember this as you read solutions—these are only sample proofs!
(1.1) Prove \(1^2 + 2^2 + 3^2 + \cdots + n^2 = \tfrac 16 n(n+1)(2n+1)\) for all positive integers \(n\).
Proof. By induction.
Base case. \(P_1\) holds because \(1 = 1^2 = \tfrac 16 1(2)(3) = 1\).
Induction step. Assume \(P_n: \sum_{i=1}^n{i^2} = \tfrac 16 n(n+1)(2n+1)\) holds. Consider the LHS of \(P_{n+1}\):
\[\sum_{i=1}^{n+1}{i^2} = \sum_{i=1}^n{i^2} + (n+1)^2 = \tfrac 16 n(n+1)(2n+1) + (n+1)^2\]where we have used the induction hypothesis. Factoring out \((n+1)\) from both terms yields that
\[\sum_{i=1}^{n+1}{i^2} = (n+1)\left(\frac {2n^2+n + 6n+6}6 \right) = \frac 16 (n+1)((n+1)+1)(2(n+1)+1).\]So \(P_{n+1}\) holds, and by induction, all \(P_k\) hold for all \(k \in \mathbb N\). \(\Box\)
(1.6) Prove \(11^n - 4^n\) is divisible by 7 when \(n\) is a positive integer. (An integer \(k\) is divisible by an integer \(q\) if there exists an integer \(m\) so that \(k = mq\).)
Proof. By induction.
Base case. \(P_1\) holds because \(11 - 4 = 7\) which is trivially divisible by 7.
Induction step. Assume \(P_n\) holds; this means that we assume that there exists \(m \in \mathbb Z\) so that \(11^n - 4^n = 7m\). Consider
\[11^{n+1} - 4^{n+1} = 11(11^n)-4(4^n).\]We have that \(11 = 7+4\) so we get that
\[11(11^n)-4(4^n) = 7(11^n) + 4(11^n) - 4(4^n) = 7(11^n) + 4(11^n - 4^n) = 7(11^n) + 4(7m)\]where we have used the inductive hypothesis in the last step. So,
\[11^{n+1} - 4^{n+1} = 7(11^n + 4m);\]as \(11^n + 4n\) is an integer, we conclude that \(7\) divides \(11^{n+1} - 4^{n+1}\), hence that \(P_{n+1}\) is true.
So by induction, for all \(k \in \mathbb N\), \(P_k\) is true. \(\Box\)
(4.3, partial) For each subset of \(\mathbb R\) below, determine both the supremum and the infimum, if they exist. If either doesn’t exist, say so. You do not need to give a rigorous proof of your answer.
\(\inf A = 3\); \(\sup A = 5\).
\(\inf B = 0\); \(\sup B = +\infty\). (For this question, it’s also okay if you say it DNE).
\(\inf C = -\sqrt 3/2\); \(\sup C = \sqrt 3/2\). This set only has 3 elements.
\(\inf D = -\sqrt 3\); \(\sup D = \sqrt 3\). Even though \(D \subset \mathbb Q\), it is still a subset of the real numbers, so it has an infimum and supremum (an we know what they are).
\(\inf E = 2/3\); \(\sup E = 1\). \(1\) is certainly an upper bound. Proof that it is the least upper bound:
Let \(a < 1\). Then \(1 > 1-a > 0\) and so let \(n > -\log_3(1-a)\) be a natural number which exists by the Archimedean property. So then \(1 - 3^{-n} > 1 - 3^{\log_3(1-a)} = 1 - 1 + a = a\). So \(a\) cannot be an upper bound. So \(1\) is indeed the least upper bound.
Don’t worry about writing out any formal proofs in this problem. Decide whether each of the following statements is true. If the statement is true, you don’t need to do anything more. If the statement is false, give a concrete example (that is, a counterexample) that shows the statement failing.
For a nonempty, bounded set \(S \subseteq \mathbb R\), \(\inf S < \sup S\).
False. Let \(S\) be a set of one element.
If \(r \ne 0\) is rational and \(\alpha\) is irrational, then \(r\alpha\) is irrational.
True. Were \(r\alpha = p/q\) for some integers \(p,q\) then \(\alpha = p/(rq)\) which would be a rational number (why?).
If \(T \subset S \subset \mathbb R\), \(T\) is nonempty and \(S\) is bounded, then \(\sup T \le \sup S\).
True. If \(\sup S\) is an upper bound for \(T\) as \(\forall t \in T, t \in S\) (definition of subset) so \(\sup S \ge t\). As \(\sup T\) is a least upper bound for \(T\), it must be at most as big as the upper bound \(\sup S\).
A finite, nonempty set always contains its supremum.
True. Finite, nonempty sets have maximums, which agree with supremums when they exist.
Let \(A\) be a nonempty set of real numbers which is bounded below. Let \(-A\) be the set \(\{ -x \;:\; x \in A \}\). Prove that
\[\inf A = -\sup(-A).\](Note: This is the bulk of the proof of Corollary 4.5. You’re welcome to make use of all of the theorems and properties in Section 3, including Theorem 3.2. \(\mathbb R\) is an ordered field.)
Proof.
Let \(M = \sup(-A)\). For any element \(x \in A\), we have that \(-x \in -A\) by definition of \(-A\). By definition of supremum, we have then that \(M \ge -x\). By theorem 3.2, multiplying both sides by \(-1\) yields that \(-M \le x\). As this holds for all \(x \in A\), we conclude that \(-M\) is a lower bound for \(A\).
Consider any lower bound \(t\) of \(A\). This means that \(t \le x\) for all \(x \in A\). Theorem 3.2 then says that \(-t \ge -x\) for all \(x \in A\), which means that \(-t \ge y\) for all \(y \in -A\) by definition of \(-A\). So \(t\) is an upper bound for \(-A\). As \(M\) is the supremum of \(-A\), it is lesser than any other upper bound so that \(M \le -t\). Theorem 3.2 then says that \(-M \ge t\). This is true for any lower bound \(t\) of \(A\), so \(-M\) is indeed the infimum of the set \(A\); that is, \(-M = \inf(A)\).
We conclude then that \(\inf A = -\sup(-A)\). \(\Box\)