MHB Concepts of the Pell Sequence

[MarkFL]

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:

http://mathhelpboards.com/commentary-threads-53/commentary-pell-sequence-4205.html

 

[MarkFL]

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.

 

[MarkFL]

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.

 

[MarkFL]

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.

 

[MarkFL]

Moderator edit: This commentary topic pertains to the following tutorial:

http://mathhelpboards.com/math-notes-49/pell-sequence-2905.html

I just want to take a moment to publicly thank anemone for taking the time to proofread my posts to help me eliminate many typos!

 

[MarkFL]

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."

 

[MarkFL]

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:

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.

 

[MarkFL]

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.

 

[MarkFL]

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."

 

[MarkFL]

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.

 

[MarkFL]

Expressing the Approximation as a Continued Fraction

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

$$\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}}=$$

$$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:

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

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

$$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:

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

Given that:

$$\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:

$$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:

$$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:

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

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

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

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

$$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.

 

[MarkFL]

Before we begin to develop identities involving the Pell numbers, I want to present some data that we will use as reference. These are the first 24 generators, and the resulting Pythagorean triples. $n$ and $m$ are Pell numbers used in Euclid's method, and $a,b,c$ is the triple that results:

[TABLE="class: grid, width: 700, align: center"]
[TR]
[TD]index[/TD]
[TD]n[/TD]
[TD]m[/TD]
[TD]a[/TD]
[TD]b[/TD]
[TD]c[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]1[/TD]
[TD]2[/TD]
[TD]3[/TD]
[TD]4[/TD]
[TD]5[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]2[/TD]
[TD]5[/TD]
[TD]21[/TD]
[TD]20[/TD]
[TD]29[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]5[/TD]
[TD]12[/TD]
[TD]119[/TD]
[TD]120[/TD]
[TD]169[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]12[/TD]
[TD]29[/TD]
[TD]697[/TD]
[TD]696[/TD]
[TD]985[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]29[/TD]
[TD]70[/TD]
[TD]4059[/TD]
[TD]4060[/TD]
[TD]5741[/TD]
[/TR]
[TR]
[TD]6[/TD]
[TD]70[/TD]
[TD]169[/TD]
[TD]23661[/TD]
[TD]23660[/TD]
[TD]33461[/TD]
[/TR]
[TR]
[TD]7[/TD]
[TD]169[/TD]
[TD]408[/TD]
[TD]137903[/TD]
[TD]133904[/TD]
[TD]195025[/TD]
[/TR]
[TR]
[TD]8[/TD]
[TD]408[/TD]
[TD]985[/TD]
[TD]803761[/TD]
[TD]803760[/TD]
[TD]1136689[/TD]
[/TR]
[TR]
[TD]9[/TD]
[TD]985[/TD]
[TD]2378[/TD]
[TD]4684659[/TD]
[TD]4684660[/TD]
[TD]6625109[/TD]
[/TR]
[TR]
[TD]10[/TD]
[TD]2378[/TD]
[TD]5741[/TD]
[TD]27304197[/TD]
[TD]27304196[/TD]
[TD]38613965[/TD]
[/TR]
[TR]
[TD]11[/TD]
[TD]5741[/TD]
[TD]13860[/TD]
[TD]159140519[/TD]
[TD]159140520[/TD]
[TD]225058681[/TD]
[/TR]
[TR]
[TD]12[/TD]
[TD]13860[/TD]
[TD]33461[/TD]
[TD]927538921[/TD]
[TD]927538920[/TD]
[TD]1311738121[/TD]
[/TR]
[TR]
[TD]13[/TD]
[TD]33461[/TD]
[TD]80782[/TD]
[TD]5406093003[/TD]
[TD]5406093004[/TD]
[TD]7645370045[/TD]
[/TR]
[TR]
[TD]14[/TD]
[TD]80782[/TD]
[TD]195025[/TD]
[TD]31509019101[/TD]
[TD]31509019100[/TD]
[TD]44560482149[/TD]
[/TR]
[TR]
[TD]15[/TD]
[TD]195025[/TD]
[TD]470832[/TD]
[TD]183648021599[/TD]
[TD]183648021600[/TD]
[TD]259717522849[/TD]
[/TR]
[TR]
[TD]16[/TD]
[TD]470832[/TD]
[TD]1136689[/TD]
[TD]1070379110497[/TD]
[TD]1070379110496[/TD]
[TD]1513744654945[/TD]
[/TR]
[TR]
[TD]17[/TD]
[TD]1136689[/TD]
[TD]2744210[/TD]
[TD]6238626641379[/TD]
[TD]6238626641380[/TD]
[TD]8822750406821[/TD]
[/TR]
[TR]
[TD]18[/TD]
[TD]2744210[/TD]
[TD]6625109[/TD]
[TD]36361380737781[/TD]
[TD]36361380737780[/TD]
[TD]51422757785981[/TD]
[/TR]
[TR]
[TD]19[/TD]
[TD]6625109[/TD]
[TD]15994428[/TD]
[TD]211929657785303[/TD]
[TD]211929657785304[/TD]
[TD]299713796309065[/TD]
[/TR]
[TR]
[TD]20[/TD]
[TD]15994428[/TD]
[TD]38613965[/TD]
[TD]1235216565974041[/TD]
[TD]1235216565974040[/TD]
[TD]1746860020068409[/TD]
[/TR]
[TR]
[TD]21[/TD]
[TD]38613965[/TD]
[TD]93222358[/TD]
[TD]7199369738058939[/TD]
[TD]7199369738058940[/TD]
[TD]10181446324101389[/TD]
[/TR]
[TR]
[TD]22[/TD]
[TD]93222358[/TD]
[TD]225058681[/TD]
[TD]41961001862379597[/TD]
[TD]41961001862379596[/TD]
[TD]59341817924539925[/TD]
[/TR]
[TR]
[TD]23[/TD]
[TD]225058681[/TD]
[TD]543339720[/TD]
[TD]244566641436218639[/TD]
[TD]244566641436218640[/TD]
[TD]345869461223138161[/TD]
[/TR]
[TR]
[TD]24[/TD]
[TD]543339720[/TD]
[TD]1311738121[/TD]
[TD]1425438846754932241[/TD]
[TD]1425438846754932240[/TD]
[TD]2015874949414289041[/TD]
[/TR]
[/TABLE]

