Exploring the Pell Numbers

Math 242 Modern Computational Mathematics

Generalizing the Fibonacci recurrence

We will modify our gibonacciList module from last class so that we can specify 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
]

Make sure it works:

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

The Pell numbers are defined with a=0, b=1, r=2, and s=1.

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

The Pell Numbers

Since we will explore the Pell numbers today, let’s create a big list of Pell numbers:

pellList=gibonacciList[0,1,2,1,10000];

Next we create a little function l to adjust the indexing to match the usual mathematical notation. (That is, (Subscript[P, 0])=2, (Subscript[P, 1])=1, and (Subscript[P, n])=2(Subscript[P, n-1])+(Subscript[P, n-2]).)

p[n_]:=pellList[[n+1]]

1. Ratios of Pell numbers

(a) Examine the ratios ((Subscript[P, n+1])/(Subscript[P, n])) for various n. Do these ratios converge to some number as n increases? Formulate a conjecture supported by your computational evidence.

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

N[1+(Sqrt[2]),20]

Conjecture: The ratio of Pell numbers ((Subscript[P, n+1])/(Subscript[P, n])) converges to 1+(Sqrt[2]) as n->∞.

(b) 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.

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

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

Conjecture: (lim_(n->∞))((Subscript[P, n+1])/(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.

TableForm[Table[ Divisible[p[n],p[m]],{n,1,20},{m,1,10}],TableHeadings->{p/@Range[20],p/@Range[10]}]

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.

TableForm[Table[p[m]p[n+1]-p[n]p[m+1],{n,1,20},{m,1,10}],TableHeadings->{{"n"},{"m"}}]

Table[p[m]p[n+1]-p[n]p[m+1]==(((-1))^(m+1))p[n-m],{n,1,20},{m,1,n}]//TableForm

Conjecture: (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. Hint: multiply by 2.

p/@Range[20]

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

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

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

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

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

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

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

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

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.

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?

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[L, 3n])=a (Subscript[L, n]^3) +b (Subscript[L, n]^2)+c (Subscript[L, 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])"}}]