Assignment 1
Exercise 1 (Computing Cube Roots) Can you modify the babylonians procedure which found approximates of \(\sqrt{2}\) to instead find rational approximates of \(\sqrt[3]{2}\)?
Here, instead of starting with a rectangle of sides \(x,y\) let’s start with a three dimensional brick with a square base (sides \(x\) and \(x\)), height \(y\), and area \(2\). Our goal is to find a “closer to cube” shaped brick than this one, and then to iterate. Propose a method of getting “closer to cube-shaped” and carry it out: what are the side lengths of the next shape in terms of \(x\) and \(y\)?
Start with a simple rectangular prism of volume \(2\) and iterate this procedure a couple times to get an approximate value of \(\sqrt[3]{2}\). How close is your approximation?
Solution. Starting with a rectangular prism with a square base of length \(x\) and height \(y\), we can produce a more cube-like one by taking the new \(x\) value to be the average of the three side lengths, and the new \(y\) value to be whatever is needed to keep the volume equal to 2. In symbols, this produces a recursive sequence
\[ x_n = \dfrac{2x_{n-1}+y_{n-1}}{3} \;\;\; \text{and} \;\;\; y_{n} = \dfrac{2}{x_{n}^2} \]
Starting with \(x_0=1\) and \(y_0=2\) we can find the next few terms: \[ \renewcommand{\arraystretch}{2.5} \begin{array}{cc|cc} x_1=& \dfrac{2x_{0}+y_{0}}{3}=\dfrac{2(1)+2}{3}=\dfrac{4}{3}& y_1=& \dfrac{2}{(\frac{4}{3})^2}=\dfrac{2}{1}\cdot \dfrac{9}{16}=\dfrac{9}{8} \\ x_2= & \dfrac{2x_1+y_1}{3}= \dfrac{2(\frac{4}{3})+\frac{9}{8}}{3} = \dfrac{\frac{91}{24}}{3}=\dfrac{91}{72}& y_2=& \dfrac{2}{(\frac{91}{72})^2}=\dfrac{2}{1}\cdot \dfrac{5184}{8281} =\dfrac{10368}{8281} \\ x_3= & \dfrac{2x_2+y_2}{3}=\dfrac{2(\frac{91}{72})+\frac{10368}{8281}}{3}=\dfrac{1126819}{894348} & y_3= &\dfrac{2}{(\frac{1126819}{894348})^2}=\dfrac{1599716690208}{1269721058761} \end{array} \] The approximation at \(x_3=1.25993349345\) is very close to the actual answer for \(\sqrt[3]{2}=1.25992104989\).
Exercise 2 (Irrationality) Following analogous logic to that of Pythagoras, prove that \(\sqrt{3}\) is irrational. Generalize this to prove that \(\sqrt{6}\) is irrational.
Solution. Assume to the contrary that \(\sqrt{3}\) is rational. Then let \(p,q\in\mathbb{Z}\) such that \(\frac{p}{q}=\sqrt{3}\) and \(\frac{p}{q}\) is in lowest terms. From this expression, we can square both sides and then multiply by \(q^2\): \[\begin{align} \frac{p}{q}=&\,\sqrt{3}\\ \frac{p^2}{q^2}=&\,3\\ p^2=&\,3q^2 \end{align}\] Given this equality, and that \(p,q\in\mathbb{Z}\), we must have \(3|(p\cdot p)\). Since 3 is prime, by Euclid’s Lemma, either \(3|p\) or \(3|p\). Then \(p\) must be a multiple of 3, so we can write \(p=3\cdot k\) for some \(k\in\mathbb{Z}\). Then our expression after substituting and simplifying becomes \[\begin{align} (3k)^2=3q^2\\ 9k^2=3q^2\\ 3k^2=q^2 \end{align}\] By the same process, since 3 is prime, Euclid’s Lemma tells us that either \(3|q\) or \(3|q\), so \(q\) is a multiple of 3, and can hence be written as \(q=3\cdot m\). Then, examine our starting fraction, which can be written as \[\begin{align} \frac{p}{q}=\frac{3k}{3m} \end{align}\] This is a contradiction! We specified that our fraction was in lowest terms, yet we found a common factor of 3. We know that rational numbers can be constructed out of ratios of integers, and that any rational number can be written in lowest terms, so the false assumption must have been that \(\sqrt{3}\) was rational. Thus, \(\sqrt{3}\) must be irrational.
We can extend this proof to \(\sqrt{6}\). Assume to the contrary that \(\sqrt{6}\) is rational, such that there are integers \(p\) and \(q\) where \(\frac{p}{q}=\sqrt{6}\), and \(\frac{p}{q}\) is in lowest terms. Then we have that \[\begin{align} \frac{p}{q}=&\sqrt{6}\\ \frac{p^2}{q^2}=&6\\ p^2=&6q^2=3\cdot(2q^2) \end{align}\] By Euclid’s Lemma, \(3|p\) or \(3|p\), so \(p=3k\) for some \(k\in\mathbb{Z}\). Then \[\begin{align} (3k)^2=&3\cdot(2q^2)\\ 3\cdot(3k^2)=&3\cdot(2q^2)\\ 3k^2=2q^2 \end{align}\] Then, again by Euclid’s Lemma, since \(3\nmid2\), either \(3|q\) or \(3|q\). We therefore end up with a common factor of 3, which contradicts our assumption that the fraction is in lowest terms, and by similar process of elimination as the above proof, our false assumption must have been that \(\sqrt{6}\) was rational. Hence, \(\sqrt{6}\) is irrational.
Exercise 3 (Irrationality, II) Show where the argument you give above for \(\sqrt{6}\) fails if you instead consider \(\sqrt{9}\) (which is rational!)
Solution. Attempting to this method of proof to \(\sqrt{9}\) fails when we are generating the common factor. We can prove that the numerator is separated from the denominator by only an extra factor of 3, but this is true! Since 9 is the square of 3, \(\sqrt{9}=3\), so any rational representation of \(\sqrt{9}=3\) will have an additional factor of 3 in the numerator. Assuming that \(\sqrt{9}\) is rational, and represented by \(\frac{p}{q}=\sqrt{9}\), where \(p,q\in\mathbb{Z}\) and \(\frac{p}{q}\) is in lowest terms, we have \[\begin{align} \frac{p}{q}=\sqrt{9}\\ \frac{p^2}{q^2}=9\\ p^2=3\cdot(3q^2) \end{align}\] By Euclid’s Lemma, we have from the first factor of 3 that \(3|p\) or \(3|p\), and from the second factor of 3 that \(3|p\) or \(3|p\), so \(p=3k\) for some \(k\in\mathbb{Z}\). Then, substituting this back into the expression, we have that \[\begin{align} (3k)^2=9q^2\\ 9k^2=9q^2\\ k^2=q^2 \end{align}\] There is no contradiction here, so we cannot prove that \(\sqrt{9}\) is irrational this way, and indeed, choosing any solution to \(k^2=q^2\) (even just \(k=q=1\)) gives us a rational number which squares to 9.
Definition 1 (The Babylonian Algorithm and Number Theory) Because \(\sqrt{2}\) is irrational, there is no pair of integers \(p,q\) with \(p^2=2q^2\). Good rational approximations to \(\sqrt{2}\) will almost satisfy this equation, so the closer \(p^2\) is to \(2q^2\) the closer \(p/q\) is to \(\sqrt{2}\). If \(p\) and \(q\) are integers, the best we can hope for is these values to be one apart. Thus, we will call \(p/q\) an excellent approximation to \(\sqrt{2}\) if \[p^2=2q^2+1\]
Exercise 4 (The Babylonian Algorithm and Number Theory) Prove that all approximations produced by the babylonian sequence starting from the rectangle with sides \(1\) and \(2\) are excellent, by induction.
Solution. Base Case: the goal is to show the babylon procedure always produces excellent approximations, and so the first new side it produces starting from \(x=2,y=1\) is \(x_1=\frac{3}{2}\): this is an excellent approximation as \[\frac{p}{q}=\frac{3}{2} \implies \] \[p^2=3^2=9\hspace{1cm} 2q^2+1=2*2^2+1=9\] Induction: Assume that all of the outputs up to and including the \(n^{th}\) step of the babylonian process are excellent approximations. In particular for the \(n^{th}\) step, say we have \(x_n=p/q\) (and thus \(y_n=\frac{2}{x_n}=\frac{2}{p/q}\)), where \(p^2=2q^2+1\).
Then for the \(n+1^{st}\) step, we have \[x_{n+1} = \frac{\frac{p}{q}+\frac{2}{\frac{p}{q}}}{2}=\frac{\frac{p^2+2q^2}{pq}}{2}=\frac{p^2+2q^2}{2pq}\]
For this new approximation to be excellent, we need that its numerator squared is twice the square of the denominator, or \[(p^2+2q)^2=2(2pq)^2+1\] We need to use the induction hypothesis \(p^2=2q^2+1\) to deduce this: and we proceed starting with what we want, and doing algebra to reduce it to something we know.
\[(p^2+2q)^2=2(2pq)^2+1\] \[p^4+4p^2q^2+4q^2=8p^2q^2+1\] \[p^4-4p^2q^2+4q^2=1\] \[(p^2-2q^2)^2=1\] \[p^2=2q^2+1\] Because this last line is the induction hypothesis, we know its true! And as all the rules of algebra are reversible the original line (what we want) is also true. So, we are done: every approximation is excellent by induction.
In class we looked at Archimedes’ argument for determining the perimeter of a circle by circumscribing it with \(n\)-gons. The idea was that since the \(n\) gons got closer and closer to the circle, their perimeters should get closer and closer to the circle s perimeter, so we could use them to approximate the circumference.
The exercise below shows a way this type of argument can fail! We will look at a sequence of polygons which are converging to a triangle (the difference in area between them and the triangle they approximate is getting smaller and smaller), even though the perimeter of these polygons is not at all approaching the perimeter of the triangle.
Exercise 5 (Convergence to the Diagonal) Consider the right triangle whose legs are length 1. Define a sequence \(T_n\) of polygons approximating this triangle as follows. Let \(T_0\) denote the unit square, and \(T_n\) denote the polygon formed by \(n\) equal “steps” approximating the triangle:
- Prove that as \(n\) goes to infinity the area of the polygons \(T_n\) do converge to the area of the triangle (Hint: can you write down a formula for the total error between \(T_n\) and the triangle, as a sum of the areas of small triangles that you can calculate?)
- prove that the length of the zig-zag diagonal side of the \(T_n\) has length \(2\) always, independent of \(n\), and so the perimeter of each polygon \(T_n\) in the sequence is 4. Thus, following the style of argument of archimedes, we should be tempted to conclude the perimeter of the limiting shape is also 4.
This is a problem! The pythagorean theorem tells us that the hypotenuse of the triangle must be \(\sqrt{1^2+1^2}=\sqrt{2}\), so the perimeter should be \(2+\sqrt{2}\). Thus, if we believe both our argument inspired by Archimedes calculation and Pythagoras’ argument, we are forced to conclude that \(4=2+\sqrt{2}\), or \(2=\sqrt{2}\) which is false!
Solution. While investigating these approximations, we can look at the error involved in each of them when approximating the given right triangles area. Looking at the figure below, we can see that the total error for a given approximation is equal to the area of the light blue shaded triangles. For \(T_n\), the approximation with \(n\) equal steps, each small triangle has an area of \(\frac{1}{2(n+1)(n+1)}\), and there are \((n+1)\) total triangles contributing to the area. So, the total error is equal to \(\frac{(n+1)}{2(n+1)(n+1)} = \frac{1}{2(n+1)}\). As \(n \rightarrow \infty\), the total error goes to 0, so the area of the polygon approximation converges to the area of the triangle.
However, the length of the approximation of the diagonal never shrinks. If we look at how the length changes between the approximation \(T_0\) and \(T_1\), we see that it doesn’t actually change. There is a square that is cut out of the area, but this removal doesn’t change the length. The two side lengths that are removed from the total length (the top and left side of the square) are once again added to the total length through the new side lengths added, on the bottom and right sides of the square. This phenomenon of simply removing a square continues with higher approximations, as we go from \(T_0 \rightarrow T_1 \rightarrow T_3 \rightarrow T_7 \rightarrow ... \rightarrow T_{2^n-1}\). In each case, the length of the approximation is not changed because it is only squares that are being removed (and two original sides of the square are replaced with two new sides of the square, at the next level).
Thus, as \(n \rightarrow \infty\), the length remains the same for every \(n\), thus leading to the conclusion that the length of the diagonal of the triangle is equal to 2. (This is actually false because of the infinite number of ridges along the diagonal of the polygon approximations as \(n \rightarrow \infty\), so while the area of the approximation converges to the triangles area, the diagonal length does not do the same).
Now we turn to look at the practical details of Archimedes’ and Zu Chongzi’s estimates of \(\pi\). We saw in class there is a nice formula for the perimeter \(P_n\) of the \(n\)-gon circumscribing the circle in terms of trigonometry: \[P_n = 2n\tan\frac{180}{n}\]
But this is useless to us in practice unless we can actually compute the values of the tangent function! Archimedes’ big idea was that he could simplify things alot if he considered doubling a polygons number of sides. That is, the goal is to compute a formula for the number \(P_{2n}\), assuming you already know the number \(P_n\).
Exercise 6 Let \(t_n=\tan(180/n)\).
- Show that \(t_n\) satisfies the recurrence relation \[t_{2n}=\sqrt{1+\frac{1}{t_n^2}}-\frac{1}{t_n}\]
Hint: you’ll need some trig identities reviewed in the text to write everything in terms of tangent!
- Use this to find a recurrence relation for \(P_n\).
- Use this to find a recurrence relation for \(P_n\).
- Find the perimeter of the square circumscribing the unit circle. Use this and your recurrence formula to find the perimeter of the octagon and 16 gon that circumscribe the unit circle.
Solution. The half-angle identity for tangent from trigonometry tells us that \[\tan\frac\theta 2 =\frac{1-\cos\theta}{\sin\theta}\]
So this gives us the tangent of half the angle in terms of \(\sin\) and \(\cos\) of the angle, but we seek a formula in terms of \(\tan=\sin/\cos\) instead. To get one, we need to do some manipulations with trigonometric identities:
\[\begin{align*} \tan\frac\theta 2 &=\frac{1}{\sin\theta}-\frac{\cos\theta}{\sin\theta}\\ &=\csc\theta -\cot\theta\\ &=\sqrt{\csc^2\theta}-\frac{1}{\tan\theta}\\ &=\sqrt{1+\cot^2\theta}-\frac{1}{\tan\theta}\\ &=\sqrt{1+\frac{1}{\tan\theta}}-\frac{1}{\tan\theta} \end{align*}\]
This trigonometric identity holds for any value of \(\theta\), so, plugging in \(\theta = 180/n\) we see
\[\tan\left(\frac{180}{2n}\right)=\sqrt{1+\frac{1}{\tan^2\left(\frac{180}{n}\right)}}-\frac{1}{\tan\left(\frac{180}{n}\right)}\]
Which is exactly what we were asked to show: \(t_{2n}=\sqrt{1+\frac{1}{t_n^2}}-\frac{1}{t_n}\). Now, the tangent of \(180/n\) only gives us half the side length of the circumscribing \(n\)-gon, so to get the full perimeter \(P_n\) we need to multiply by \(2n\), which gives \(P_n = 2nt_n\), or (solving for \(t_n\)) \[t_n=\frac{P_n}{2_n}\]
Substituting this into our trigonometric identity takes it from a recurrence for \(t_{2n}\) in terms of \(t_n\), to a recurrence for \(P_{2n}\) in terms of \(P_n\):
\[\frac{P_{2n}}{2\cdot 2n}=\sqrt{1+\frac{1}{\frac{P_n}{2n}}}-\frac{1}{\frac{P_n}{2n}}\]
Simplifying the algebra a bit yields
\[P_{2n}=4n\left(\sqrt{1+\frac{2n}{P_n}}-\frac{2n}{P_n}\right)\]
We can now use this to easily find the perimeter of an octagon circumscribing the circle, starting from the square. The square has four sides, each a diameter of the circle, so its perimeter is \(P_4=4\cdot 2 = 8\). Plugging this in we get
\[P_8=4\cdot 4\left(\sqrt{1+\frac{2\cdot 4}{8}}-\frac{2\cdot 4}{8}\right)=16\left(\sqrt{2}-1\right)\]
Exercise 7 In his argument solving the Basel problem, Euler crucially uses that if we know
- all the zeroes of a function
- the value of that function is 1 at \(x=0\)
then we can factor the function as an infinite polynomial in terms of its zeroes. This implies that a function is completely determined by its value at \(x=0\) and its zeroes (because after all, once you know that information you can just write down a formula like Euler did!) This is absolutely true for all finite polynomials, but it fails spectacularly in general.
Show that this is a serious flaw in Euler’s reasoning by finding a different function that has all the same zeroes as \(\sin(x)/x\) and is equal to \(1\) at zero (in the limit)!
Solution. If \(f(x)\) is any function, we can find a function which has the same zeroes as \(f\) by multiplying it by any positive function \(g\) (positive meaning it only outputs positive numbers, and thus never outputs zero). To see this has the same zeroes, note that \(f(x)g(x)=0\) means either \(f(x)=0\) or \(g(x)=0\), and since \(g(x)>0\forall x\), we must have \(f(x)=0\).
To make it so that the new combined function also takes the same value at \(x=0\), all we need is that \(g(0)=1\) as then \(f(0)g(0)=f(0)1=f(0)\).
Thus, for any \(f\), the following functions all have the same zeroes and same value at zero as \(f\):
\[e^x f(x)\hspace{1cm} \left(1+\frac{1}{2}\sin x\right)f(x)\hspace{1cm} (x^2+1)f(x)\hspace{1cm}\textrm{etc...}\]
For a concrete example we can take \(\frac{e^x\sin{x}}{x}\) to have the same zeroes and value at zero as Euler’s function \(\sin(x)/x\).