Developing the Identities

Let's begin with a formula for the square of the $n$th Pell number. The recursive definition is:

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

Solve for $P_n$:

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

Multiply through by $P_n$:

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

Next, let's find a formula for the difference of the squares of two successive Pell Numbers. Using the above result, we may state:

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

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

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

Exploring the sequences that generate the triangle sides directly

Notice from the data above that $c$ appears to always be a Pell number. In fact, it appears the the $n$th $c$ is always the $(2n+1)$th Pell Number, for $n>0$. This can be expressed:

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

Before we prove this identity, let's first develop another useful identity.

$$P_{i+1}P_{j+1}+P_{i}P_{j}=P_{j+1}\left(2P_{i}+P_{i-1} \right)+P_{i}P_{j}=2P_{j+1}P_{i}+P_{j}P_{i}+P_{j+1}P_{i-1}=$$

$$P_{i}\left(2P_{j+1}+P_{j} \right)+P_{j+1}P_{i-1}=P_{i}P_{j+2}+P_{i-1}P_{j+1}$$

There results:

$$P_{i+1}P_{j+1}+P_{i}P_{j}=P_{i}P_{j+2}+P_{i-1}P_{j+1}=P_{j+1}\left(2P_{i-1}+P_{i-2} \right)++P_{i-1}P_{j+1}=$$

$$2P_{i-1}P_{j+2}+P_{i-2}P_{j+2}+P_{i-1}P_{j+1}=P_{i-1}\left(2P_{j+2}+P_{j+1} \right)+P_{i-2}P_{j+2}=$$

$$P_{i-1}P_{j+3}+P_{i-2}P_{j+2}$$

Here is what we have so far:

$$P_{i+1}P_{j+1}+P_{i}P_{j}=P_{i}P_{j+2}+P_{i-1}P_{j+1}=P_{i-1}P_{j+3}+P_{i-2}P_{j+2}$$

It would appear that one can take away from the $i$ indices, up to $i$, as long as the same value, we call this $n$, is added to the $j$ indices and vice-versa. We will prove this later, and for a more general case.

$$P_{i+1}P_{j+1}+P_{i}P_{j}=P_{i+1-n}P_{j+1+n}+P_{i-n}P_{j+n}$$

Let $i=j=n$:

$$P_{n+1}^2+P_{n}^2=P_1P_{2n+1}+P_0P_{2n-1}$$

Recall $P_0=1,\,P_1=1$:

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

Thus we have shown the identity to be true. Next week, we will examine $c_n$ as a sequence itself.

 

[MarkFL]

We see that $c_n$ is the sequence:

$5, 29, 169, 985, 5741, ...$

How can we take 5 and 29 and get 169? We find that $6\cdot29-5=169$.

Could be that:

$c_{n+1}=6c_{n}-c_{n-1}$ ?

Let's rewrite this in terms of Pell numbers where $c_{n}=P_{2n+1}^2+P_{n}^2=P_{2n+1}$.

First, using the sum of the squares $c_{n}=P_{2n+1}^2+P_{n}^2$:

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

Simplify subscripts:

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

Distribute:

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

Collect like terms:

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

Use the recursive definition $P_{n+2}=2P_{n+1}+P_{n}$:

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

Expand the squared binomial on the left:

$$4P_{n+1}^2+4P_{n}P_{n+1}+P_{n}^2=5P_{n+1}^2+5P_{n}^2-P_{n-1}^2$$

Collect like terms:

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

Now use $$P_{n+1}=2P_{n}+P_{n-1}$$ and expand and distribute:

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

$$8P_{n}^2+4P_{n}P_{n-1}=4P_{n}^2+4P_{n-1}P_{n}+P_{n-1}^2+4P_{n}^2-P_{n-1}^2$$

