$$$$

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}(w_n+\frac{2}{w_n})$. Following analogous reasoning (but for a rectangle of area $a$) one might propose the recursive sequence $w_{n+1}=\frac{1}{2}(w_n+\frac{a}{w_n})$ as a means of computing $\sqrt{a}$. This sequence is generated by iterating the function $$f(x)=\frac{1}{2}(x+\frac{a}{x})$$

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\ge \sqrt{a}$ then $f(x)\ge \sqrt{a}$, so $f$ maps the interval $[\sqrt{a},\mathrm{\infty })$ into $[\sqrt{a},\mathrm{\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},\mathrm{\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\ge \sqrt{a}$ but $\frac{1}{2}(x+\frac{a}{x})<\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\ge 0$ as it is a square, so we have a contradiction. Thus, $f(x)\ge \sqrt{a}$.

• To show $f$ is a contraction, we compute $|f(x)-f(y)|$ for $x,y$ in $[\sqrt{a},\mathrm{\infty })$ and then seek to bound above by a fixed multiple of $|x-y|$. We begin with some algebra $$|f(x)-f(y)|=|\frac{1}{2}(x+\frac{a}{x})-\frac{1}{2}(y+\frac{a}{y})|=|\frac{1}{2}(x-y+\frac{a}{x}-\frac{a}{y})|.$$

  $$=|\frac{1}{2}(x-y+\frac{a(y-x)}{xy})|=|\frac{1}{2}(x-y)(1-\frac{a}{xy})|=\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\ge \sqrt{a}$, so $xy\ge a$ which imples $1\ge \frac{a}{xy}$ so $|1-\frac{a}{xy}|<1$, so $$\frac{1}{2}|1-\frac{a}{xy}||x-y|<\frac{1}{2}|x-y|,\text{for all }x,y\in [\sqrt{a},\mathrm{\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},\mathrm{\infty })$ is convergent with the limit of $\sqrt{a}$.

Example: approximate $\sqrt{3}$ using $f(x)=\frac{1}{2}(x+\frac{3}{x})$.

Start with $w_0=2$:

$$\begin{array}{rl}{w}_1& =\frac{1}{2}(2+\frac{3}{2})=\frac{1}{2}\cdot \frac{7}{2}=\frac{7}{4}=1.75\\ w_2& =\frac{1}{2}(1.75+\frac{3}{1.75})\approx \frac{1}{2}(1.75+1.71429)=\frac{1}{2}(3.46429)\approx 1.73214\\ w_3& =\frac{1}{2}(1.73214+\frac{3}{1.73214})\approx \frac{1}{2}(1.73214+1.73196)=\frac{1}{2}(3.4641)\approx 1.73205\end{array}$$

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},\dots$$ Is generated by iterating $f(x)=\sqrt{x}$.

• Prove that this map is a contraction map on the domain $[1,\mathrm{\infty })$, which guarantees this subsequence converges for every $a\ge 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\ge 1}{a}_k=\alpha$ and $\prod _{k\ge 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 \text{and}\prod _{k=1}^n{b}_k=B_n\to \beta$$ as $n\to \mathrm{\infty }$.

To study the infinite product $\prod _{k\ge 1}{a}_k{b}_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=(lim{A}_n)\cdot (lim{B}_n)=\alpha \beta .$$

Therefore $\prod _{k\ge 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\ge 1}\frac{1}{4n^2-1}$$ $$\prod _{n\ge 5}(1-\frac{1}{n^2})$$

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}(\frac{1}{2n-1}-\frac{1}{2n+1}).$$ Thus, $$\sum _{n=1}^N\frac{1}{4n^2-1}=\frac{1}{2}\sum _{n=1}^N(\frac{1}{2n-1}-\frac{1}{2n+1}).$$ This is a telescoping sum:

$$\begin{array}{rl}\sum _{n=1}^N& (\frac{1}{2n-1}-\frac{1}{2n+1})\\ & =(\frac{1}{1}-\frac{1}{3})+(\frac{1}{3}-\frac{1}{5})+(\frac{1}{5}-\frac{1}{7})+\cdots +(\frac{1}{2N-1}-\frac{1}{2N+1})\\ & =1+(-\frac{1}{3}+\frac{1}{3})+(-\frac{1}{5}+\frac{1}{5})+\cdots +(-\frac{1}{2N-1}+\frac{1}{2N-1})-\frac{1}{2N+1}\\ & =1-\frac{1}{2N+1}.\end{array}$$

