1. A few years ago I made an exploration of some simple concepts that led to some fun facts and a sequence of numbers I later learned is quite well-known. It may even rival the Fibonacci sequence in its fame.

I thought it might be nice to collect my notes and present my findings here. I thought I would present a small portion once a week, so that others can have a chance to give feedback and add their own insights.

My own personal discovery of the Pell numbers began with a simple desire to find good rational approximations of the square root of two. I thought of poor Pythagoras and his mystic cult of followers, called the Brotherhood, struggling with the irrationality of the square root of two in ancient Greece. I pictured them, in their togas, sandals and olive laurels, toiling in vain under the hot Greek sun with sharpened sticks in the wet coastal sand trying to find a right isosceles triangle having natural side lengths.

In their arsenal was one of the best known theorems from plane geometry, which incidentally happens to incorrectly bear the name of Pythagoras. The Brotherhood did reportedly independently discover this truth, yet later it was found to be known for centuries to the Babylonians and Indians, among others.

Pythagoras had had much success describing nature with natural numbers, most notably with his well-tempered musical scale, and it was shocking to him and the Brotherhood that something as simple as the diagonal of a unit square could not be described with rational numbers, i.e., that it would be "incommensurable."

One can easily understand that attitude from a naive perspective on number theory well over two thousand years ago. The square root of two is thought to be the first irrational number discovered.

Yet the zealous Brotherhood would never be able to get closer than one tantalizing unit away from the legs of the triangle being equal using natural numbers, and as they progressed, the numbers would have grown to overwhelming magnitudes very quickly. It must be a trap set by the petulant gods, they might have thought, to keep man in his place and in ignorance of the true inner workings of the universe. As it turns out, while this search will never reveal the impossible rational representation for the square root of two, it is far from a fruitless search.

Were it not for the irrationality of the square root of two, we would obviously be able to find a Pythagorean triple of the form $\displaystyle (a,a,c)$ where, of course $\displaystyle \frac{c}{a}=\sqrt{2}$. We will now confirm the irrationality of root two with (hopefully) no worries of being executed for divulging a mystical mathematical secret to the public.

Comments and questions to this topic should be posted here:

2.

Now, let’s look at Euclid’s proof that the square root of two is irrational.

Let us assume that the root of two is rational and represent it as such:

$\displaystyle \sqrt{2}=\frac{p}{q}$

p and q are assumed to be co-prime integers, i.e., the fraction is fully reduced.

Solve for p and square both sides:

$\displaystyle p^2=2q^2$

We will see later that an approximation to this relationship, namely

$\displaystyle p^2-2q^2=\pm1$

will yield the best rational approximations to the square root of two. For now though, we see that p must be even, since its square is even, making q odd since they are co-prime. We can then let $\displaystyle p=2m$ and $\displaystyle q=2n+1$ to represent an even and odd number respectively.

$\displaystyle (2m)^2=2(2n+1)^2$

Expansion of the squares yields:

$\displaystyle 4m^2=2(4n^2+4n+1)$

Divide through by 2 and partially factor the right side:

$\displaystyle 2(m^2)=2(2(n^2+n))+1$

Let $\displaystyle u=m^2$ and $\displaystyle v=2(n^2+n)$ and substitute:

$\displaystyle 2u=2v+1$

Here we absurdly have an even natural number being equal to an odd one. This impossibility means without a doubt that the assumption we made regarding the rationality of the square root of two is false. We can also look at it this way by dividing through by 2:

$\displaystyle u=v+\frac{1}{2}$

This of course is also impossible for natural numbers, to be one half unit apart. This is what's known as proof by reductio ad absurdium. You begin with an assumption and then reduce the statement to an absurdity, thereby proving the assumption to be false.

This is essentially the proof given by Euclid in his The Elements.

If we use the well-known method of Euclid for generating Pythagorean triples $\displaystyle (a,b,c)$ where $\displaystyle a^2+b^2=c^2$ , we should now not be surprised to find that a triple where $\displaystyle a=b$, will force a contradiction of the terms of the method.

However, we can set the two legs of the triangle one unit apart in length and try to find successively larger triangles that more closely approximate right-angled isosceles triangles, leading naturally to rational approximations for the square root of two, my motivation for using this method.

As the lengths of the sides increase in magnitude, with legs a and b restricted to being one unit apart in measure, this constant unit differential will shrink in comparison to the growing dimensions of the resulting triangles. This would be true for any constant difference between the legs, but using the smallest possible difference will lead to the best approximations and will also force the triples to be primitive. So, let's continue with the method for finding Pythagorean triples as described by Euclid in his The Elements and witness what transpires.

Euclid's Method for Generating Pythagorean Triples

First, pick two natural numbers m and n, such that $\displaystyle 0<n<m$. Now we simply generate the integral side lengths $\displaystyle (a,b,c)$ as follows:

$\displaystyle a=m^2-n^2$

$\displaystyle b=2mn$

$\displaystyle c=m^2+n^2$

Here is why this always works:

By Pythagoras, we know we must have:

$\displaystyle a^2+b^2=c^2$

Substitute for a, b, and c the values given above:

$\displaystyle (m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2$

Expand left side:

$\displaystyle m^4-2m^2n^2+n^4+4m^2n^2=(m^2+n^2)^2$

Collect like terms:

$\displaystyle m^4+2m^2n^2+n^4=(m^2+n^2)^2$

Factor left side:

$\displaystyle =(m^2+n^2)^2=(m^2+n^2)^2$

Therefore this must be true for all $\displaystyle (n,m)$ combinations as defined by the method.

A triple $\displaystyle (a,b,c)$ generated this way is said to be primitive if there is no integral factor greater than one shared by the three numbers.

In the next installment, we shall prove that in order to produce a primitive triple, m and n must have opposing parity and be co-prime themselves.

When $\displaystyle m$ and $\displaystyle n$ have the same parity, their difference will be even, and when their parity is different, their difference will be odd:

$\displaystyle m$ and $\displaystyle n$ both even:

$\displaystyle 2p-2q=2(p-q)$

$\displaystyle m$ and $\displaystyle n$ both odd:

$\displaystyle (2p+1)-(2q+1)=2(p-q)$

So, we see that both the differences of two even numbers and two odd numbers is even. Thus, when $\displaystyle m$ and $\displaystyle n$ have the same parity, we may state:

$\displaystyle m-n=2p\,\therefore\,m=n+2p$

and so Euclid's method generates:

$\displaystyle a=(n+2p)^2-n^2=4p(n+p)$

$\displaystyle b=2n(n+2p)$

$\displaystyle c=(n+2p)^2+n^2=2(n^2+np+2p^2)$

We see then that $\displaystyle a,\,b,\,c$ will all be even when $\displaystyle m$ and $\displaystyle n$ share the same parity. Now, what about when their parities are different? Then their difference will be odd, and we may write:

$\displaystyle m-n=2p+1\,\therefore\,m=n+2p+1$

and so Euclid's method generates:

$\displaystyle a=(n+2p+1)^2-n^2=(2n+2p+1)(2p+1)$

$\displaystyle b=2n(n+2p+1)$

$\displaystyle c=(n+2p+1)^2+n^2$

As we can see, as long as $\displaystyle m$ and $\displaystyle n$ are co-prime, this method will generate a primitive triple, since $\displaystyle c$ is prime. What if $\displaystyle m$ and $\displaystyle n$ do have a common factor?

Let us assume that $\displaystyle m$ and $\displaystyle n$ are not co-prime and recalling that $\displaystyle n<m$ means that the ration of $\displaystyle m$ to $\displaystyle n$ is reducible to a rational number greater than unity which we'll call $\displaystyle r$. There results:

$\displaystyle m=rn$ where $\displaystyle 1<r$

$\displaystyle a=(rn)^2-n^2=n^2(r^2-1)$

$\displaystyle b=2(rn)(n)=2n^2r$

$\displaystyle c=(rn)^2+n^2=n^2(r^2+1)$

Here, we see that there is a common factor of $\displaystyle n^2$ reducing to the triple:

$\displaystyle (r^2-1,2r,r^2+1)$

This simple method will generate only primitives if natural numbers are used for $\displaystyle r$, but will miss some since they are reduced from only some of the non-primitive triples, the ones resulting from $\displaystyle m$ and $\displaystyle n$ not being co-prime. Left out are the non-primitives generated from when $\displaystyle m$ and $\displaystyle n$ have the same parity, but are co-prime.

In conclusion, we can see that the only way to generate a primitive triple is for $\displaystyle m$ and $\displaystyle n$ to be co-prime and to have opposing parity. All such pairs will generate all possible primitive triples. The proof that Euclid's method is the most general Diophantine solution to the theorem of Pythagoras can be found in An Introduction to the Theory Of Numbers by G.H Hardy and E.M. Wright, Chapter 13 "Some Diophantine Equations," section 13.2, theorem 225 pp. 190-191. It was Diophantus of Alexandria (ca. 250 A.D.) who first proved the substance of theorem 225.

Approximating Right-Angled Isosceles Triangles

Continuing with our goal of finding approximate right-angled isosceles triangles with integral side lengths, here is the aforementioned contradiction of the terms of Euclid's method for a triple of the form where $\displaystyle a=b$:

$\displaystyle m^2-n^2=2mn\,\therefore\,(m-n)^2=(\sqrt{2}n)^2$

Find the root of both sides. Using only the positive root ($\displaystyle n<m$) and solving for $\displaystyle m$, we have:

$\displaystyle m=n(1+\sqrt{2})$

Thus, $\displaystyle m$ is forced to be irrational when it is defined to be natural, contradicting the terms of the method. This does, however, tell us that in our approximations we should expect to find:

$\displaystyle \frac{m}{n}\approx1+\sqrt{2}$

This equation, where $\displaystyle a=b$, by dividing through by $\displaystyle n^2$, will transform to:

$\displaystyle \left(\frac{m}{n} \right)^2-2\left(\frac{m}{n} \right)=1$

Dividing through by $\displaystyle \frac{m}{n}$ yields:

$\displaystyle \frac{m}{n}-2=\frac{n}{m}$

$\displaystyle \frac{m}{n}=\frac{n}{m}+2=\frac{2m+n}{m}$

Two numbers are said to be in the silver ratio $\displaystyle \delta_S=1+\sqrt{2}$ if:

"the ratio between the sum of the smaller plus twice the larger of those quantities and the larger one is the same as the ratio between the larger one and the smaller."

This relationship will prove very productive later and will show up repeatedly in different forms. Recall the roots are:

$\displaystyle \frac{m}{n}=1\pm\sqrt{2}$

However, for now, we will simply restrict the legs to having a difference of 1, the smallest non-zero difference they can have as natural numbers. Note that when the legs differ by one, we must have a primitive triple since any reduction in dimensions would absurdly place the legs $\displaystyle \frac{1}{r}$ units apart in length (where $\displaystyle r$ is the supposed common factor), which means $\displaystyle m$ and $\displaystyle n$ must be co-prime according to our analysis of Euclid's method.

In the next installment, we will look at what happens when $\displaystyle a$ and $\displaystyle b$ differ by 1.

Let us now define the desired relationship between the legs a and b and thus m and n:

$\displaystyle |a-b|=1\,\therefore\,a-b=\pm1$

To solve for m we'll use $\displaystyle a-b=\pm1$ and to solve for n, we'll use $\displaystyle b-a=\mp1$.

We change the "sign" of the plus/minus sign to of course make the statements equivalent, which keeps m and n in sync (describing the same triangle), but to also emphasize that the solutions for m and n will have opposite signs in their radicals.

Now let's find m and n using these equations. For m we'll begin with:

$\displaystyle (m^2-n^2)-(2mn)=\pm1$

Add $\displaystyle 2n^2$ to both sides:

$\displaystyle m^2-2mn+n^2=2n^2\pm1$

Factor the left side:

$\displaystyle(m-n)^2=2n^2\pm1$

And for n we need:

$\displaystyle (2mn)-(m^2-n^2)=\mp1$

Add $\displaystyle 2m^2$ to both sides:

$\displaystyle n^2+2mn+m^2=2m^2\mp1$

Factor the left side:

$\displaystyle (n+m)^2=2m^2\mp1$

Since $\displaystyle 0<n<m$, we must naturally discard both negative roots, and so solving for the desired variables, we find:

(1) $\displaystyle m=n+\sqrt{2n^2\pm1}$

(2) $\displaystyle n=-m+\sqrt{2m^2\mp1}$

Thus, we can see that m and n will always be a pair of numbers such that when one represents a natural number in the form $\displaystyle \sqrt{2p^2+1}$, the other will be a natural number in the form $\displaystyle \sqrt{2q^2-1}$. So, once we find just one such pair of numbers that satisfy this relationship, we can then use m and our next n, and be assured of finding our next m from (1) and so on, unbounded. Every other pairing will be where $\displaystyle a-b=1$ and likewise every other pairing will be where $\displaystyle b-a=1$. And, as we progress up this infinite ladder of numbers, the ration of m to n will converge to the so-called silver ratio.

We may now write (1) and (2) respectively:

$\displaystyle m=n_{\text{next}}=n+\sqrt{2n^2\pm1}$

$\displaystyle n=m_{\text{prev.}}=-m+\sqrt{2m^2\mp1}$

Now, if we take one step back down the ladder, m's were our current n's, and the sign under the radical would have reversed parity, allowing us to write from the second expression:

$\displaystyle n_{\text{prev.}}=-n+\sqrt{2n^2\pm1}\,\therefore\,\sqrt{2n^2\pm1}=n+n_{\text{prev.}}$

Finally, substituting this into our first expression above, we find:

(3) $\displaystyle m=n_{\text{next}}=n+(n+n_{\text{prev.}})$

What we have found is explicit instructions for recursively finding a sequence of numbers that will generate Pythagorean triples that successively more accurately approximate right-isosceles triangles as we "climb the ladder," and as an added bonus, we no longer have that pesky radical with its oscillating plus or minus one to evaluate.

Observe the striking similarity between this recursion formula and the equation we obtained from analyzing $\displaystyle a=b$:

(4) $\displaystyle \left(\frac{m}{n} \right)^2=2\left(\frac{m}{n} \right)+\left(\frac{m}{n} \right)^0$

The Pell Sequence

Since this is the Pell sequence we have found, we could express the recursion formula as:

$\displaystyle P_{n+1}=2P_{n}+P_{n-1}$

Also, we can take (4), use $\displaystyle r=\frac{m}{n}$ to represent any algebraic number since the solutions are irrationa;and after multiplying through by $\displaystyle r^{n-1}$ write it as:

(5) $\displaystyle r^{n+1}=2r^n+r^{n-1}$ where $\displaystyle r=1\pm\sqrt{2}$

More on this later, but keep it in mind and don't be too surprised to see n in the exponent when we find P as a function of n. Now we just need to find our starting or seed values. Note that zero and 1 will both work for n, so we will use those as our seeds:

$\displaystyle P_0=0,\,P_1=1$

Now that the process is seeded, we may proceed unbounded to the next values:

0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, ...

This sequence's recursive definition is quite similar to the famous Fibonacci sequence, given by $\displaystyle F_{n+1}=F_{n}+F_{n-1}$, but it was mistakenly attributed to English mathematician John Pell in 1780 by the prolific Swiss mathematician Leonhard Euler. This sequence of numbers, the Pell sequence, has actually been known since ancient times, but many results have been unknowingly and incorrectly names and so from habit the names stick, espcially when a giant like Euler does the naming.

Actually, it was Pierre de Fermat who first extensively studied such sequences in Europe. Historically, this sequence most notably arose just as it did here, in the quest to find right triangles having integral side lengths and whose legs differ by only one unit.

Next week, we will begin to look at some of the numerous and interesting properties of the Pell sequence.

Notice the alternating parity in the Pell sequence, defined as:

$P_{n+1}=2P_{n}+P_{n-1}$ where $P_{0}=0,\,P_{1}=1$

The two seed values have opposite parity, and so for the entire sequence, any two adjacent terms will also have opposite parity. We may demonstrate this as follows:

We may arrange the recursive definition as:

$2P_{n}=P_{n+1}-P_{n-1}$

This tells us every other term must have the same parity, since their difference is even. So, this means either all of the terms have the same parity, or they have alternating parity. Since the seed values have opposing parity, then we may conclude the entire sequence has to have alternating parity. Recall this is one of the requirements for a primitive Pythagorean triple.

Later, we will develop a short program for the TI-89 to do the grunt work of generating the Pell sequence (and to reduce human error), to find the dimensions of the resulting triangles, and some resulting rational approximations for the square root of two and display these values. We will define these approximations by taking $c$ and dividing by the average of $a$ and $b$. Simpler approximations will divide $c$ by $a$ and also by $b$. The definitions of these approximations are as follows:

$\displaystyle A_1=\frac{c}{\frac{a+b}{2}}=\frac{2c}{a+b}=\frac{2(m^2+n^2)}{m^2-n^2+2mn}$

$\displaystyle A_2=\frac{c}{a}=\frac{m^2+n^2}{m^2-n^2}$

$\displaystyle A_3=\frac{c}{b}=\frac{m^2+n^2}{2mn}$

We have shown that when $a=b$ then $m=n(1+\sqrt{2})$. While this is impossible, we should expect:

$\displaystyle \lim_{n\to\infty}\left(\frac{m}{n} \right)=\sqrt{2}+1$

and

$\displaystyle \lim_{n\to\infty}\left(\frac{n}{m} \right)=\sqrt{2}-1$

which may be shown as follows:

$\displaystyle \lim_{n\to\infty}\left(\frac{n+\sqrt{2n^2\pm1}}{n} \right)=\lim_{n\to\infty}\left(\frac{1+\sqrt{2\pm \frac{1}{n^2}}}{1} \right)=\sqrt{2}+1$

Another way we can find this limit is with:

$\displaystyle \lim_{n\to\infty}\left(\frac{P_{n+1}}{P_{n}} \right)=\lim_{n\to\infty}\left(\frac{2P_{n}+P_{n-1}}{P_{n}} \right)=2+\frac{1}{L}$

This results in the quadratic in $L$:

$L^2-2L-1=0$

This, incidentally, is the characteristic equation for the recursion, just as we should expect.

Application of the quadratic formula (discarding the negative root, which will come into play later) we find:

$L=\sqrt{2}+1$

Now, let's verify the approximations we defined above will converge to $\sqrt{2}$.

$\displaystyle \lim_{n\to\infty}(A_1)=\lim_{n\to\infty}\left( \frac{2(m^2+n^2)}{m^2-n^2+2mn} \right)=2\lim_{n\to\infty}\left(\frac{\left(\frac{m}{n} \right)^2+1}{\left(\frac{m}{n} \right)^2-1+2\left(\frac{m}{n} \right)} \right)=$

$\displaystyle \frac{2\left((\sqrt{2}+1)^2+1 \right)}{(\sqrt{2}+1)^2-1+2(\sqrt{2}+1)}=\frac{4(\sqrt{2}+2)}{4(\sqrt{2}+1)}=\sqrt{2}$

$\displaystyle \lim_{n\to\infty}(A_2)=\lim_{n\to\infty}\left( \frac{m^2+n^2}{m^2-n^2} \right)=\lim_{n\to\infty}\left(\frac{\left(\frac{m}{n} \right)^2+1}{\left(\frac{m}{n} \right)^2-1} \right)=$

$\displaystyle \frac{(\sqrt{2}+1)^2+1}{(\sqrt{2}+1)^2-1}=\frac{2\sqrt{2}+4}{2\sqrt{2}+2}=\sqrt{2}$

$\displaystyle \lim_{n\to\infty}(A_3)=\lim_{n\to\infty}\left( \frac{m^2+n^2}{2mn} \right)=\lim_{n\to\infty}\left(\frac{\left(\frac{m}{n} \right)^2+1}{2\left(\frac{m}{n} \right)} \right)=$

$\displaystyle \frac{(\sqrt{2}+1)^2+1}{2(\sqrt{2}+1)}=\frac{2 \sqrt{2}+4}{2\sqrt{2}+2}=\sqrt{2}$

Recall that we found the limiting ratio of two consecutive satisfies:

$\displaystyle L=2+\frac{1}{L}$

and observe that the two roots of this quadratic in disguise satisfy:

$\displaystyle L_1L_2=-1$

Vieta's formulas tell us this will be true for any quadratic of the form:

$\displaystyle x^2+kx-1=0$

whose roots are:

$\displaystyle \frac{-k\pm\sqrt{k^2+4}}{2}$

So, this is the family of surds whose negative conjugate is its own multiplicative inverse. But I digress.

Thus, we have found that the ratio of any two successive members of the Pell sequence will approach the "silver ratio" $\delta_S=1+\sqrt{2}$ as we continue to generate them with $n$ growing without bound. For comparison, this limiting ratio for the Fibonacci sequence is the so-called "golden ratio" $\displaystyle \varphi=\frac{1+\sqrt{5}}{2}$. Later we will find the limiting ratio for a much more generalized defined recursive sequence.

Next week, we will look at an interesting problem posed by the brilliant English mathematician who discovered and mentored the incredible Indian phenom Ramanujan, dubbed "The Man Who Loved Infinity."

Improvements to The Approximations

In G.H. Hardy's A Course of Pure Mathematics, he poses in chapter 1 titled "Real Variables," Section 5, page 11, problem 3:

Quote:
Show that if $\displaystyle \frac{m}{n}$ is a good approximation to $\sqrt{2}$, then $\displaystyle \frac{m+2n}{m+n}$ is a better one, and that the errors in the two cases are in opposite directions.
Before we employ the Pell numbers to solve this problem, let's proceed in a more general manner, more along the lines of what Hardy probably had in mind. Let's let $\epsilon_1$ represent the error for the first case, and $\epsilon_2$ represent the error for the second. We may then state:

$\displaystyle \frac{m}{n}=\sqrt{2}+\epsilon_1$

and

$\displaystyle \frac{m+2n}{m+n}=\sqrt{2}+\epsilon_2$

Now, we may state $\epsilon_2$ in terms of $\epsilon_1$ by using:

$\displaystyle \frac{m+2n}{m+n}=\frac{\frac{m}{n}+2}{\frac{m}{n}+1}$

Substitute for the values given above:

$\displaystyle \sqrt{2}+\epsilon_2=\frac{\sqrt{2}+\epsilon_1+2}{ \sqrt{2}+\epsilon_1+1}$

Solve for $\epsilon_2$:

$\displaystyle \epsilon_2=\frac{\sqrt{2}+\epsilon_1+2}{\sqrt{2}+ \epsilon_1+1}-\sqrt{2}=\frac{\sqrt{2}+\epsilon_1+2-\sqrt{2}(\sqrt{2}+\epsilon_1+1)}{\sqrt{2}+\epsilon_1+1}=$

$\displaystyle=\frac{\sqrt{2}+\epsilon_1+2-2-\sqrt{2}\epsilon_1-\sqrt{2}}{\sqrt{2}+\epsilon_1+1}=-\frac{\epsilon_2(\sqrt{2}-1)}{\frac{m}{n}+1}$

Now, we are told that $\displaystyle \frac{m}{n}$ is a "good approximation" thus we may assume $\displaystyle 0<\frac{m}{n}$. So, we have shown that the magnitude of the error decreases, i.e. $|\epsilon_2|<|\epsilon_1|$ and that the two errors are in opposite directions. The only restrictions are those which came with the problem, namely $n\ne0$ and $\displaystyle \frac{m}{n}\ne-1$.

Let's try to find a method that makes no assumptions about how good the approximation is. The only assumption here is that the first approximation is not -1, which is intrinsic to the problem, so we are not introducing this condition. If $\displaystyle \frac{m}{n}$ approximates $\sqrt{2}$, then we may define its error by writing:

$\displaystyle \left(\frac{m}{n} \right)^2-\epsilon_1=2\,\therefore\,\left(\frac{m}{n} \right)^2=\epsilon_1+2\,\therefore\,m^2-2n^2=epsilon_1n^2$

Now, assuming $\displaystyle \frac{m+2n}{m+n}$ also approximates $\sqrt{2}$ from what Hardy states in the problem, we may define its error in like manner:

$\displaystyle \left(\frac{m+2n}{m+n} \right)^2-\epsilon_2=2\,\therefore\,\left(\frac{m+2n}{m+n} \right)^2=2+\epsilon_2$

Now, observe that:

$\displaystyle \left(\frac{m+2n}{m+n} \right)^2=\frac{2(m+n)^2-2(m+n)^2+(m+2n)^2}{(m+n)^2}=2-\frac{2(m+n)^2-(m+2n)^2}{(m+n)^2}$

Expanding binomials, we find:

$\displaystyle \left(\frac{m+2n}{m+n} \right)^2=2-\frac{2(m^2+2mn+n^2)-(m^2+4mn+4n^2)}{(m+n)^2}=2-\frac{2m^2+4mn+2n^2-m^2-4mn-4n^2}{(m+n)^2}$

Collect like terms, then use $m^2-2n^2=\epsilon_1n^2$:

$\displaystyle \left(\frac{m+2n}{m+n} \right)^2=2-\frac{m^2-2n^2}{(m+n)^2}=2-\epsilon_1\left(\frac{n}{m+n} \right)^2$

Now use $\displaystyle \left(\frac{m+2n}{m+n} \right)^2=2+\epsilon_2$:

$\displaystyle 2+\epsilon_2=2-\epsilon_1\left(\frac{n}{m+n} \right)^2$

$\displaystyle \epsilon_2=-\epsilon_1\left(\frac{n}{m+n} \right)^2$

Since a square is always positive and $\displaystyle \frac{m}{n}\ne-1$, we have shown both that the magnitude of the error decreases and the two errors are in the opposite direction as desired.

Next week, we will approach this problem using the Pell sequence.

As we previously found, we can approximate the square root of two with:

$\displaystyle \frac{P_{n+1}}{P_n}-1=\frac{P_{n+1}-P_n}{P_n}$

Let $\displaystyle m=P_{n+1}-P_n$ and $\displaystyle n=P_n$.

Naturally, a better approximation will be given by:

$\displaystyle \frac{P_{n+2}-P_{n+1}}{P_{n+1}}$

Using the recursive definition of the Pell sequence, we may rewrite the improved approximation as:

$\displaystyle \frac{(2P_{n+1}+P_{n})-P_{n+1}}{P_{n+1}}=\frac{P_{n+1}+P_{n}}{P_{n+1}}$

Now, we may write this approximation so that we may express it in terms of $m$ and $n$.

$\displaystyle \frac{(P_{n+1}-P_{n})+2P_{n}}{(P_{n+1}-P_{n})+P_{n}}=\frac{m+2n}{m+n}$

According to Hardy, and as we have shown, the error in the first improvement will be in the opposite direction as the original, and as a consequence, in the second improvement, the error will be in the same direction as the original. Let's examine these improvements in more detail and see if a pattern emerges.

We know the first improvement to our approximation is:

$\displaystyle \frac{m+2n}{m+n}$

Let's now use this formula to generate the second improvement:

$\displaystyle \frac{(m+2n)+2(m+n)}{(m+2n)+(m+n)}=\frac{3m+4n}{2m+3n}$

Again, we continue and find the third improvement:

$\displaystyle \frac{(3m+4n)+2(2m+3n)}{(3m+4n)+(2m+3n)}=\frac{7m+10n}{5m+7n}$

Next, the fourth improvement:

$\displaystyle \frac{(7m+10n)+2(5m+7n)}{(7m+10n)+(5m+7n)}=\frac{17m+24n}{12m+17n}$

We will now assert that the $k$th improvement will be given by:

$\displaystyle \frac{(P_{k}+P_{k-1})m+2P_{k}n}{P_{k}m+(P_{k}+P_{k-1})n}$

We can prove this by induction on $k$ by using Hardy's formula to find the ($k$+1)th improvement:

$\displaystyle \frac{((P_{k}+P_{k-1})m+2P_{k}n)+2(P_{k}m+(P_{k}+P_{k-1})n)}{((P_{k}+P_{k-1})m+2P_{k}n)+(P_{k}m+(P_{k}+P_{k-1})n)}=\frac{(3P_{k}+P_{k-1})m+(4P_{k}+2P_{k-1})n}{(2P_{k}+P_{k-1})m+(3P_{k}+P_{k-1})n}$

We may rewrite this expression, then employ the recursion definition of the Pell sequence:

$\displaystyle \frac{(P_{k}+(2P_{k}+P_{k-1}))m+2(2P_{k}+P_{k-1})n}{(2P_{k}+P_{k-1})m+(P_{k}+(2P_{k}+P_{k-1}))n}=\frac{(P_{k+1}+P_{k})m+2P_{k+1}n}{P_{k+1}m+(P_{k+1}+P_{k})n}$

This completes our proof by induction. Therefore, we should expect the following to be true, where $\displaystyle r=\frac{m}{n}$:

$\displaystyle \frac{(P_{k}+P_{k-1})r+2P_{k}}{P_{k}r+(P_{k}+P_{k-1})}\approx\sqrt{2}$

where:

$\displaystyle P_{k}r+(P_{k}+P_{k-1})\ne0$

which implies:

$\displaystyle r\ne-\frac{P_{n}+P_{n-1}}{P_n}\approx-\sqrt{2}$

Hence, our rational approximation can never converge on $-\sqrt{2}$. Now we need to show that the errors between subsequent improvements will oscillate about the convergent value, or be in opposite directions. We will save this part of the problem until we have first looked at Pell's equation next week.

Pell's Equation

In mathematics, a Diophantine equation is an indeterminate (i.e. having an infinite number of solutions) polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations. In more technical language, they define an algebraic curve, algebraic surface or more general object, and ask about the lattice points on it. Most texts on number theory contain sections devoted to Diophantine equations. Perhaps the most famous such equation is Fermat's Last Theorem, which states that the equation

$x^n+y^n=z^n$ where $2<n\in\mathbb{Z}$

has no solutions, except the trivial solutions in which one of the variables $x,\,y,\,z$ is zero. Although Fermat claimed to have found a proof of this theorem, it was not actually proven until 1994 by the British mathematician Andrew Wiles.

In 1637, Pierre de Fermat wrote a marginal note in his copy of Bachet's edition of the works of Diophantus where he first enunciated the theorem and asserted that he possessed a "most elegant" proof, but had no room in the margin for it. However, the later history of the subject seems to show that he must have been mistaken, although many fallacious proofs were given in the 357 years that were to follow until it was actually solved. The brilliant 200 page proof given by Wiles requires the extensive use of twentieth century number theory.

The word Diophantine refers to the Hellenistic mathematician of the 3rd century, Diophantus of Alexandria, who made a study of such equations and was one of the first mathematicians to introduce symbolism into algebra. The mathematical study of Diophantine problems Diophantus initiated is now called "Diophantine Analysis." I linear Diophantine equation is an equation between two sums of monomials of degree zero or one.

While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations (beyond the theory of quadratic forms) was an achievement of the twentieth century.

Let's now look at a Diophantine equation of particular interest to us:

$x^2-ny^2=\pm1$

where $n$ is any non-square positive integer. In our case, we will let $n=2$. Because the solutions to this equation yield good rational approximations of the form $\displaystyle \frac{x}{y}$ to the square root of $n$, we will assert from the $k$th improvement we found earlier, that the solutions for this equation, called Pell's equation, can be given by:

$\left((P_{n}+P_{n-1})+2P_{n} \right)^2-2\left(P_{n}+(P_{n+P_{n-1}}) \right)^2=\pm1$

Collect like terms on the left within the parentheses:

$\left(3P_{n}+P_{n-1} \right)^2-2\left(2P_{n}+P_{n-1}) \right)^2=\pm1$