$$8P_{n}^2+4P_{n-1}P_{n}=8P_{n}^2+4P_{n-1}P_{n}$$

Hence, we have shown the recursion for $c_n$ to be valid. Now let's see if we can verify it by the second expression $c_{n}=P_{2n+1}$.

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

Simplify subscripts:

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

On the left, use the definition $P_{2n+3}=2P_{2n+2}+P_{2n+1}$:

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

Collect like terms:

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

On the left, use the definition $P_{2n+2}=2P_{2n+1}+P_{2n}$:

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

Distribute:

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

Collect like terms:

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

This is true by the recursive definition, hence we have proven the recursive sequence definition for $c_n$ again. This implies:

$$P_{n+3}=6P_{n+1}-P_{n-1}$$

Using this recursive definition and the seeds 5 and 29, we have:

5, 29, 169, 985, 5741, 33641, 195025, 1136689, ...

Could we use the seeds 1 and 1? Yes, we get the same sequence. We now know how this relates to the Pell sequence. Next week we will show that the ratio of two successive terms (the larger over the smaller) will converge to the square of the silver ratio.

 

[MarkFL]

Let's now verify that:

$$\lim_{n\to\infty}\frac{c_{n+1}}{c_{n}}=(1+\sqrt{2})^2=3+3\sqrt{2}$$

To begin, let's state:

$$\lim_{n\to\infty}\frac{c_{n+1}}{c_{n}}=L$$

Using the recursive definition, we may write:

$$\lim_{n\to\infty}\frac{c_{n+1}}{c_{n}}=\lim_{n\to\infty}\frac{6c_{n}-c_{n-1}}{c_{n}}=6-\frac{1}{L}$$

So, we have:

$$L=6-\frac{1}{L}$$

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

The larger root is indeed $$L=3+2\sqrt{2}=(1+\sqrt{2})^2$$

It converges to the same value the original sequence would if would had only considered $b-a=1$ or $a-b=1$, picking up only every other triangle.

From the data, it would appear that:

$$c_{n}=b_{n}+b_{n-1}+c_{n-1}$$

If we write this in terms of Pell numbers, we find:

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

Simplify, then collect all terms having $P_n$ as a factor to the right, then factor:

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

Divide out common factor:

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

This is just another way to write the recursive definition, hence we have show this is true. We may also observe that the following appears to be true:

$$c_n=a_n+a_{n-1}+c_{n-1}$$

Express in Pell numbers:

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

We find that we have:

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

So, this must be true as well. It also appears that we must have:

$$c_{n+1}=5c_{n}+b_{n}+b_{n-1}=5c_{n}+a_{n}+a_{n-1}$$

If this is true, then recall we found

$$c_{n+1}=6c_{n}-c_{n-1}$$

Combining the two, we could write:

$$6c_{n}-c_{n-1}=5c_{n}+b_{n}+b_{n-1}=5c_{n}+a_{n}+a_{n-1}$$

$$c_{n}-c_{n-1}=b_{n}+b_{n-1}=a_{n}+a_{n-1}$$

First, let's look at:

$$c_{n}-c_{n-1}=b_{n}+b_{n-1}$$

Express in Pell numbers:

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

Remove parentheses, collect like terms and factor:

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

We have seen before that this implies:

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

which is of course the recursive definition, hence it is true. Now let's look at:

$$c_{n}-c_{n-1}=a_{n}+a_{n-1}$$

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

Remove parentheses and collect like terms:

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

Shown as well. Thus, so for for $c$, we have:

(a) $$c_{n+1}=b_{n+1}+b_{n}+c_{n}$$

(b) $$c_{n+1}=a_{n+1}+a_{n}+c_{n}$$

(c) $$c_{n+1}=5c_{n}+b_{n}+b_{n-1}=5c_{n}+a_{n}+a_{n-1}$$

(d) $$c_{n+1}=6c_{n}-c_{n-1}$$

Combining (a) and (c) we get:

(e) $$b_{n+1}=4c_{n}+b_{n-1}$$

Combining (b) and (c) we get:

(f) $$a_{n+1}=4c_{n}+a_{n-1}$$

Combining these with the upcoming expressions for the legs, we have:

(g) $$c_{n}=\frac{1}{2}(3b_{n}-b_{n-1})+(-1)^n$$

(h) $$c_{n}=\frac{1}{2}(3a_{n}-a_{n-1})+(-1)^{n+1}$$

Combining (a), (g) and the upcoming expressions for $b$, we get:

(i) $$c_{n+1}=\frac{1}{2}(17b_{n}-3b_{n-1})+5(-1)^{n}$$

Combining (b), (h) and the upcoming expression for $a$, we get:

(j) $$c_{n+1}=\frac{1}{2}(17a_{n}-3a_{n-1})+5(-1)^{n+1}$$

(i) and (j) lead to:

(k) $$17(b_{n}-a_{n})-3(b_{n-1}-a_{n-1})=20(-1)^{n+1}$$

