The first factorization discovered (and "proved") in James Sellers' paper
Domino Tilings and Products of Fibonacci and Pell Numbers
published in Journal of Integer Sequences, Vol. 5 (2002), Article 02.\
1.2, is:
Theorem: Let F(n) be the sequence defined by the recurrence
F(n) = 2 F(n - 1) + 7 F(n - 2) + 2 F(n - 3) - F(n - 4)
subject to the initial conditions
F(0) = 2, F(1) = 10, F(2) = 36, F(3) = 145
Let G(n) be the sequence defined on non-negative integers by the recurrence
G(n) = G(n - 1) + G(n - 2)
subject to the initial conditions
G(0) = 1, G(1) = 2
Let H(n) be the sequence defined by the recurrence
H(n) = 2 H(n - 1) + H(n - 2)
subject to the initial conditions
H(0) = 2, H(1) = 5
Then the following is true for every non-negative integer n
F(n) = G(n) H(n)
Proof: Routine! (since everything in sight is C-finite) .
---------------------------------------------------------------------
The second factorization discovered (and "proved") in that paper is:
Theorem: Let F(n) be the sequence defined by the recurrence
F(n) = 15 F(n - 1) - 32 F(n - 2) + 15 F(n - 3) - F(n - 4)
subject to the initial conditions
F(0) = 1, F(1) = 8, F(2) = 95, F(3) = 1183
Let G(n) be the sequence defined on non-negative integers by the recurrence
G(n) = 3 G(n - 1) - G(n - 2)
subject to the initial conditions
G(0) = 1, G(1) = 2
Let H(n) be the sequence defined by the recurrence
H(n) = 5 H(n - 1) - H(n - 2)
subject to the initial conditions
H(0) = 1, H(1) = 4
Then the following is true for every non-negative integer n
F(n) = G(n) H(n)
Proof: Routine! (since everything in sight is C-finite) .
-------------------------------------------------------------------------
The third factorization discovered (and whose "proof" was left to the reader\
, since it was too "complicated") in that paper is:
Theorem: Let F(n) be the sequence defined by the recurrence
F(n) = F(n - 1) + 76 F(n - 2) + 69 F(n - 3) - 921 F(n - 4) - 584 F(n - 5)
+ 4019 F(n - 6) + 829 F(n - 7) - 7012 F(n - 8) + 829 F(n - 9)
+ 4019 F(n - 10) - 584 F(n - 11) - 921 F(n - 12) + 69 F(n - 13)
+ 76 F(n - 14) + F(n - 15) - F(n - 16)
subject to the initial conditions
F(0) = 1, F(1) = 1, F(2) = 34, F(3) = 153, F(4) = 2245, F(5) = 14824,
F(6) = 167089, F(7) = 1292697, F(8) = 12988816, F(9) = 108435745,
F(10) = 1031151241, F(11) = 8940739824, F(12) = 82741005829,
F(13) = 731164253833, F(14) = 6675498237130, F(15) = 59554200469113
Let G(n) be the sequence defined on non-negative integers by the recurrence
G(n) = G(n - 1) + G(n - 2)
subject to the initial conditions
G(0) = 1, G(1) = 1
Let H(n) be the sequence defined by the recurrence
H(n) = H(n - 1) + 25 H(n - 2) + 11 H(n - 3) - 47 H(n - 4) - 11 H(n - 5)
+ 25 H(n - 6) - H(n - 7) - H(n - 8)
subject to the initial conditions
H(0) = 1, H(1) = 1, H(2) = 17, H(3) = 51, H(4) = 449, H(5) = 1853, H(6) = 12853,
H(7) = 61557
Then the following is true for every non-negative integer n
F(n) = G(n) H(n)
Proof: Routine! (since everything in sight is C-finite) .
---------------------------------------------------------------------------
This took, 0.497, seconds .