Expand squared binomials:

$\left(9P_{n}^2+6P_{n}P_{n-1}+P_{n-1}^2 \right)-2\left(4P_{n}^2+4P_{n-1}P_{n}+P_{n-1}^2 \right)^2=\pm1$

Collect like terms again on the left:

$P_{n}^2-2P_{n-1}P_{n}-P_{n-1}^2=\pm1$

We have already seen that this is the relationship that arises from setting the natural length legs of a right triangle one unit apart, so we have shown this to be true. We should also be able to solve Pell's equation with the $0$th improvement:

$(P_{n+1}-P_{n})^2-2(P_{n})^2=\pm1$

Expand squared binomials:

$P_{n+1}^2-2P_{n}P_{n+1}+P_{n}^2-2P_{n}^2=\pm1$

Collect like terms:

$P_{n+1}^2-2P_{n}P_{n+1}-P_{n}^2=\pm1$

And again we have shown this to be true.

As was mentioned, the name of the Diophantine equation we are studying is Pell's equation, and this arose from Leonhard Euler's mistakenly attributing its study to John Pell. Euler was aware of the work of Lord Brouncker, the first European mathematician to find a general solution to the equation, but apparently confused Brouncker with Pell.

This equation was first studied extensively in ancient India, starting with Brahmagupta, who developed the chakravala method to solve Pell's equation, and other quadratic indeterminate equations in his Brahma Sphuta Siddhanta in 628 A.D., about a thousand years before Pell's time. His Brahma Sphuta Siddhanta was translated into Arabic in 773 and was subsequently translated into Latin in 1126. Bhaskara II in the 12th century and Narayana in the 14th century both found general solutions to Pell's equation and other quadratic indeterminate equations.