When $n$ is even, $b_n-a_n=-1$, and when $n$ is odd this difference is $+1$. Next week we will look at how the parity of the subscript of a Pell number relates to the parity of the number itself.

 

[MarkFL]

When $n$ is even, then $P_n$ is even. Let's use an identity where we know the subscript is even.

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

We see that it is the product of either an odd number and the sum of two even numbers, or the product of an even number and the sum of two odd numbers, both of which produce an even number. Let's now look at an identity where we know the subscript is odd.

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

Here we see it will be the sum of the square of an even number and the square of an odd number. This will be the sum of an even number and an odd number, which is odd. So now we know that the Pell numbers carry the parity of their subscript. Recall:

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

If we had decided to seed the sequence with $P_0=1$ and $P_1=2$, all of this would be reversed because in that case we would have:

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

We would still get the same sequence of numbers, but our identities would differ slightly. Many of our results depend on $P_0=0$. Later, we will develop identities for a more general case.

From this we can see that when $n$ is even, $a-b=1$, so we have shown that when $n$ is even, then we have $b_n-a_n=-1$. Conversely, this means that when $n$ is odd, this difference must be $+1$.

Back to (k). Let's look first at when $n$ is even. This would give:

$$17(-1)-3(+1)=20(-1)$$

Checks out, now when $n$ is odd:

$$17(+1)-3(-1)=20(+1)$$

Checks out again, and if the parities of the seeds were reversed, all the signs would be reversed and it would still be true.

Let's next look at:

$$a_{n}+a_{n-1}=(b_n\pm k)+(b_{n-1}\mp k)=b_{n}+b_{b-1}$$

Express in terms of Pell numbers:

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

Collect like terms and factor:

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

Divide out common factor:

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

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

Done.

Later, we shall explore the notion of $k$ being values other than unity in further detail, based on the seeds we choose. For now though, we will continue with $b$.

Analysis of the data suggests:

$$b_{n+1}=6b_{n}-\left(b_{n-1}+4(-1)^{n+1} \right)$$

Express as Pells:

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

Divide through by 2 and distribute:

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

We are going to use two alternate methods to finish.

Method 1:

Use $P_{n+1}P_{n}=2P_{n}^2+P_{n}P_{n-1}$ on the left:

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

Collect like terms:

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

On the left, replace $P_{n+1}$ with its equivalent $2P_{n}+P_{n-1}$:

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

Expand squared binomial:

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

Distribute on the left and on the right replace $P_{n+1}$ with its equivalent $2P_{n}+P_{n-1}$:

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

Distribute on the right:

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

Collect like terms:

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

Divide through by $-2$:

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

Shown as desired.

Now, instead of using $P_{n+1}P_{n}=2P_{n}^2+P_{n}P_{n-1}$ we could have finished by developing that formula in a different form. Recall we diverged at:

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

Next time we will look at another method to prove the statement using a formula for the product of two successive Pell numbers.

 

[MarkFL]

I wish to convey my apologies for keeping everyone waiting for 10 months for the next installment of our saga. (Hug) I pledge to post a new installment every Saturday evening my time (EST) until we are done. So, with no further ado, let's continue where we left off...

Method 2:

Before we proceed, we need a formula for the product of two successive Pell numbers.

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

If we continue in like manner, we may hypothesize that:

$$P_{n+1}P_{n}=2\sum_{k=0}^n\left(P_{k}^2 \right)$$

So, let's check the base case:

$$P_{1}P_{0}=2\sum_{k=0}^0\left(P_{k}^2 \right)$$

$$0=0$$

This is true, so again the induction hypothesis $H_{n}$ is:

$$P_{n+1}P_{n}=2\sum_{k=0}^n\left(P_{k}^2 \right)$$

As our inductive step, let's add $$2P_{n+1}^2$$ to both sides:

$$2P_{n+1}^2+P_{n+1}P_{n}=2\sum_{k=0}^n\left(P_{k}^2 \right)+2P_{n+1}^2$$

Factor the left side and incorporate the new term into the summation on the right side:

$$\left(2P_{n+1}+P_{n} \right)P_{n+1}=2\sum_{k=0}^{n+1}\left(P_{k}^2 \right)$$

Using the recursive definition of the Pell numbers on the left, we may write:

$$P_{(n+1)+1}P_{n+1}=2\sum_{k=0}^{n+1}\left(P_{k}^2 \right)$$

We have derived $H_{n+1}$ from $H_{n}$ thereby completing the proof by induction.

On with finding $b_{n}$, using our newly developed formula for the product of two successive Pell numbers. Recall we left off at:

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

Using the formula we developed, we may write:

$$2\sum_{k=0}^{n+1}\left(P_{k}^2 \right)=6\cdot2\sum_{k=0}^{n}\left(P_{k}^2 \right)-2\sum_{k=0}^{n-1}\left(P_{k}^2 \right)+2(-1)^{n}$$

Divide through by 2 and arrange as:

$$\sum_{k=0}^{n+1}\left(P_{k}^2 \right)+\sum_{k=0}^{n-1}\left(P_{k}^2 \right)=6\sum_{k=0}^{n}\left(P_{k}^2 \right)+(-1)^{n}$$

Pulling off the last two terms in the leftmost summation so that the indices of the two resulting sums are the same, we obtain:

$$P_{n+1}^2+P_{n}^2+\sum_{k=0}^{n-1}\left(P_{k}^2 \right)+\sum_{k=0}^{n-1}\left(P_{k}^2 \right)=6\sum_{k=0}^{n}\left(P_{k}^2 \right)+(-1)^{n}$$

Collect like terms:

$$P_{n+1}^2+P_{n}^2+2\sum_{k=0}^{n-1}\left(P_{k}^2 \right)=6\sum_{k=0}^{n}\left(P_{k}^2 \right)+(-1)^{n}$$

Pull the last term off of the sum on the right:

$$P_{n+1}^2+P_{n}^2+2\sum_{k=0}^{n-1}\left(P_{k}^2 \right)=6P_{n}^2+6\sum_{k=0}^{n-1}\left(P_{k}^2 \right)+(-1)^{n}$$

Collect like terms:

$$P_{n+1}^2-4\sum_{k=0}^{n-1}\left(P_{k}^2 \right)-5P_{n}^2=(-1)^{n}$$

For the first term on the left apply the recursive definition and expand the square and rewrite the sum using the formula we developed above:

$$\left(2P_{n}+P_{n-1} \right)^2-2\cdot2\sum_{k=0}^{n-1}\left(P_{k}^2 \right)-5P_{n}^2=(-1)^{n}$$

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

Collect like terms:

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

Divide through by $-1$ and arrange as:

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

Shown as desired. Next time we will find $a_{n}$.

 

[MarkFL]

Looking at the data in post #11, it would suggest that:

$$a_{n+1}=6a_{n}-a_{n-1}+4(-1)^{n+1}$$

We may express this inhomogeneous recursion in terms of Pell numbers as follows:

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

Distribute:

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

Collect like terms and move everything to the left side:

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

Rewrite the first term using the recursive definition:

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

Expand the resulting squared binomial and collect like terms:

$$4P_{n}P_{n+1}-3P_{n+1}^2+8P_{n}^2-P_{n-1}^2+4(-1)^{n}=0$$

Apply the recursive definition to the second term:

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

Expand the squared binomial, collect like terms and divide through by 4:

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

Apply the recursive definition to the second fact of the first term:

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

Distribute, collect like terms and arrange as:

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

Shown as desired. Next week we will investigate two ways to find the closed form expression for $P_{n}$. This week's installment was relatively short, but next week's topic deserves its own post.

I wrote the notes from which I am writing this tutorial almost 4 years ago, and at that time I did not know about characteristic roots and how they apply to finding the closed form for a linear recursion. So, I will first present my original method, and then the much easier method using the characteristic roots.

 

[MarkFL]

Expressing a Pell Number in Closed Form
​

We wish to find $P_n$ as a function of $n$. Recall that we earlier found:

$$\left(1\pm\sqrt{2} \right)^{n+1}=2\left(1\pm\sqrt{2} \right)^{n}+\left(1\pm\sqrt{2} \right)^{n-1}$$

This allows us to write:

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

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

And if we multiply the above two equations by different parameters, and then add them together, we obtain:

$$P(n+1)=2P(n)+P(n-1)$$

where:

$$P(n)=c_1\left(1+\sqrt{2} \right)^{n}+c_2\left(1-\sqrt{2} \right)^{n}$$

Now, at this point let's look at obtaining this closed form via the characteristic roots. From our recursion:

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

we obtain the characteristic equation:

$$r^2-2r-1=0$$

Application of the quadratic formula yields the characteristic roots:

$$r=1\pm\sqrt{2}$$

And so we know the closed forum is:

$$P(n)=c_1\left(1+\sqrt{2} \right)^{n}+c_2\left(1-\sqrt{2} \right)^{n}$$

This method will be useful later when we generalize concerning linear homogenous recursions.

Now, we may make use of our initial or seed values to determine the value of the parameters. Thus, we may state:

$$P(0)=c_1\left(1+\sqrt{2} \right)^{0}+c_2\left(1-\sqrt{2} \right)^{0}=c_1+c_2=0\implies c_1=-c_2$$

$$P(1)=c_1\left(1+\sqrt{2} \right)^{1}+c_2\left(1-\sqrt{2} \right)^{1}=-c_2\left(1+\sqrt{2} \right)+c_2\left(1-\sqrt{2} \right)=$$

$$-2\sqrt{2}c_2=1\implies c_2=-\frac{1}{2\sqrt{2}}\implies c_1=\frac{1}{2\sqrt{2}}$$

And so we have the closed form:

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

We should now be able to verify that:

$$P(n+1)=2P(n)+P(n-1)$$

Using our closed form, we may rewrite the left side as:

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

Group like terms together:

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

Factoring, we obtain:

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

Distribute and combine like terms:

$$P(n+1)=\frac{1}{2\sqrt{2}}\left(\left(1+\sqrt{2} \right)^{n-1}\left(3+2\sqrt{2} \right)-\left(1-\sqrt{2} \right)^{n-1}\left(3-2\sqrt{2} \right) \right)$$

Now, observing that the following is true:

$$\left(1\pm\sqrt{2} \right)^2=3\pm2\sqrt{2}$$

We may now write:

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

And so we have verified the closed form as desired.

Now, this closed form will get you a value for the $n$th Pell number immediately without the need for recursion, but with the heavy drawback of cumbersome binomials to expand for all but the smallest values of $n$.

Perhaps the binomial theorem can be used to cancel every other term and simplify our function definition, given that 1 is one of the terms of the binomials.

Recall the binomial theorem:

$$(x+y)^n=\sum_{k=0}^n\left[{n \choose k}x^{n-k}y^k \right]$$

Thus, our two binomials may be expressed as follows:

$$\left(1+\sqrt{2} \right)^n=\sum_{k=0}^n\left[{n \choose k}\left(\sqrt{2} \right)^k \right]$$

$$\left(1-\sqrt{2} \right)^n=\sum_{k=0}^n\left[{n \choose k}\left(-\sqrt{2} \right)^k \right]$$

Now, let's define:

$$w=\left(1+\sqrt{2} \right)^n-\left(1-\sqrt{2} \right)^n=\sum_{k=0}^n\left[{n \choose k}\sqrt{2}^k\left(1-(-1)^k \right) \right]$$

We see then that when $k$ is even, that term is zero, and so we may use the floor function to determine the number of terms, which we will call $p$. Observe that we may state:

$$p=\left\lfloor\frac{n+1}{2} \right\rfloor$$

And so we now have:

$$w=\sum_{k=1}^{p}\left[{n \choose 2k-1}2^{\frac{2k+1}{2}} \right]=2\sqrt{2}\sum_{k=1}^{p}\left[{n \choose 2k-1}2^{k-1} \right]$$

Now, we may notice that we may state:

$$P_{n}=\frac{w}{2\sqrt{2}}=\sum_{k=1}^{p}\left[{n \choose 2k-1}2^{k-1} \right]$$

Suppose now that $n$ is an odd number given by:

$$n=2q+1$$ and so:

$$p=\left\lfloor\frac{2(q+1)}{2} \right\rfloor=q+1$$

And so this allows us to state:

$$P_{2q+1}=\sum_{k=1}^{q+1}\left[{2q+1 \choose 2k-1}2^{k-1} \right]$$

This gives an alternate way to express the Pell numbers with odd indices, which is the sequence $c_n$.

Next week, we will look at "climbing down the ladder" to define the Pell numbers with negative indices.

 

[MarkFL]

Climbing Down the Ladder

Let's see if we can find the Pell numbers with negative indices, if they exist. If we know how to climb up a ladder, then, in theory at least, we should be able to climb down as well. We can reverse the direction in the sequence by taking the recursive formula we found and solving it for the $(n-1)$th term:

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

So, let's create a table and see if a pattern emerges:

[TABLE="class: grid, width: 250"]
[TR]
[TD]$n$[/TD]
[TD]$P_{-n}$
[/TD]
[/TR]
[TR]
[TD]-1[/TD]
[TD]$P_{-(-1)}=P_{1}=1$[/TD]
[/TR]
[TR]
[TD]0[/TD]
[TD]$P_{0}=0$[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]$P_{-1}=P_{1}-2P_{0}=1$[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]$P_{-2}=P_{0}-2P_{-1}=-2$[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]$P_{-3}=P_{-1}-2P_{-2}=5$[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]$P_{-4}=P_{-2}-2P_{-3}=-12$[/TD]
[/TR]
[/TABLE]

It appears that we may hypothesize:

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

We may choose to write this as:

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

Now, we may climb back up the ladder one rung to find the $(n-1)$th term using the standard recursion formula and our hypothesis, and then factor:

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

Using the reverse recursion, this becomes:

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

which may be written in the form:

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

And so our hypothesis is true, which means the Pell sequence is defined infinitely in both directions.

We have found that the Pell numbers with even indices are negated when their index is negated, and those with odd indices are unchanged when their index is negated. Thus, we may state:

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

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

Now, recall that we found:

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

So, what about:

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

Notice now, as $n\to-\infty$, the numerator has a smaller magnitude than the denominator, in fact it is simply the reciprocal of the limit where $n\to\infty$. We also know the limit will be negative since any two successive Pell numbers with negative indices will have opposite signs. So we may state:

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

Let's confirm this:

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

It follows then that:

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

We have found that as $n\to-\infty$, the convergence ratio is negated and inverted from what it as when $n\to\infty$, and this should make perfect sense since the indices are getting smaller as we approach negative infinity. As we approach positive infinity, the indices are getting larger. That would explain the inversion, while the negation is explained by every other term being negative. It appears that the negative solution to Pell's equation has come into play here.