This gives an exact formula for the partial sums: $$\sum _{n=1}^N\frac{1}{4n^2-1}=\frac{1}{2}(1-\frac{1}{2N+1}),$$ and taking the limit: $$\sum _{n\ge 1}\frac{1}{4n^2-1}=\underset{N}{lim}\frac{1}{2}(1-\frac{1}{2N+1})=\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(1-\frac{1}{n^2})=\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(1-\frac{1}{n^2})=\frac{4}{N}\cdot \frac{N+1}{5}=\frac{4(N+1)}{5N}.$$

Now its easy to take the limit as $N\to \mathrm{\infty }$: $$\underset{N\to \mathrm{\infty }}{lim}\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{array}{ccccccccc}{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{array}$$ We can see that for all of the terms $0\le a_n\le b_n$. Then just looking at $a_n$, we can see $$\begin{array}{rl}\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}+\underset{=\frac{1}{2}}{\underbrace{\frac{1}{4}+\frac{1}{4}}}+\underset{=\frac{1}{2}}{\underbrace{\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}}}+\cdots \end{array}$$

This means we have the following partial sums:

$$\sum _{1\le n\le 1}{a}_n=1\sum _{1\le n\le 2}{a}_n=1+\frac{1}{2}\sum _{1\le n\le 4}{a}_n=1+\frac{1}{2}+\frac{1}{2}$$ $$\sum _{1\le n\le 8}{a}_n=1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}\sum _{1\le n\le 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\le n\le 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\le a_n\le 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_k{b}_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|\le 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 $ϵ>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|<ϵ/B$. Then, for all $n>m\ge N$, we estimate:

$$\begin{array}{rl}\left|\sum _{k=m}^n{a}_k{b}_k\right|& \le \sum _{k=m}^n|a_k{b}_k|\\ & \le \sum _{k=m}^n|a_k|\cdot |b_k|\\ & \le \sum _{k=m}^n|a_k|\cdot B=B\sum _{k=m}^n|a_k|\\ & <B\frac{ϵ}{B}=ϵ\end{array}$$

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 $ϵ=1$, there exists some integer $N$ such that for all $k\ge 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\ge 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\ge N}{a}_k$ we get by deleting the first finitely many terms. Now since $a_k^p<a_k$ for $k\ge N$, it follows that $\sum _{k=N}^{\mathrm{\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}^{\mathrm{\infty }}{a}_k^p=\sum _{k=1}^{N-1}{a}_k^p+\sum _{k=N}^{\mathrm{\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=lim sup\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=\underset{n\to \mathrm{\infty }}{lim sup}\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: $$lim sup\sqrt[n]{|a_n|}=\underset{n\to \mathrm{\infty }}{lim}\underset{k\ge n}{sup}\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\ge N$: $\underset{k\ge n}{sup}\sqrt[k]{|a_k|}<r$. (Just using the limit definition, setting $ϵ$ to anything less than $r-L$.)

In particular, for all $k\ge N$, $$\sqrt[k]{|a_k|}\le \underset{j\ge k}{sup}\sqrt[j]{|a_j|}<r.$$ So for all $k\ge N$, we have: $$\sqrt[k]{|a_k|}<r\Rightarrow |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\ge N}|a_k|<\sum _{k\ge N}{r}^k.$ And $\sum _{k\ge 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}^{\mathrm{\infty }}|a_k|$ converges as well. Hence the series $\sum a_k$ converges absolutely, and therefore converges.

Case 2: $L>1$

Now assume $L=\underset{n\to \mathrm{\infty }}{lim sup}\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$, $$\underset{k\ge n}{sup}\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\Rightarrow |a_k|>r^k.$$ Since $r>1$, we know that $r^k>1$ for large $k$, so $|a_k|>1$ infinitely often. Therefore: $$\underset{k\to \mathrm{\infty }}{lim}|a_k|\nrightarrow 0.$$ Hence $a_k\nrightarrow 0$, and by the Divergence Test, the series $\sum a_k$ diverges.