Solutions to specific examples of the Pell equation, such as the Pell numbers arising from the equation with $n=2$, had been known for much longer, since the time of Pythagoras in Greece and to a similar date in India.

Trivially, $x=1$ and $y=0$ always solve this equation. Lagrange proved that for any natural number $n$ that is not a perfect square, there are positive $x$ and $y$ that satisfy Pell's equation. Moreover, infinitely many such solutions exist. These solutions, as stated above, yield good rational approximations of the form $\dfrac{x}{y}$ to $\sqrt{n}$. Many solutions to other Diophantine equations were given by Euler as well.

This is how we solved Pell's equation for $n=2$, by using known approximations for $\sqrt{2}$. In fact, when we used Euclid's method for generating Pythagorean triples and set $a$ and $b$ one unit apart, we unwittingly arrived at Pell's equation for $n=2$, and subsequently solved it with the Pell sequence.

In fact, as we shall see, we can generate infinitely many solution forms using the Pell sequence and a related sequence defined recursively the same, but with different seed values or initial data. The two sequences are listed for convenience:

1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, ...

0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, ...

Now, using corresponding terms from the two sequences, the first several solutions are given:

$(1P_{n}+1P_{n-1})^2-2(1P_{n}+0P_{n-1})^2=\pm1$

$(3P_{n}+1P_{n-1})^2-2(2P_{n}+1P_{n-1})^2=\pm1$