Let's recall the two solutions to Pell's equation, represented here by $x=1+\sqrt{2}$ and $y=1-\sqrt{2}$ and observe that:

$$x=-\frac{1}{y}\implies y=-\frac{1}{x}$$

This explains explicitly the behavior of the limits as our indices approach both positive and negative infinity. As we approach positive infinity and take a pair of successive terms and find the ratio of the larger term to the smaller, we find this ratio approaches the positive solution to Pell's equation. Likewise, as we let the indices approach negative infinity, and take a pair of successive term and find the ratio of the term with the larger index, i.e., the number with the smaller magnitude, to the one with the smaller index, i.e., the number with the larger magnitude, we find this ratio approaches the negative solution to Pell's equation, which is of course, the negative multiplicative inverse of the positive solution.

Next week, we will begin exploring more identities of Pell numbers now that we know how to deal with negative indices.

 

[MarkFL]

Let's take a look at the following pattern:

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

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

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

This is enough to suggest the hypothesis:

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

This is our induction hypothesis $H_m$. Using the recursive definition, we may write:

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

Using the induction hypothesis, we obtain:

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

Distribute:

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

Factoring yields:

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

Use of the recursive definition gives us:

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

We have derived $H_{m+1}$ from $H_{m}$, thereby completing the proof by induction.

Next week, we will investigate some summations of Pell numbers.

 

[MarkFL]

Some Summations of The Pell Numbers
​

Let's examine a summation of the Pell numbers and see if any patterns arise:

[TABLE="class: grid, width: 500"]
[TR]
[TD]$n$[/TD]
[TD]$P_{n}$[/TD]
[TD]$$\sum_{k=0}^n\left(P_k \right)$$[/TD]
[/TR]
[TR]
[TD]$1$[/TD]
[TD]$1$[/TD]
[TD]$1=\left(P_0+P_1 \right)^2$[/TD]
[/TR]
[TR]
[TD]$2$[/TD]
[TD]$2$[/TD]
[TD]$3$[/TD]
[/TR]
[TR]
[TD]$3$[/TD]
[TD]$5$[/TD]
[TD]$8=2P_{2}^2$[/TD]
[/TR]
[TR]
[TD]$4$[/TD]
[TD]$12$[/TD]
[TD]$20$[/TD]
[/TR]
[TR]
[TD]$5$[/TD]
[TD]$29$[/TD]
[TD]$49=\left(P_2+P_3 \right)^2$[/TD]
[/TR]
[TR]
[TD]$6$[/TD]
[TD]$70$[/TD]
[TD]$119$[/TD]
[/TR]
[TR]
[TD]$7$[/TD]
[TD]$169$[/TD]
[TD]$288=2P_{4}^2$[/TD]
[/TR]
[TR]
[TD]$8$[/TD]
[TD]$408$[/TD]
[TD]$696$[/TD]
[/TR]
[TR]
[TD]$9$[/TD]
[TD]$985$[/TD]
[TD]$1681=\left(P_4+P_5 \right)^2$[/TD]
[/TR]
[TR]
[TD]$10$[/TD]
[TD]$2378$[/TD]
[TD]$4059$[/TD]
[/TR]
[TR]
[TD]$11$[/TD]
[TD]$5741$[/TD]
[TD]$9800=2P_{6}^2$[/TD]
[/TR]
[TR]
[TD]$12$[/TD]
[TD]$13860$[/TD]
[TD]$23660$[/TD]
[/TR]
[TR]
[TD]$13$[/TD]
[TD]$33461$[/TD]
[TD]$57121=\left(P_6+P_7 \right)^2$[/TD]
[/TR]
[/TABLE]

From this, we have the following two hypotheses to investigate:

(a) $$\sum_{k=0}^{4n-1}\left(P_{k} \right)=2P_{2n}^2$$

(b) $$\sum_{k=0}^{4n+1}\left(P_{k} \right)=\left(P_{2n}+P_{2n+1} \right)^2$$

If (a) is true, then we can write:

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

Collect the squared terms on the left and rewrite the index of the larger term while on the right, use the recursion formula to reduce the term with the greatest index:

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

Factor $2$ from the terms on the left and collect like terms on the right:

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

Factor difference of squares on the left and apply the recursion formula on the right:

$$2\left(P_{2n+2}+P_{2n} \right)\left(P_{2n+2}-P_{2n} \right)=4P_{4n+2}$$

Within each factor on the left use the recursion formula to reduce the terms with the greatest indices:

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

Collect like terms within factors on the left:

$$2\left(2P_{2n+1}+2P_{2n} \right)2P_{2n+1}=4P_{4n+2}$$

Divide through by 4 and arrange as:

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

On the right, apply the identity $$P_{2n}=2P_{n}\left(P_{n}+P_{n-1} \right)$$:

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

Shown as desired.

Now, if (b) is true, then we may write:

$$\sum_{k=0}^{4n+5}\left(P_{k} \right)=\left(P_{2n}+P_{2n+1} \right)^2+P_{4n+2}+P_{4n+3}+P_{4n+4}+P_{4n+5}= \left(P_{2(n+1)}+P_{2(n+1)+1} \right)^2$$

