Exploring the Pell Numbers

Math 242 Modern Computational Mathematics

Generalizing the Fibonacci Numbers

Today we will modify our gibonacciList module from last class so that we can specify not only the initial values, but also the coefficients in the recursive formula. Specifically, we will compute generalized Fibonacci (or “gibonacci”) sequences defined as follows:

(Subscript[G, 0])=a, (Subscript[G, 1])=b, and (Subscript[G, n])=r (Subscript[G, n-1])+s (Subscript[G, n-2])

for any values a, b, r, and s that we specify.

gibonacciList[a_,b_,r_,s_,n_]:=Module[{gibList=Table[0,n+1]},
(* set the initial values (Subscript[G, 0]) and (Subscript[G, 1]) *)
gibList[[1]]=a;
gibList[[2]]=b;

(* compute (Subscript[G, 2]) through (Subscript[G, n]) and store them in the list *)
Do[
gibList[[i]]=r*gibList[[i-1]]+s*gibList[[i-2]]
,{i,3,n+1}];

(* return the list *)
gibList
]

Now we can compute the Fibonacci numbers:

gibonacciList[0,1,1,1,10]

We can also compute the Lucas numbers:

gibonacciList[2,1,1,1,10]

We can also compute the Pell numbers, which are defined by (Subscript[P, 0])=0, (Subscript[P, 1])=1, and (Subscript[P, n])=2(Subscript[P, n-1])+(Subscript[P, n-2]).

gibonacciList[0,1,2,1,20]

Let's create a big list of Pell numbers and define a little function to fix the indexing, as we have for the other sequences:

pellList=gibonacciList[0,1,2,1,10000];
p[n_]:=pellList[[n+1]]

Print the first few numbers to confirm that our code works correctly:

p/@Range[0,12]

Identities and Properties Involving Pell Numbers

Explore the following question to discover identities and properties involving the Pell numbers.

1. Ratios of Pell numbers

Examine the ratios ((Subscript[P, n+m])/(Subscript[P, n])) for various n and m. Formulate a conjecture about (lim_(n->∞))((Subscript[P, n+m])/(Subscript[P, n])) for m∈{1,2,3,...} supported by your computational evidence.

Solution

First try m=1:

N[Table[p[n+1]/p[n],{n,1,20}],20]

We can recognize this (e.g., using the Online Encyclopedia of Integer Sequences), as 1+(Sqrt[2]).

N[1+Sqrt[2],20]

Now make a table for various values of m and n:

N[TableForm[Table[p[n+m]/p[n],{n,1,20},{m,1,10}],TableHeadings->{{"n=1","n=2","..."},{"m=1","m=2","..."}}],10]

N[Table[(((1+(Sqrt[2])))^m),{m,1,10}],10]

Conjecture: The Pell numbers satisfy (lim_(n->∞))((Subscript[P, n+m])/(Subscript[P, n]))=(((1+(Sqrt[2])))^m) for positive integers m.

2. Which Pell numbers are divisible by other Pell numbers?

For example, (Subscript[P, 4])=12 divides (Subscript[P, 8])=408. Formulate a conjecture supported by computational evidence. As a bonus, prove your conjecture.

Solution

Here is a solution using a 2-dimensional table:

TableForm[Table[ Divisible[p[n],p[m]],{n,1,20},{m,1,10}],TableHeadings->{Table["n="<>ToString[n],{n,1,20}],Table["m="<>ToString[m],{m,1,10}]}]

Look at the pattern in where True appears in the table.

Conjecture: (Subscript[P, n]) divides (Subscript[P, m]) exactly when n divides m.

3. Is there Pell number identity involving (Subscript[P, m])(Subscript[P, n+1])-(Subscript[P, n])(Subscript[P, m+1])?

Compute (Subscript[P, m])(Subscript[P, n+1])-(Subscript[P, n])(Subscript[P, m+1]) for various positive integers n. Formulate a conjecture. Optionally, generalize your identity by adding a new index.

Solution

Here is a solution involving tables:

t1=Table[p[m]p[n+1]-p[n]p[m+1],{n,1,20},{m,1,10}];
TableForm[t1,TableHeadings->{Table["n="<>ToString[n],{n,1,20}],Table["m="<>ToString[m],{m,1,10}]}]

Conjecture: The Pell numbers satisfy (Subscript[P, m])(Subscript[P, n+1])-(Subscript[P, n])(Subscript[P, m+1])=(((-1))^n)(Subscript[P, m-n]) for integers m>n and (Subscript[P, m])(Subscript[P, n+1])-(Subscript[P, n])(Subscript[P, m+1])=(((-1))^(m+1))(Subscript[P, n-m]) for integers n>m