$(7P_{n}+3P_{n-1})^2-2(5P_{n}+2P_{n-1})^2=\pm1$

$(17P_{n}+7P_{n-1})^2-2(12P_{n}+5P_{n-1})^2=\pm1$

$(41P_{n}+17P_{n-1})^2-2(29P_{n}+12P_{n-1})^2=\pm1$

We could continue unbounded using the two sequences to generate solutions to Pell's equation. Later we will prove this in more general terms, after we have defined the first sequence (and all other Pell-like sequences) in terms of the Pell sequence itself. We will also show that all of these solutions are equivalent for differing indices of $P$.

Next week we will return to the problem posed by Hardy and look again at the "oscillating error."

The Oscillating Error

Now we are ready to finish the problem posed by Hardy and demonstrate the oscillating behavior of subsequent rational approximations, or in other words, that is one approximations is in defect, the next will be in excess, and vice-versa. Recall that in setting the legs of our approximate right-angled isosceles triangle one unit difference in length, we found:

$P_{n+1}^2-2P_{n}P_{n+1}-P_{n}^2=(-1)^n$

This of course may be rewritten as:

$(P_{n+1}-P_{n})^2-2(P_{n})^2=(-1)^n$

Now, if we let $x=P_{n+1}-P_{n}$ and $y=P_{n}$, we find that $\displaystyle \frac{x}{y}$ does indeed form a good rational approximation to $\sqrt{2}$ as required. Thus, we have:

$\dfrac{x}{y}\approx\sqrt{2}$, where we may define the error $\epsilon$ with $\epsilon=\dfrac{x}{y}-\sqrt{2}$.

Substituting for $x$ and $y$, we have Pell's equation for $n=2$:

$x^2-2y^2=(-1)^n$

Factoring the left side as the difference of squares, we may write:

$(x+\sqrt{2}y)(x-\sqrt{2}y)=(-1)^n$

Now, dividing through by $y(x+\sqrt{2}y)$ with no worries of division by zero yields:

$\displaystyle \frac{x}{y}-\sqrt{2}=\frac{(-1)^n}{y(x+\sqrt{2}y)}$

Recall the left side is the error $\epsilon$. There results:

$\displaystyle \epsilon=\frac{(-1)^n}{y(x+\sqrt{2}y)}$

Thus, as desired, we have shown that the magnitude of the error will decrease as $n$ increases and the sign of the error will oscillate for all sequential values of $n$. This particular value for the error $\epsilon$ is valid only for rational approximations as defined for $x$ and $y$ above, i.e., $x$ and $y$ must obviously satisfy Pell's equation. However, if we were to modify Pell's equation as follows:

$x^2-2y^2=\pm p$ where $p\in\mathbb{N}$

We could thusly incorporate all rational approximations to $\sqrt{2}$, and demonstrate the identical oscillating behavior of the resulting error, and as a result we can plainly see that when $p=1$, we get the best approximations for a given $y$ since 1 is the smallest natural number, minimizing the error for integral solutions of this Diophantine equation. This is equivalent to minimizing the error in our earlier approximations by setting the legs of our triangles one unit apart in length, resulting in the closest approximation to a right angled isosceles triangle with integral side lengths for a given hypotenuse.

