Assignment 5
Exercise 1 (Real Number Powers) On a previous homework you proved that for a real number \(a>1\) if \(r_1\leq r_2\) are any rational numbers then \(a^{r_1}\leq a^{r_2}\). In class we used this to help us extend the definition of the powers to all real value inputs. Recall if \(x\in\RR\) we choose a monotone increasing sequence \(r_n\to x\) of rational numbers, and define \[a^x :=\lim a^{r_n}\]
Using this definition, show that raising to a power is a monotone increasing function when \(a>1\): that is, if \(x,y\) are any real numbers with \(x\leq y\) then \(a^x\leq a^y\).
Solution. Choose a monotone increasing sequence \(x_n\) of rational numbers with \(x_n\to x\) and similarly a monotone sequence \(y_n\to y\). By definition, we can write \(a^x\) and \(a^y\) as limits \[a^x=\lim a^{x_n}\hspace{1cm} a^y = \lim a^{y_n}\]
If \(x=y\) then we could have chosen \(x_n=y_n\) for all \(n\), so \(a^{x_n}=a^{y_n}\) and thus \(\lim a^{x_n}=\lim a^{y_n}\), giving \(a^x=a^y\). So, we really only need to consider the case \(x\neq y\). Here, choose \(\epsilon = y-x>0\). Using that \(y_n\to y\) we know there is some \(N\) such that for \(n>N\) we have \(|y_n-y|<\epsilon\). Unpacking this, we find \[n>N\,\implies\, y_n>x\]
Since the sequence \(x_n\) is monotone increasing, we know \(x_n<\sup\{x_n\}=\lim x_n=x\) for all \(n\) and so for \(n>N\) we may string these inequalities together to yield \[n>N\,\implies \, x_n<x<y_n\hspace{1cm} x_n<y_n\]
Using what we know about rational exponents, this implies that \(a^{x_n}< a^{y_n}\) for all \(n>N\), and so \(a^{y_n}-a^{x_n}>0\). Beacause we know each of these converges, the limit theorems guarantee that \(a^{y_n}-a^{x_n}\) converges, with limit \(a^y-a^x\). Furthermore since this sequence is all positive nubmers the limit theorems guarantee its limit cannot be negative. That is \[a^y-a^x = \lim (a^{y_n}-a^{x_n})\geq 0\]
Re-arranging, \(a^y\geq a^x\) as required.
Exercise 2 (Infinite Powers) This problem directly uses the fact we proved in the previous homework exercise: if \(a>1\) is the base of an exponential and \(x\leq y\) then \(a^x\leq a^y\).
Construct the following recursive sequence, called a “power tower” for any number \(x\): \(s_0=1,\hspace{0.5cm}s_{n+1}=x^{s_n}\). Thus \(s_1=x\), \(s_2=x^x\), \(s_3=x^{x^x}\), etc.
Prove that the infinite power tower for \(x=\sqrt{2}\) is a convergent sequence, and find its limit. Hint: show is monotone and bounded. Find an equation the limit should satisfy, and solve it.
Solution. We first check \((s_n)\) is monotone increasing by induction. The base case \(n=1\) can be checked directly: \[s_1 = \sqrt{2}^1 < \sqrt{2}^{\sqrt{2}} = s_2\]
because of the hint and the fact that \(1 < \sqrt{2}\). Now to the inductive step. Let us assume that \(s_{n-1} < s_n\). Since we know whenever \(x<y\) then \(b^x<b^y\) we can apply this to see \[\sqrt{2}^{s_{n-1}}<\sqrt{2}^{s_n}\]
But by the definition of our recursive sequence, this is just \(s_n < s_{n+1}\), which is what we wanted to prove.
We now check \((s_n)\) is bounded above by \(3\) by induction. The base case \(n =1\) can be checked directly: \[ s_1 = \sqrt{2} < 3. \]
Now to the inductive step. Let us assume that \(s_{n} < 3\). We show \(s_{n+1} < 3\). Using the hint we see that
\[ s_{n+1} = \sqrt{2}^{s_{n}} < \sqrt{2}^3 < 3, \]
Thus, \(s_n\) is monotone increasing and its bounded above, so it converges by Monotone Convergence. Let’s call the limit \(L\). Since \(\lim s_{n+1}=\lim s_n = L\), and \(s_{n+1}=\sqrt{2}^{s_n}\), we see that the limit should satisfy \[L=\sqrt{2}^L\]
What values of \(L\) satisfy such an equation? W can see by inspection that \(L=2\) works as \[2=\sqrt{2}^2\] And so \(L=4\) also works, since \[4=\sqrt{2}^4=(2)^2\]
(These are the only two solutions, which is harder to check with the tools we have right now than anticipated so its OK if we don’t prove these are the only possibilities here. Apologies! We will have the tools to do this kind of thing soon, when we study continuity)
Which of these must be the limit? We know from our proof the sequence is bounded above by \(3\), so \(L\leq 3\). Thus, the limit must be \(2\).
Exercise 3 (The Number \(e\)) Read the section about the number \(e\) in the book’s chapter on Monotone Convergence. Then following the strategy I use for the sequence \(a_n\), prove the sequence \(b_n=\left(\frac{n+1}{n}\right)^{n+1}\) is monotone decreasing, and bounded below.
Solution. To show that the sequence \(b_n=(\frac{n+1}{n})^{n+1}\) is monotone decreasing, we can do the inverse of what was done for the sequence \(a_n\), we want to show that \(\dfrac{b_n}{b_{n-1}}\leq 1\), and because we know that this sequence is going to be positive, we can instead show that \(\dfrac{b_{n-1}}{b_n}\geq 1\).
\[\begin{align*} \frac{b_{n-1}}{b_n} &= \dfrac{\left(\frac{n}{n-1}\right)^n}{\left(\frac{n+1}{n}\right)^{n+1}} \\ &= \left(\frac{n}{n-1}\right)^n \cdot \left(\frac{n}{n+1}\right)^{n+1} \\ &= \left(\frac{n-1}{n}\right) \left(\frac{n^2}{n^2-1}\right)^{n+1} \\ &= \left(\frac{n-1}{n}\right) \left(1+\frac{1}{n^2-1}\right)^{n+1} \\ \end{align*}\]
Using Bernoulli’s Inequality we can do the following
\[\begin{align*} \left(\frac{n-1}{n}\right) \left(1+\frac{1}{n^2-1}\right)^{n+1} &\geq \left(\frac{n-1}{n}\right)\left(1+\frac{n+1}{n^2-1}\right) \\ &\geq \left(\frac{n-1}{n}\right)\left(1+\frac{1}{n-1}\right) \\ &\geq \left(\frac{n-1}{n}\right)\left(\frac{n}{n-1}\right) \\ &=\frac{n-1}{n-1}\frac{n}{n}\\ & = 1 \end{align*}\]
Since \(\frac{b_{n-1}}{b_n} \geq 1\), multiplying through by the denominator shows \(b_{n-1}\geq b_n\) and so \(b_n\) is monotone decreasing.
We know that it is bounded by below because it is a positive sequence, so it is automatically bounded below by 0. Because it is both monotone decreasing and bounded below we know that it converges by the monotone convergence theorem.
Exercise 4 (Infinite Roots) We saw in class that the sequence \(\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}\) converges to the golden ratio. Find a similar recursive sequence whose limit is the positive real root of \(x^2-2x-5\) (and prove it converges to the correct value).
Solution. If \(x\) is a positive number that satisfies \(x^2-2x-5=0\) then \(x^2=2x+5\), or (as \(x\) is positive) \[x=\sqrt{5+2x}\] This suggests a recursive sequence: starting with any value for \(s_0\) (say, \(s_0=0\)) we may define \(s_{n+1}=\sqrt{5+2s_n}\). Now we follow the exact proof technique in the book, showing this is monotone and bounded, by induction.
To see its increasing: take the base case \(s_0=0\) and \(s_1=\sqrt{5+2s_0}=\sqrt{5}\), so \(s_0<s_1\). For the induction step, assume \(s_{n-1}<s_n\), and build up the next terms using the definition:
\[s_{n-1}<s_n\implies 2s_{n-1}<2s_n\implies 5+2s_{n-1}<5+2s_n\implies \sqrt{5+2s_{n-1}}<\sqrt{5+2s_n}\] The final inequality in this chain is the definition of \(s_{n}<s_{n+1}\), so we’ve succeeded in the induction.
To prove its bounded, we know we are trying for a sequence that converges to the positive root of \(x^2-2x-5=0\), which is \(1+\sqrt{6}\) or approximately \(3.449\). Thus we might take an upper bound of 4. As a base case, note \(s_0=0<4\). For induction, assume \(s_n<4\). Then \[s_n<4\implies 2s_n<8\implies 5+2s_n<13\] Since \(13<16\), this implies \(\sqrt{5+2s_n}<\sqrt{16}=4\), so the induction succeeds. Thus, our sequence is monotone and bounded, so we can apply monotone convergence to see it must converge to some limit \(L\).
Finally, we investigate the value of this limit \(L\). We know \(L=\lim s_n\) by definition. But since truncating the first term of a sequence doesn’t change its limit, we also know \(L=\lim s_{n+1}\). Using the recursive definition of the sequence, this means \[L=\lim\sqrt{5+2s_n}\]
Now we can use the limit laws: since \(s_n\to L\) we know \(2s_n\to 2L\) and \(5+2s_n\to 5+2L\). Finally using the limit law for square roots, this implies \(\sqrt{5+2s+n}\to\sqrt{5+2L}\) since the sequence and limit are both nonnegative (as \(s_0=0\) and we proved its increasing). Putting this together, we see the limit \(L\) satisfies \(L=\sqrt{5+2L}\), so \(L\) is positive and \(L^2=5+2L\), or \(L^2-2L-5=0\), which is exactly what we claimed.
Exercise 5 (Infinite Fractions) We saw in class that the continued fraction \[1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots}}}\] converges to the golden ratio. What number does the following generalization converge to? \[1+\frac{1}{2+\frac{1}{1+\frac{1}{2+\frac{1}{1+\frac{1}{2+\frac{1}{1+\frac{1}{2+\cdots}}}}}}}\]
Prove your claim.
Solution. In class, we defined a sequence recursively by \(s_{n+1}=1+\frac{1}{s_n}\) to generate the continued fraction for the golden ratio. Here, our continued fraction doesn’t repeat every step, but takes two steps to repeat. This means we might want to define our sequence as \[s_{n+1}=1+\frac{1}{2+\frac{1}{s_n}}\] Together with some starting value, like \(s_0=1\). We would like to prove this sequence converges with monotone convergence, so let’s compute a couple terms and investigate the values.
\[s_0=0\hspace{1cm} s_1=\frac{4}{3}\approx 1.333\hspace{1cm} s_2=1.3636..\]
Thus (unlike our sequence from class, which zig-zagged and we needed to break into two sequences) this appears to be directly increasing, so lets try to prove that and prove that its bounded above.
Let’s start with the increasing bit, and use induction. Our experimental work above is good as a base case, as we saw \(s_0<s_1\). So now assume that \(s_{n-1}<s_n\) and we’ll try to prove that \(s_n<s_{n+1}\), by building up the next terms using the definitions. Here
\[s_{n-1}<s_n\implies \frac{1}{s_{n-1}}>\frac{1}{s_n}\implies 2+\frac{1}{s_{n-1}}>2+\frac{1}{s_n}\]
Taking reciprocals reversed the inequality. So, doing it again will flip it again!
\[ 2+\frac{1}{s_{n-1}}>2+\frac{1}{s_n}\implies \frac{1}{2+\frac{1}{s_{n-1}}}<\frac{1}{2+\frac{1}{s_n}}\implies 1+\frac{1}{2+\frac{1}{s_{n-1}}}<1+\frac{1}{2+\frac{1}{s_n}}\]
But the last terms here are precisely the definitions of \(s_n\) and \(s_{n+1}\) respectively, so we’ve proven \(s_n<s_{n+1}\) as required for our induction.
Next, we wish to show its bounded above, by induction. We did not compute too many terms in our experiments, so its hard to tell if 2 will be an upper bound or not. But let’s give it a shot. The base case is true as \(s_0=1\). So assume \(s_n<2\). Then \[s_n<2\implies \frac{1}{s_n}>\frac{1}{2}\implies 2+\frac{1}{s_n}>2+\frac{1}{2}=\frac{5}{2}\] and so, taking reciprocals again \[\implies \frac{1}{2+\frac{1}{s_n}}<\frac{2}{5}\implies 1+\frac{1}{2+\frac{1}{s_n}}<1+\frac{2}{5}=\frac{7}{5}\]
And, as \(7/5<2\) we’re done! We’ve proven \(s_{n+1}<2\), completing the induction. This means our sequence is monotone increasing and bounded above, so it converges by Monotone Convergence to some limit \(L\). To find the value of this limit, we note \(\lim s_{n+1}=L\) as well (truncating the first term doesn’t change the limit) but then we can compute \(\lim s_{n+1}\) a second way using the limit laws:
Since \(s_n\to L\), we know \(\frac{1}{s_n}\to \frac{1}{L}\) (to use the limit law for reciprocals we need to check a couple things here: (1) \(s_n\) is nonzero because \(s_0=1\) and the sequence is monotone increasing (2) its limit is also \(>1\) and thus not zero, since its monotone increasing starting at 1). Now adding the constant sequence \(2\), we see \(2+\frac{1}{s_n}\to 2+\frac{1}{L}\) and we can again use the limit law for reciprocals (since \(2+1/L\) is greater than 2, and thus nonzero) to conclude \[\frac{1}{2+\frac{1}{s_n}}\to\frac{1}{2+\frac{1}{L}}\] and finally, adding the constant sequence 1 that \[\lim s_{n+1}=\lim 1+\frac{1}{2+\frac{1}{s_n}}=1+\frac{1}{2+\frac{1}{L}}\]
Putting it all together we find that \(L\) must satisfy the equation \[L=1+\frac{1}{2+\frac{1}{L}}\]
To find \(L\) we need to solve this equation (and remember that \(L\geq 1\) is positive). Simplifying
\[L=1+\frac{L}{2L+1}\implies L(2L+1)=2L+1+L=3L+1\] \[\implies 2L^2+L=3L+1\implies 2L^2-2L-1=0\]
Thus our solution \(L\) sovles this quadratic, so
\[L=\frac{2\pm\sqrt{2^2-4\cdot 2\cdot(-1)}}{2\cdot 2}=\frac{2\pm\sqrt{12}}{4}=\frac{1\pm\sqrt{3}}{2}\]
Only one of these two possibilities is positive, and so we have singled out the limit \(L\):
\[L=\frac{1+\sqrt{3}}{2}\approx 1.36602\ldots\]