Assignment 7
Exercise 1 (Contraction Maps to Calculate \(\sqrt{a}\)) The babylonian procedure for approximating \(\sqrt{2}\) defined the recursive sequence \(w_{n+1}=\frac{1}{2}\left(w_n+\frac{2}{w_n}\right)\). Following analogous reasoning (but for a rectangle of area \(a\)) one might propose the recursive sequence \(w_{n+1}=\frac{1}{2}\left(w_n+\frac{a}{w_n}\right)\) as a means of computing \(\sqrt{a}\). This sequence is generated by iterating the function \[f(x)=\frac{1}{2}\left(x+\frac{a}{x}\right)\]
In this problem we will use the contraction mapping theorem to confirm this sequence does in fact converge to \(\sqrt{a}\) for any \(a>1\).
- Show that if \(x\geq\sqrt{a}\) then \(f(x)\geq\sqrt{a}\), so \(f\) maps the interval \([\sqrt{a},\infty)\) into \([\sqrt{a},\infty)\).
- Show that on this domain, \(f\) is a contraction map. Hint: factor out a copy of \(\frac{1}{2}|x-y|\) from \(|f(x)-f(y)|\) and show the remaining term is \(<1\) for all \(x,y\in [\sqrt{a},\infty)\).
- Show that if \(f(x)=x\) then \(x^2=a\).
- Now apply the contraction mapping theorem to conclude that iterating \(f\) from any point in the domain converges to \(\sqrt{a}\).
Finally, do a small example of your procedure (so you can see the benefit of what you’ve done!) and compute a rational approximation to \(\sqrt{3}\) by doing a couple iterates.
Solution.
This step is due to Jerry, whose solution was better than mine! Proceed with contradiction. Suppose that \(x \geq \sqrt{a}\) but \(\frac{1}{2}\left(x + \frac{a}{x}\right) < \sqrt{a}\). So \(x + \frac{a}{x} < 2\sqrt{a}\), so \(x^2 + a < 2\sqrt{a}x\) given that \(x > \sqrt{a} > 0\) as \(a > 1\). Rearranging, we have \(x^2 + a - 2\sqrt{a}x < 0\), but \(x^2 + a - 2\sqrt{a}x = (x - \sqrt{a})^2 \geq 0\) as it is a square, so we have a contradiction. Thus, \(f(x) \geq \sqrt{a}\).
To show \(f\) is a contraction, we compute \(|f(x)-f(y)|\) for \(x,y\) in \([\sqrt{a},\infty)\) and then seek to bound above by a fixed multiple of \(|x-y|\). We begin with some algebra \[ |f(x) - f(y)| = \left| \frac{1}{2}\left(x + \frac{a}{x}\right) - \frac{1}{2}\left(y + \frac{a}{y}\right) \right| = \left| \frac{1}{2}(x - y + \frac{a}{x} - \frac{a}{y}) \right|. \]
\[ = \left| \frac{1}{2}(x - y + \frac{a(y - x)}{xy}) \right| = \left| \frac{1}{2}(x - y)\left(1 - \frac{a}{xy} \right) \right| = \frac{1}{2}|x - y||1 - \frac{a}{xy}|. \]
Thus we need only show the terms multiplying \(|x-y|\) are uniformly less than some constant \(k<1\). To do so, note that \(x, y \geq \sqrt{a}\), so \(xy \geq a\) which imples \(1 \geq \frac{a}{xy}\) so \(|1 - \frac{a}{xy}| < 1\), so \[ \frac{1}{2}|1 - \frac{a}{xy}||x - y| < \frac{1}{2}|x - y|, \quad \text{for all } x, y \in [\sqrt{a}, \infty). \] Thus we can take \(k=1/2\) and as \(1/2<1\) this shows \(f\) is a contraction.
Suppose \(f(x) = x\), so \(\frac{1}{2}(x + \frac{a}{x}) = x\), so \(x + \frac{a}{x} = 2x\), then \(x^2 + a = 2x^2\), thus \(a = x^2\).
Given that \(f\) is a contraction map, by the contraction mapping theorem, \(f\) has a unique fixed point that satisfies \(f(x) = x\). We showed that when such equality holds, \(a = x^2\), so \(x = \sqrt{a}\) (as our entire domain is positive). Thus, any sequence generated by applying iterations of \(f\) on \(x_0 \in [\sqrt{a}, \infty)\) is convergent with the limit of \(\sqrt{a}\).
Example: approximate \(\sqrt{3}\) using \(f(x) = \frac{1}{2}\left(x + \frac{3}{x}\right)\).
Start with \(w_0 = 2\):
\[\begin{align*} w_1 &= \frac{1}{2} \left(2 + \frac{3}{2}\right) = \frac{1}{2} \cdot \frac{7}{2} = \frac{7}{4} = 1.75 \\ w_2 &= \frac{1}{2} \left(1.75 + \frac{3}{1.75}\right) \approx \frac{1}{2} (1.75 + 1.71429) = \frac{1}{2} (3.46429) \approx 1.73214 \\ w_3 &= \frac{1}{2} \left(1.73214 + \frac{3}{1.73214} \right) \approx \frac{1}{2} (1.73214 + 1.73196) = \frac{1}{2} (3.4641) \approx 1.73205 \end{align*}\]
Thus, after only three iterations, we obtain the approximation: \[ \sqrt{3} \approx 1.73205, \] accurate to five decimal places.
We can combine the contracting mapping theorem with other techniques to continue re-proving known results in easier ways. Here we take another look at our argument for the basic limit \(a^{1/n}\to 1\).
Exercise 2 (Proving \(a^{1/n}\to 1\) by Contraction Mapping) Fill in the following outline to prove \(a^{1/n}\to 1\) for all \(a>0\):
The sequence \(a^{1/n}\) is not generated by iterating a function, but it has many subsequences that are. For example the subsequence \[a, a^{1/2}, a^{1/4}, a^{1/8},\ldots\] Is generated by iterating \(f(x)=\sqrt{x}\).
Prove that this map is a contraction map on the domain \([1,\infty)\), which guarantees this subsequence converges for every \(a\geq 1\). Find the limiting value.
Now, for \(a>1\) prove the full sequence \(a^{1/n}\) is monotone decreasing and bounded below by 1. This ensures it converges (by monotone convergence).
Putting these two facts together, we see the entire sequence converges to 1, as if we have a convergent sequences, all subsequences have the same limit!
Finally, use the limit laws to argue the same holds even when \(a<1\).
Exercise 3 (Multiplying Infinite Products) Let \(\prod_{k\geq 1}a_k=\alpha\) and \(\prod_{k\geq 1}b_k=\beta\) be convergent infinite products. Prove that \(\prod_{k=1} a_k b_k\) converges, with limit \(\alpha\beta\).
Solution. Proof. By definition, the infinite products are limits of finite partial products. That is, our assumption unpacks to \[ \prod_{k=1}^n a_k = A_n \to \alpha \quad \text{and} \quad \prod_{k=1}^n b_k = B_n \to \beta \] as \(n \to \infty\).
To study the infinite product \(\prod_{k\geq 1} a_kb_k\) we also need to treat it as a limit of finite products: \[ C_n = \prod_{k=1}^n (a_k b_k). \]
Since multiplication is associative and commutative, we can regroup the finite product as follows: \[ C_n=\prod_{k=1}^n (a_k b_k) = \left( \prod_{k=1}^n a_k \right) \cdot \left( \prod_{k=1}^n b_k \right) = A_n B_n. \]
We are given that \(A_n \to \alpha\) and \(B_n \to \beta\), so by the limit law for the product of convergent sequences, we have: \[ \lim C_n = \lim A_n B_n = \left( \lim A_n \right) \cdot \left( \lim B_n \right) = \alpha \beta. \]
Therefore \(\prod_{k \geq 1} (a_k b_k) = \alpha \beta\) as desired.
Exercise 4 (Telescopes) Find the value of the following infinite product and series by showing they’re telescoping and computing an exact formula for their partial sums: \[\sum_{n\geq 1}\frac{1}{4n^2-1}\] \[\prod_{n\geq 5}\left(1-\frac{1}{n^2}\right)\]
Solution (Sum). We begin by factoring the denominator of each term as a difference of squares, so we can use partial fractions: \[ \frac{1}{4n^2-1}=\frac{1}{(2n - 1)(2n + 1)} = \frac{A}{2n - 1} + \frac{B}{2n + 1}. \] Combining fractions gives the condition \(1 = A(2n + 1) + B(2n - 1)\) for all \(n\), which we can solve various ways (getting equations for the constant and coefficient of \(n\) terms, or plugging in various values of \(n\) to get a system of equations: whatever precalc method you like!) In the end, we get \(A = \frac{1}{2}\) and \(B = -\frac{1}{2}\) so: \[ \frac{1}{(2n - 1)(2n + 1)} = \frac{1}{2} \left( \frac{1}{2n - 1} - \frac{1}{2n + 1} \right). \] Thus, \[ \sum_{n=1}^N \frac{1}{4n^2 - 1} = \frac{1}{2} \sum_{n=1}^N \left( \frac{1}{2n - 1} - \frac{1}{2n + 1} \right). \] This is a telescoping sum:
\[\begin{align*} \sum_{n=1}^N & \left( \frac{1}{2n - 1} - \frac{1}{2n + 1} \right) \\ &= \left( \frac{1}{1} - \frac{1}{3} \right) + \left( \frac{1}{3} - \frac{1}{5} \right) + \left( \frac{1}{5} - \frac{1}{7} \right) + \cdots + \left( \frac{1}{2N - 1} - \frac{1}{2N + 1} \right) \\ &= 1 +\left(-\frac{1}{3}+\frac{1}{3}\right)+\left(-\frac{1}{5}+\frac{1}{5}\right)+\cdots + \left(-\frac{1}{2N-1}+\frac{1}{2N-1}\right)-\frac{1}{2N+1}\\ &= 1 - \frac{1}{2N + 1}. \end{align*}\]
This gives an exact formula for the partial sums: \[ \sum_{n=1}^N \frac{1}{4n^2 - 1} = \frac{1}{2} \left(1 - \frac{1}{2N + 1} \right), \] and taking the limit: \[ \sum_{n \geq 1} \frac{1}{4n^2 - 1} = \lim_{N} \frac{1}{2} \left(1 - \frac{1}{2N + 1} \right) = \frac{1}{2}. \]
Solution (Product). We begin by factoring each term in the product \[ 1 - \frac{1}{n^2} = \frac{n^2 - 1}{n^2} = \frac{(n - 1)(n + 1)}{n^2}. \] So: \[ \prod_{n=5}^N \left(1 - \frac{1}{n^2} \right) = \prod_{n=5}^N \frac{(n - 1)(n + 1)}{n^2}. \]
This is already a telescoping product, as we notice by writing out some terms. But we can perhaps see it even more transparently by using breaking into two products for each finite partial product \[ \prod_{n=5}^N \frac{n - 1}{n} \cdot \frac{n + 1}{n} = \left( \prod_{n=5}^N \frac{n - 1}{n} \right) \cdot \left( \prod_{n=5}^N \frac{n + 1}{n} \right). \]
Each one of these has the numerator differing by one from the denominator, so immediately telescopes: \[ \prod_{n=5}^N \frac{n - 1}{n} = \frac{4}{5} \cdot \frac{5}{6} \cdot \frac{6}{7} \cdots \frac{N - 1}{N} = \frac{4}{N}. \] \[ \prod_{n=5}^N \frac{n + 1}{n} = \frac{6}{5} \cdot \frac{7}{6} \cdot \frac{8}{7} \cdots \frac{N + 1}{N} = \frac{N + 1}{5}. \]
We cannot take the limits separately here as one of them does not converge, but we are not asking about them separately! Putting back together \[ \prod_{n=5}^N \left(1 - \frac{1}{n^2} \right) = \frac{4}{N} \cdot \frac{N + 1}{5} = \frac{4(N + 1)}{5N}. \]
Now its easy to take the limit as \(N \to \infty\): \[ \lim_{N \to \infty} \frac{4(N + 1)}{5N} = \frac{4}{5}. \]
Exercise 5 (The Divergence of the Harmonic Series) Give an alternate proof that the harmonic series \(\sum \frac{1}{n}\) diverges, by comparing it with the partial sums of \[1, 1/2, 1/4, 1/4, 1/8, 1/8, 1/8, 1/8, 1/16,...\]
Hint: show that for each \(N\) the partial sum of the harmonic series is greater than the partial sums of this series. But then show the partial sums of this series are unbounded: for any integer \(k\) we can find a point where the sum surpasses \(k\). This means the partial sums of the harmonic series are unbounded: but we know all convergent series are bounded! Thus the harmonic series cannot be convergent.
Solution. Starting with out term comparison, we can let \(b_n=\frac{1}{n}\) and \(a_n\) be the partial sums shown. So we have, \[ \begin{matrix} a_n = & 1, & \frac{1}{2}, & \frac{1}{4}, & \frac{1}{4}, & \frac{1}{8}, & \frac{1}{8}, & \frac{1}{8}, & \cdots \\ b_n = & 1, & \frac{1}{2}, & \frac{1}{3}, & \frac{1}{4}, & \frac{1}{5}, & \frac{1}{6}, & \frac{1}{7}, & \cdots \end{matrix} \] We can see that for all of the terms \(0\leq a_n\leq b_n\). Then just looking at \(a_n\), we can see \[\begin{align*} \sum a_n &= 1+ \frac{1}{2}+ \frac{1}{4}+ \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \cdots \\ &= 1+ \frac{1}{2}+ \underbrace{\frac{1}{4}+ \frac{1}{4}}_{=\frac{1}{2}} + \underbrace{\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}}_{=\frac{1}{2}} + \cdots \\ \end{align*}\]
This means we have the following partial sums:
\[\sum_{1\leq n \leq 1}a_n = 1\hspace{0.5cm}\sum_{1\leq n \leq 2}a_n=1+\frac{1}{2}\hspace{0.5cm}\sum_{1\leq n \leq 4}a_n=1+\frac{1}{2}+\frac{1}{2}\] \[\sum_{1\leq n\leq 8}a_n=1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}\hspace{0.5cm} \sum_{1\leq n\leq 16}a_n=1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2} \]
This pattern continues to add up to a new 1/2 forever, as there are \(2^{n-1}\) terms of \(1/2^n\). Thus,
\[\sum_{1\leq n\leq 2^N}a_n=1+\frac{N}{2}\]
This diverges, so the entire series must diverge (the series is a limit of partial sums, and the sequence of partial sums has a divergent subsequence). And because we know that \(0\leq a_n\leq b_n\) and \(\sum a_n\) diverges, that means that \(\sum b_n\) must also diverge.
Exercise 6 (Multiplying by a Bounded Sequence) Let \(\sum a_k\) be an absolutely convergent series, and \(b_k\) a bounded sequence. Prove that the series of pairwise products converges: \[\sum a_kb_k\]
Hint: Show this is Cauchy, using that \(\sum a_k\) is.
Solution. Since \(\sum a_k\) is absolutely convergent, we know that: \(\sum |a_k|\) converges. Because \(b_k\) is bounded, we may choose an \(B>0\) with \(|b_k| \leq B\) for all \(k\). We will use these facts to prove that the series \(\sum a_k b_k\) satisfies the Cauchy criterion for convergence.
Choose an \(\epsilon>0\). Since \(\sum |a_k|\) conveges it is Cauchy, which means we may select an \(N\) such that for any \(n>m>N\) we have \(\sum_{m}^n |a_k|<\epsilon/B\). Then, for all \(n > m \geq N\), we estimate:
\[\begin{align*} \left| \sum_{k=m}^n a_k b_k \right| &\leq \sum_{k=m}^n |a_k b_k| \\ &\leq \sum_{k=m}^n |a_k| \cdot |b_k| \\ &\leq \sum_{k=m}^n |a_k| \cdot B = B \sum_{k=m}^n |a_k|\\ & < B\frac{\epsilon}{B}=\epsilon \end{align*}\]
Therefore, \(\sum a_k b_k\) satisfies the Cauchy criterion and hence converges.
Exercise 7 (Raising to a Power) Let \(a_k\) be a sequence of positive terms such that \(\sum a_k\) converges. Prove that if \(p>1\) is a positive integer, then the following series also converges \[\sum_k (a_k)^p\]
Hint: if \(0<x<1\), then raising \(x\) to the \(p^{th}\) power makes it smaller. Can you show that eventually \(a_k\) is less than 1 and then use comparison + dealing with the first finitely many terms to reach the required conclusion?
Proof. Since \(\sum a_k\) converges and each \(a_k > 0\), we know that \(a_k \to 0\). Therefore, using the definition of convergence with \(\epsilon=1\), there exists some integer \(N\) such that for all \(k \geq N\), we have \(0 < a_k < 1.\)
Now fix any integer \(p > 1\). If \(0<x<1\) then \(x^n<1^n=1\) for all \(n\), and thus for any integer \(p>2\), we have \[x^p = x x^{p-1} < x\cdot 1 = x\]
Thus, for \(k \geq N\), we have \(0 < a_k^p < a_k.\) This sets us up to apply comparison: since \(\sum a_k\) converges, so does the sum \(\sum_{k\geq N} a_k\) we get by deleting the first finitely many terms. Now since \(a_k^p < a_k\) for \(k \geq N\), it follows that \(\sum_{k=N}^\infty a_k^p\) also converges.
As for the first \(N-1\) terms, there are only finitely many of them, so the sum \(\sum_{k=1}^{N-1} a_k^p\) is finite. Therefore, the full series \[ \sum_{k=1}^\infty a_k^p = \sum_{k=1}^{N-1} a_k^p + \sum_{k=N}^\infty a_k^p \] is the sum of two convergent series, and thus converges.
Exercise 8 (The Root Test with Limsup) Prove that if \(\sum a_n\) is a series and \(L=\limsup\sqrt[n]{|a_n|}\), the series converges if \(L<1\) and diverges for \(L>1\).
Proof. We consider the two cases separately.
Case 1: \(L < 1\)
Let \(L = \limsup_{n \to \infty} \sqrt[n]{|a_n|}\) and assume \(L < 1\). Choose a number \(r\) such that \(L < r < 1\). We will now use the definition of limsup: \[\limsup \sqrt[n]{|a_n|} = \lim_{n \to \infty} \sup_{k \geq n} \sqrt[k]{|a_k|}.\] Since the sequence of suprema converges to \(L\) and \(L < r\), there exists an integer \(N\) such that for all \(n \geq N\): \(\sup_{k \geq n} \sqrt[k]{|a_k|} < r\). (Just using the limit definition, setting \(\epsilon\) to anything less than \(r-L\).)
In particular, for all \(k \geq N\), \[\sqrt[k]{|a_k|} \leq \sup_{j \geq k} \sqrt[j]{|a_j|} < r.\] So for all \(k \geq N\), we have: \[\sqrt[k]{|a_k|} < r \quad \Rightarrow \quad |a_k| < r^k.\]
We now compare the tail of the series \(\sum |a_n|\) with the geometric series \(\sum r^n\). Since \(0 < r < 1\), the geometric series converges, and so the comparison test implies: \(\sum_{k \geq N} |a_k| < \sum_{k \geq N} r^k.\) And \(\sum_{k\geq N}r^k\) converges, so so does our series. The finitely many terms \(\sum_{k=0}^{N-1} |a_k|\) form a finite sum, and so we conclude: \(\sum_{k=0}^\infty |a_k|\) converges as well. Hence the series \(\sum a_k\) converges absolutely, and therefore converges.
Case 2: \(L > 1\)
Now assume \(L = \limsup_{n \to \infty} \sqrt[n]{|a_n|} > 1\).
Let \(r\) be a number such that \(1 < r < L\). Again, use the definition of limsup as the limit of the sequence of suprema. Since this limit equals \(L > r\), and the sequence of suprema is a monotone decreasing sequence, \(r\) is a lower bound and so for every \(n\), \[\sup_{k \geq n} \sqrt[k]{|a_k|} > r.\]
For the supremum to be greater than \(r\), there must be at least one element of the sequence greater than \(r\). But this must hold for each \(n\)! So, there are infinitely many values where \[\sqrt[k]{|a_k|} > r \quad \Rightarrow \quad |a_k| > r^k.\] Since \(r > 1\), we know that \(r^k > 1\) for large \(k\), so \(|a_k| > 1\) infinitely often. Therefore: \[ \lim_{k \to \infty} |a_k| \nrightarrow 0. \] Hence \(a_k \nrightarrow 0\), and by the Divergence Test, the series \(\sum a_k\) diverges.