We will return later to this modification of Pell's equation and the sequences that satisfy it. For more information on Pell's equation, see Hardy and Wright's An Introduction to the Theory of Numbers, Chapter 14 "Quadratic Fields," section 14.5, theorem 244, pp. 210.

Next week we will investigate expressing the approximation as a continued fraction.

Expressing the Approximation as a Continued Fraction

Recall, we may approximate $\sqrt{2}$ with:

$\displaystyle \frac{P_{n+1}}{P_{n}}-1=\frac{P_{n+1}-P_{n}}{P_{n}}=\frac{(2P_{n}+P_{n-1}-P_{n}}{P_{n}}=1+\frac{P_{n-1}}{P_{n}}=$

$\displaystyle 1+\frac{1}{\frac{P_{n}}{P_{n-1}}}=1+\frac{1}{\frac{2P_{n-1}+P_{n-2}}{P_{n-1}}}=1+\frac{1}{2+\frac{P_{n-2}}{P_{n-1}}}=1+\frac{1}{2+\frac{1}{\frac{P_{n-1}}{P_{n-2}}}}$

If $n$ is finite, then the continued fraction will terminate when we have a denominator that reaches:

$\displaystyle 2+\frac{P_0}{P_1}=2+\frac{0}{1}=2$

For instance, suppose we begin with $\displaystyle 1+\frac{P_2}{P_3}$. The continued fraction will terminate after $n=3$ iterations as follows:

$\displaystyle 1+\frac{P_2}{P_3}=1+\frac{1}{2+\frac{P_1}{P_2}}=1+\frac{1}{2+\frac{1}{2+\frac{P_0}{P_1}}}=1+\frac{1}{2+\frac{1}{2}}$

We can then see that as $n$ approaches infinity, then we must have:

$\displaystyle \sqrt{2}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+ \frac{1}{2+\cdots}}}}$