Rearranging, we can express the rightmost equality as:

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

Simplify the indices on the left and use the recursion formula to reduce the greatest term:

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

On the left factor the difference of squares and collect like terms on the right:

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

Rearrange terms on the left and use recursion formula on the two leftmost terms on the right:

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

On the left, reduce the terms with the largest index using the recursion formula within both factors:

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

Now collect like terms on the left:

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

Within the leftmost factor on the left, use the recursion formula to simplify:

$$4P_{2n+2}\left(3P_{2n+2}-P_{2n} \right)=4P_{4n+4}$$

Divide through by $4$, and within the rightmost factor on the left, reduce the greater term using the recursion formula:

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

On the left, distribute and collect like terms:

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

Factor on the left and factor indices where possible:

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

On the right, use the identity $$P_{2n}=2P_{n}\left(P_{n}+P_{n-1} \right)$$

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

Divide through by $$2P_{2(n+1)}$$ and simplify indices:

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

Collect like terms:

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

Rewrite left side using recursion formula:

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

Shown as desired.

Next week, we will look as using other seed or initial values to generate Pell-like sequences.

 

[MarkFL]

Using Other Seed Values to Generate Pell-Like Sequences​

If our seed values differ by $k\in\mathbb{Z}$ units, we can generate right triangles whose legs differ by some function of $k$ (a constant with alternating parity) by using the same recursive instructions, but with a different starting point.

Let $P_0=1$ and $P_1=3$. This produces the sequence:

$1,3,7,17,41,99,239,577,1393,3363,8110,19601,47321,\cdots$

As we shall later prove, those terms are equivalent to the Pell sum $P_{n-1}+P_{n}$. Letting the terms of this sequence serve as the numerator while the terms of the Pell sequence serve as the denominator will also yield rational approximations to $\sqrt{2}$:

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

As $n\to\infty$ this becomes:

$$1+\frac{1}{\sqrt{2}+1}=1+\sqrt{2}-1=\sqrt{2}$$

As we shall later prove, this new sequence can be used along with the Pell sequence to generate an infinite number of solutions to Pell's equation. Let's look at another sequence.

Let $P_0=0$ and $P_1=2$. This sequence begins with the terms:

$0,2,4,10,24,58,140,816,1970,4756,11482,27720,66922,\cdots$

It appears that this sequence is simply the doubling of the Pell Sequence. Let's try other sequences.

Let $P_0=3$ and $P_1=5$:

$3,5,13,31,75,181,437,1055,2547,6149,14845,35839,86523,\cdots$

Let $P_0=2$ and $P_1=3$:

$2,3,8,19,46,111,268,647,1562,3771,9104,21979, \cdots$

Let's see what kind of triangles this last sequence generates:

[table="width: 500, class: grid"]
[tr]
[td]$n$[/td]
[td]$m$[/td]
[td]$a$[/td]
[td]$b$[/td]
[td]$c$[/td]
[/tr]
[tr]
[td]2[/td]
[td]3[/td]
[td]5[/td]
[td]12[/td]
[td]15[/td]
[/tr]
[tr]
[td]3[/td]
[td]8[/td]
[td]55[/td]
[td]48[/td]
[td]73[/td]
[/tr]
[tr]
[td]8[/td]
[td]19[/td]
[td]297[/td]
[td]304[/td]
[td]425[/td]
[/tr]
[tr]
[td]19[/td]
[td]46[/td]
[td]1755[/td]
[td]1748[/td]
[td]2477[/td]
[/tr]
[/table]

We see that $a$ and $b$ differ by a constant 7. Let's look at another sequence and the triangles it generates.

Let $P_0=3$ and $P_1=4$:

$3,4,11,26,63,152,367,886,2139,5164,12467,\cdots$

[table="width: 500, class: grid"]
[tr]
[td]$n$[/td]
[td]$m$[/td]
[td]$a$[/td]
[td]$b$[/td]
[td]$c$[/td]
[/tr]
[tr]
[td]3[/td]
[td]4[/td]
[td]7[/td]
[td]24[/td]
[td]25[/td]
[/tr]
[tr]
[td]4[/td]
[td]11[/td]
[td]105[/td]
[td]88[/td]
[td]137[/td]
[/tr]
[tr]
[td]11[/td]
[td]26[/td]
[td]555[/td]
[td]572[/td]
[td]797[/td]
[/tr]
[tr]
[td]26[/td]
[td]63[/td]
[td]3293[/td]
[td]3276[/td]
[td]4645[/td]
[/tr]
[/table]

Now we see that $a$ and $b$ always differ by 17.

Next week, we will examine what happens when we use variable seed values.

 

[RLBrown]

Hi MarkFL,

I am new to this Forum, and was fascinated by your treaties on Pell Numbers. I have a Matrix recursion for Twin Primitive Pythagorean Triples, that you may find amusing.

See: Twin and Nearly Twin Pythagorean Triples