4. Sums of Pell numbers

Formulate a conjecture involving each of the following sums.

(∑_(k=0)^n)(Subscript[P, 2k+1])

Solution

2*Table[Sum[p[2k+1],{k,0,n}],{n,0,10}]

Conjecture: The Pell numbers satisfy 2(∑_(k=0)^n)(Subscript[P, 2k+1])=(Subscript[P, 2n+2]) for nonnegative integers n.

(∑_(k=0)^n)(Subscript[P, 2k])

Solution

2*Table[Sum[p[2k],{k,0,n}],{n,0,10}]

Conjecture: The Pell numbers satisfy 2(∑_(k=0)^n)(Subscript[P, 2k+1])=(Subscript[P, 2n+1])-1 for nonnegative integers n.

(∑_(k=0)^n)(Subscript[P, k])

Solution

2*Table[Sum[p[k],{k,1,n}],{n,1,10}]

p/@Range[20]

Conjecture: 2(∑_(k=0)^n)(Subscript[P, k])=(Subscript[P, n+1])+(Subscript[P, n])-1

5. Are there any squares, cubes, or higher powers in the Pell sequence?

Search for Pell numbers of the form (a^b) for some integers a and b. State a conjecture...

Solution

Do[
If[IntegerQ[Sqrt[p[n]]],Print[{n,p[n]}]],
{n,0,10000}
]

Conjecture: The only Pell numbers that are squares are 0, 1, and 169.

Do[
If[IntegerQ[CubeRoot[p[n]]],Print[{n,p[n]}]],
{n,0,10000}
]

Conjecture: The only Pell numbers that are cubes are 0, and 1.

6. Are there polynomial identities involving the Pell numbers?

Recall the polynomial identities that we found for the Fibonacci and Lucas numbers. Do similar identities hold for the Pell numbers?

Solution involving a module

findPellCoefficients[q_]:=Module[{nvals,matrix, vector,sol},
(* set up the nvals *)
nvals=Range[2,2q+2,2];
Print["nvals:",nvals];

(* set up the matrix *)
matrix=Table[p[n]^i,{n,nvals},{i,q,0,-1}];
Print["matrix:",MatrixForm[matrix]];

(* set up the vector *)
vector=Table[p[q*n],{n,nvals}];
Print["vector:",vector];

(* solve the system *)
sol=LinearSolve[matrix,vector];
Print["solution:",sol];

(* return the solution *)
sol
]

(a) P=a (Subscript[P, n]^2) +b (Subscript[P, n])+c for some coefficients a,b,c and positive integers n.

findPellCoefficients[2]

We could explore further, but these fractions don’t look promising.

(b) (Subscript[P, 3n])=a (Subscript[P, n]^3) +b (Subscript[P, n]^2)+c (Subscript[P, n])+d for some coefficients a,b,c,d and positive integers n.

findPellCoefficients[3]

Maybe the identity is (Subscript[P, 3n])= 8(Subscript[P, n]^3) +(((-1))^n)3(Subscript[P, n]) for nonnegative n? Try a table of values:

TableForm[Table[{n,p[3n],8((p[n])^3)+(((-1))^n)3p[n]},{n,1,10}],TableHeadings->{None,{"n","(Subscript[P, 3  n])","8(Subscript[P, n]^3) +(-1)^n3(Subscript[P, n])"}}]

(c) (Subscript[P, 5n])=(Subscript[a, 1]) (Subscript[P, n]^5) +(Subscript[a, 2]) (Subscript[P, n]^4)+(Subscript[a, 3]) (Subscript[P, n]^3) +(Subscript[a, 4]) (Subscript[P, n]^2)+(Subscript[a, 5]) (Subscript[P, n])+(Subscript[a, 6]) for some coefficients (Subscript[a, 1]),...,(Subscript[a, 6]) and positive integers n.

findPellCoefficients[5]

Maybe the identity is (Subscript[P, 5n])= 60(Subscript[P, n]^5)+(((-1))^n)40(Subscript[P, n]^3) +5(Subscript[P, n]) for nonnegative n? Try a table of values:

TableForm[Table[{n,p[5n],64((p[n])^5)+(((-1))^n)40((p[n])^3)+5p[n]},{n,1,10}],TableHeadings->{None,{"n","(Subscript[P, 5  n])","60(Subscript[P, n]^5) +(-1)^n40(Subscript[P, n]^3) + 5(Subscript[P, n])"}}]