7.3E: Exercises

Exercises

In Exercises 1 - 7, prove each assertion using the Principle of Mathematical Induction.

1. \(\displaystyle{ \sum_{j=1}^{n} j^2 = \dfrac{n(n+1)(2n+1)}{6}}\)
2. \(\displaystyle{ \sum_{j=1}^{n} j^3 = \dfrac{n^2(n+1)^2}{4}}\)
3. \(2^{n} > 500 n\) for \(n > 12\)
4. \(3^{n} \geq n^3\) for \(n \geq 4\)
5. Use the Product Rule for Absolute Value to show \(\left|x^{n}\right| = |x|^{n}\) for all real numbers \(x\) and all natural numbers \(n \geq 1\)
6. Use the Product Rule for Logarithms to show \(\log\left(x^{n}\right) = n \log(x)\) for all real numbers \(x > 0\) and all natural numbers \(n \geq 1\).
7. Prove Theorem 7.1.1 and Theorem 7.2.2 for the case of geometric sequences. That is:
   1. For the sequence \(a_{1} = a\), \(a_{1}=a, a_{n+1}=r a_{n}, n \geq 1, \text { prove } a_{n}=a r^{n-1}, n \geq 1\).
   2. \(\displaystyle{\sum_{j=1}^{n} a r^{n-1} = a \left( \dfrac{1-r^n}{1-r}\right)}\), if \(r \neq 1\), \(\displaystyle{\sum_{j=1}^{n} a r^{n-1} = na}\), if \(r=1\).
8. Discuss the classic ‘paradox’ All Horses are the Same Color problem with your classmates.

Selected Answers

1. Let \(P(n)\) be the sentence \(\displaystyle{ \sum_{j=1}^{n} j^2 = \dfrac{n(n+1)(2n+1)}{6}}\). For the base case, \(n=1\), we get

   \[\begin{array}{rcl} \displaystyle{ \sum_{j=1}^{1} j^2} & \stackrel{?}{=} & \dfrac{(1)(1+1)(2(1)+1)}{6} \\[15pt] 1^2 & = & 1 \, \checkmark \\ \end{array}\nonumber\]

   We now assume \(P(k)\) is true and use it to show \(P(k+1)\) is true. We have

   \[\begin{array}{rcl} \displaystyle{ \sum_{j=1}^{k+1} j^2} & \stackrel{?}{=} & \dfrac{(k+1)((k+1)+1)(2(k+1)+1)}{6} \\[15pt] \displaystyle{ \sum_{j=1}^{k} j^2} + (k+1)^2 & \stackrel{?}{=} & \dfrac{(k+1)(k+2)(2k+3)}{6} \\[15pt] \underbrace{\dfrac{k(k+1)(2k+1)}{6}}_{\text{Using $P(k)$}} + (k+1)^2 & \stackrel{?}{=} & \dfrac{(k+1)(k+2)(2k+3)}{6} \\ && \\ \dfrac{k(k+1)(2k+1)}{6} + \dfrac{6(k+1)^2}{6} & \stackrel{?}{=} & \dfrac{(k+1)(k+2)(2k+3)}{6} \\ \dfrac{k(k+1)(2k+1)+6(k+1)^2}{6} & \stackrel{?}{=} & \dfrac{(k+1)(k+2)(2k+3)}{6} \\ \dfrac{(k+1)(k(2k+1)+6(k+1))}{6} & \stackrel{?}{=} & \dfrac{(k+1)(k+2)(2k+3)}{6} \\ \dfrac{(k+1)\left(2k^2+7k+6\right)}{6} & \stackrel{?}{=} & \dfrac{(k+1)(k+2)(2k+3)}{6} \\ \dfrac{(k+1)(k+2)(2k+3)}{6} & = & \dfrac{(k+1)(k+2)(2k+3)}{6} \, \checkmark \\  \end{array}\nonumber\]

   By induction, \(\displaystyle{ \sum_{j=1}^{n} j^2 = \dfrac{n(n+1)(2n+1)}{6}}\) is true for all natural numbers \(n \geq 1\).

4. Let \(P(n)\) be the sentence \(3^n > n^3\). Our base case is \(n=4\) and we check \(3^4 = 81\) and \(4^3 = 64\) so that \(3^4 > 4^3\) as required. We now assume \(P(k)\) is true, that is \(3^k > k^3\), and try to show \(P(k+1)\) is true. We note that \(3^{k+1} = 3 \cdot 3^{k} > 3k^3\) and so we are done if we can show \(3k^3 > (k+1)^3\) for \(k \geq 4\). We can solve the inequality \(3x^3 > (x+1)^3\) using the techniques of Section 5.3, and doing so gives us \(x > \frac{1}{\sqrt[3]{3}-1} \approx 2.26.\) Hence, for \(k \geq 4\), \(3^{k+1} = 3 \cdot 3^{k} > 3k^3 > (k+1)^3\) so that \(3^{k+1} > (k+1)^3\). By induction, \(3^n > n^3\) is true for all natural numbers \(n \geq 4\).

6. Let \(P(n)\) be the sentence \(\log\left(x^n \right) = n \log(x)\). For the duration of this argument, we assume \(x > 0\). The base case \(P(1)\) amounts checking that \(\log\left(x^1\right) = 1 \log(x)\) which is clearly true. Next we assume \(P(k)\) is true, that is \(\log\left(x^{k}\right) = k \log(x)\) and try to show \(P(k+1)\) is true. Using the Product Rule for Logarithms along with the induction hypothesis, we get

   \[\log\left(x^{k+1}\right) = \log\left(x^{k} \cdot x\right) = \log\left(x^{k}\right) + \log(x) = k \log(x) + \log(x) = (k+1) \log(x)\nonumber\]

   Hence, \(\log\left(x^{k+1}\right) = (k+1) \log(x)\). By induction \(\log\left(x^n \right) = n \log(x)\) is true for all \(x>0\) and all natural numbers \(n \geq 1\).