Given that:

$\displaystyle \frac{P_{n+1}}{P_{n}}=\frac{2P_{n}+P_{n-1}}{P_{n}}=2+\frac{P_{n-1}}{P_{n}}=2+\frac{1}{\frac{P_{n}}{P_{n-1}}}$

Notice we have another expression in the denominator of the same type with which we began, only the subscripts are 1 less. So, if the original subscripts are unbounded, we will have an infinitely continued fraction of the type:

$\displaystyle 2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ \frac{1}{2+\cdots}}}}=1+\sqrt{2}=\lim_{n\to\infty}\frac{P_{n+1}}{P_{n}}$

By subtracting through by 1, we may write:

$\displaystyle 1+\frac{1}{2+\frac{1}{2+\frac{1}{2+ \frac{1}{2+\cdots}}}}=\sqrt{2}=\left(\lim_{n\to\infty}\frac{P_{n+1}}{P_{n}} \right)-1$

We may also look at it this way:

$\displaystyle x=2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ \frac{1}{2+\cdots}}}}=2+\frac{1}{x}$ where $\displaystyle 0<x$

Multiplying through by $x$, and arrange in standard quadratic form, we obtain:

$\displaystyle x^2-2x-1=0$

We have seen this quadratic enough time to know its positive solution is:

$\displaystyle x=1+\sqrt{2}$

The negative solution was extraneously added when we multiplied through by $x$. Interestingly, this is additional proof of the irrationality of $\sqrt{2}$. If the continued fraction terminated, no matter after how many finite iterations, it would obviously be rational. However, the continued fractional representation must contain an infinitude of iterations, as given by the limit where the subscripts are unbounded, showing $\sqrt{2}$ to be irrational.

Next week, we will begin to develop some identities involving the Pell numbers.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•