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:

\(\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.

 

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

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

Developing the Identities

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

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

Solve for $P_n$:

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

Multiply through by $P_n$:

\(\displaystyle 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:

\(\displaystyle 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)\)

\(\displaystyle 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)\)

\(\displaystyle 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:

\(\displaystyle P_{2n+1}=P_{n+1}^2+P_{n}^2\)

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

\(\displaystyle 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}=\)

\(\displaystyle 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:

\(\displaystyle 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}=\)

\(\displaystyle 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}=\)

\(\displaystyle P_{i-1}P_{j+3}+P_{i-2}P_{j+2}\)

Here is what we have so far:

\(\displaystyle 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.

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

\(\displaystyle P_{n+1}^2+P_{n}^2=P_1P_{2n+1}+P_0P_{2n-1}\)

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

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

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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}$:

\(\displaystyle \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:

\(\displaystyle 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:

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

Now use \(\displaystyle P_{n+1}=2P_{n}+P_{n-1}\) and expand and distribute:

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

\(\displaystyle 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\)

\(\displaystyle 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}$.

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

Simplify subscripts:

\(\displaystyle P_{2n+3}=6P_{2n+1}-P_{2n-1}\)

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

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

Collect like terms:

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

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

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

Distribute:

\(\displaystyle 4P_{2n+1}+2P_{2n}=5P_{2n+1}-P_{2n-1}\)

Collect like terms:

\(\displaystyle 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:

\(\displaystyle 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:

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

To begin, let's state:

\(\displaystyle \lim_{n\to\infty}\frac{c_{n+1}}{c_{n}}=L\)

Using the recursive definition, we may write:

\(\displaystyle \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:

\(\displaystyle L=6-\frac{1}{L}\)

\(\displaystyle L^2-6L+1=0\)

The larger root is indeed \(\displaystyle 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:

\(\displaystyle c_{n}=b_{n}+b_{n-1}+c_{n-1}\)

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

\(\displaystyle 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:

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

Divide out common factor:

\(\displaystyle 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:

\(\displaystyle c_n=a_n+a_{n-1}+c_{n-1}\)

Express in Pell numbers:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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

\(\displaystyle c_{n+1}=6c_{n}-c_{n-1}\)

Combining the two, we could write:

\(\displaystyle 6c_{n}-c_{n-1}=5c_{n}+b_{n}+b_{n-1}=5c_{n}+a_{n}+a_{n-1}\)

\(\displaystyle c_{n}-c_{n-1}=b_{n}+b_{n-1}=a_{n}+a_{n-1}\)

First, let's look at:

\(\displaystyle c_{n}-c_{n-1}=b_{n}+b_{n-1}\)

Express in Pell numbers:

\(\displaystyle (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:

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

We have seen before that this implies:

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

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

\(\displaystyle c_{n}-c_{n-1}=a_{n}+a_{n-1}\)

\(\displaystyle (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:

\(\displaystyle 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) \(\displaystyle c_{n+1}=b_{n+1}+b_{n}+c_{n}\)

(b) \(\displaystyle c_{n+1}=a_{n+1}+a_{n}+c_{n}\)

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

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

Combining (a) and (c) we get:

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

Combining (b) and (c) we get:

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

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

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

(h) \(\displaystyle 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) \(\displaystyle 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) \(\displaystyle c_{n+1}=\frac{1}{2}(17a_{n}-3a_{n-1})+5(-1)^{n+1}\)

(i) and (j) lead to:

(k) \(\displaystyle 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.

\(\displaystyle 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.

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 17(-1)-3(+1)=20(-1)\)

Checks out, now when $n$ is odd:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle \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:

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

Divide out common factor:

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

\(\displaystyle 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:

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

Express as Pells:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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}$:

\(\displaystyle 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:

\(\displaystyle 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}$:

\(\displaystyle 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:

\(\displaystyle 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:

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

Divide through by $-2$:

\(\displaystyle 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:

\(\displaystyle 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.

\(\displaystyle 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:

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

So, let's check the base case:

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

\(\displaystyle 0=0\)

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

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

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

\(\displaystyle 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:

\(\displaystyle \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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle \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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle \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}\)

\(\displaystyle 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:

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

Divide through by $-1$ and arrange as:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle \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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle \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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle \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:

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

\(\displaystyle \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:

\(\displaystyle P(n+1)=2P(n)+P(n-1)\)

where:

\(\displaystyle 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:

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

we obtain the characteristic equation:

\(\displaystyle r^2-2r-1=0\)

Application of the quadratic formula yields the characteristic roots:

\(\displaystyle r=1\pm\sqrt{2}\)

And so we know the closed forum is:

\(\displaystyle 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:

\(\displaystyle 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\)

\(\displaystyle 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)=\)

\(\displaystyle -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:

\(\displaystyle 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:

\(\displaystyle P(n+1)=2P(n)+P(n-1)\)

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

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

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

We may now write:

\(\displaystyle 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:

\(\displaystyle (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:

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

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

Now, let's define:

\(\displaystyle 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:

\(\displaystyle p=\left\lfloor\frac{n+1}{2} \right\rfloor\)

And so we now have:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle n=2q+1\) and so:

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

And so this allows us to state:

\(\displaystyle 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:

\(\displaystyle 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:

$n$	$P_{-n}$
-1	$P_{-(-1)}=P_{1}=1$
0	$P_{0}=0$
1	$P_{-1}=P_{1}-2P_{0}=1$
2	$P_{-2}=P_{0}-2P_{-1}=-2$
3	$P_{-3}=P_{-1}-2P_{-2}=5$
4	$P_{-4}=P_{-2}-2P_{-3}=-12$

It appears that we may hypothesize:

\(\displaystyle P_{-n}=(-1)^{n+1}P_{n}\)

We may choose to write this as:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle P_{-(n-1)}=(-1)^{(n-1)+1}P_{n-1}\)

which may be written in the form:

\(\displaystyle 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:

\(\displaystyle P_{-2n}=-P_{2n}\)

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

Now, recall that we found:

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

So, what about:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle 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:

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

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

\(\displaystyle 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:

\(\displaystyle 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:

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

Using the induction hypothesis, we obtain:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

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

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

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

(b) \(\displaystyle \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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

\(\displaystyle 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:

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

Divide through by 4 and arrange as:

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

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

\(\displaystyle 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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle \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:

\(\displaystyle 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:

\(\displaystyle 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:

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

Factor on the left and factor indices where possible:

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

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

\(\displaystyle 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 \(\displaystyle 2P_{2(n+1)}\) and simplify indices:

\(\displaystyle 3P_{2n+1}+P_{2n}=P_{2n+2}+P_{2n+1}\)

Collect like terms:

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

Rewrite left side using recursion formula:

\(\displaystyle 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}$:

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

As $n\to\infty$ this becomes:

\(\displaystyle 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:

$n$	$m$	$a$	$b$	$c$
2	3	5	12	15
3	8	55	48	73
8	19	297	304	425
19	46	1755	1748	2477

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$

$n$	$m$	$a$	$b$	$c$
3	4	7	24	25
4	11	105	88	137
11	26	555	572	797
26	63	3293	3276	4645

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