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 .