------------------------------ Proof of the first Sellers identity A proof in the Spirit of Zeilberger of A C-finite Identity Theorem: Let F(n) be the sequence defined by the recurrence F(n) = F(n - 1) + F(n - 2) subject to the initial conditions F(0) = 1, F(1) = 2 Equivalently, the ordinary generating function of F(n) w.r.t. to t is infinity ----- \ n 1 + t ) F(n) t = ---------- / 2 ----- 1 - t - t n = 0 Also Let G(n) be the sequence defined by the recurrence G(n) = 2 G(n - 1) + G(n - 2) subject to the initial conditions G(0) = 2, G(1) = 5 Equivalently, the ordinary generating function of G(n) w.r.t. to t is infinity ----- \ n 2 + t ) G(n) t = ------------ / 2 ----- 1 - 2 t - t n = 0 Let H(n)=F(n)G(n), then infinity ----- 2 3 \ n 2 + 6 t + 2 t - t ) H(n) t = -------------------------- / 2 3 4 ----- 1 - 2 t - 7 t - 2 t + t n = 0 or equivalently, H(n) is the sequence defined by the recurrence H(n) = 2 H(n - 1) + 7 H(n - 2) + 2 H(n - 3) - H(n - 4) subject to the initial conditions H(0) = 2, H(1) = 10, H(2) = 36, H(3) = 145 Proof: F(n) is a C-finite sequence of order, 2 and G(n) is a C-finite sequence of order, 2 Hence their product is a C-finite sequence of order 4 Since the claimed sequence for their product is a C-finite sequence of order, 4, it suffices to check the equality for the first, 8, values The first, 8, members of the sequence F(n) are [1, 2, 3, 5, 8, 13, 21, 34] The first, 8, members of the sequence G(n) are [2, 5, 12, 29, 70, 169, 408, 985] The first, 8, members of the proposed product are [2, 10, 36, 145, 560, 2197, 8568, 33490] 1, times , 2, is indeed , 2 2, times , 5, is indeed , 10 3, times , 12, is indeed , 36 5, times , 29, is indeed , 145 8, times , 70, is indeed , 560 13, times , 169, is indeed , 2197 21, times , 408, is indeed , 8568 34, times , 985, is indeed , 33490 QED! Proof of the second Sellers identity A proof in the Spirit of Zeilberger of A C-finite Identity Theorem: Let F(n) be the sequence defined by the recurrence F(n) = 3 F(n - 1) - F(n - 2) subject to the initial conditions F(0) = 1, F(1) = 2 Equivalently, the ordinary generating function of F(n) w.r.t. to t is infinity ----- \ n 1 - t ) F(n) t = ------------ / 2 ----- 1 - 3 t + t n = 0 Also Let G(n) be the sequence defined by the recurrence G(n) = 5 G(n - 1) - G(n - 2) subject to the initial conditions G(0) = 1, G(1) = 4 Equivalently, the ordinary generating function of G(n) w.r.t. to t is infinity ----- \ n 1 - t ) G(n) t = ------------ / 2 ----- 1 - 5 t + t n = 0 Let H(n)=F(n)G(n), then infinity ----- 2 3 \ n 1 - 7 t + 7 t - t ) H(n) t = ----------------------------- / 2 3 4 ----- 1 - 15 t + 32 t - 15 t + t n = 0 or equivalently, H(n) is the sequence defined by the recurrence H(n) = 15 H(n - 1) - 32 H(n - 2) + 15 H(n - 3) - H(n - 4) subject to the initial conditions H(0) = 1, H(1) = 8, H(2) = 95, H(3) = 1183 Proof: F(n) is a C-finite sequence of order, 2 and G(n) is a C-finite sequence of order, 2 Hence their product is a C-finite sequence of order 4 Since the claimed sequence for their product is a C-finite sequence of order, 4, it suffices to check the equality for the first, 8, values The first, 8, members of the sequence F(n) are [1, 2, 5, 13, 34, 89, 233, 610] The first, 8, members of the sequence G(n) are [1, 4, 19, 91, 436, 2089, 10009, 47956] The first, 8, members of the proposed product are [1, 8, 95, 1183, 14824, 185921, 2332097, 29253160] 1, times , 1, is indeed , 1 2, times , 4, is indeed , 8 5, times , 19, is indeed , 95 13, times , 91, is indeed , 1183 34, times , 436, is indeed , 14824 89, times , 2089, is indeed , 185921 233, times , 10009, is indeed , 2332097 610, times , 47956, is indeed , 29253160 QED! Proof of the third Sellers identity A proof in the Spirit of Zeilberger of A C-finite Identity Theorem: Let F(n) be the sequence defined by the recurrence F(n) = F(n - 1) + F(n - 2) subject to the initial conditions F(0) = 1, F(1) = 1 Equivalently, the ordinary generating function of F(n) w.r.t. to t is infinity ----- \ n 1 ) F(n) t = ---------- / 2 ----- 1 - t - t n = 0 Also Let G(n) be the sequence defined by the recurrence G(n) = G(n - 1) + 25 G(n - 2) + 11 G(n - 3) - 47 G(n - 4) - 11 G(n - 5) + 25 G(n - 6) - G(n - 7) - G(n - 8) subject to the initial conditions G(0) = 1, G(1) = 1, G(2) = 17, G(3) = 51, G(4) = 449, G(5) = 1853, G(6) = 12853, G(7) = 61557 Equivalently, the ordinary generating function of G(n) w.r.t. to t is infinity ----- 2 3 4 6 \ n 1 - 9 t - 2 t + 9 t - t ) G(n) t = ------------------------------------------------------- / 2 3 4 5 6 7 8 ----- 1 - t - 25 t - 11 t + 47 t + 11 t - 25 t + t + t n = 0 Let H(n)=F(n)G(n), then infinity ----- \ n 2 3 4 5 6 8 ) H(n) t = (1 - 43 t - 26 t + 360 t + 110 t - 1033 t + 1033 t / ----- n = 0 9 10 11 12 14 / 2 3 - 110 t - 360 t + 26 t + 43 t - t ) / (1 - t - 76 t - 69 t / 4 5 6 7 8 9 10 + 921 t + 584 t - 4019 t - 829 t + 7012 t - 829 t - 4019 t 11 12 13 14 15 16 + 584 t + 921 t - 69 t - 76 t - t + t ) or equivalently, H(n) is the sequence defined by the recurrence H(n) = H(n - 1) + 76 H(n - 2) + 69 H(n - 3) - 921 H(n - 4) - 584 H(n - 5) + 4019 H(n - 6) + 829 H(n - 7) - 7012 H(n - 8) + 829 H(n - 9) + 4019 H(n - 10) - 584 H(n - 11) - 921 H(n - 12) + 69 H(n - 13) + 76 H(n - 14) + H(n - 15) - H(n - 16) subject to the initial conditions H(0) = 1, H(1) = 1, H(2) = 34, H(3) = 153, H(4) = 2245, H(5) = 14824, H(6) = 167089, H(7) = 1292697, H(8) = 12988816, H(9) = 108435745, H(10) = 1031151241, H(11) = 8940739824, H(12) = 82741005829, H(13) = 731164253833, H(14) = 6675498237130, H(15) = 59554200469113 Proof: F(n) is a C-finite sequence of order, 2 and G(n) is a C-finite sequence of order, 8 Hence their product is a C-finite sequence of order 16 Since the claimed sequence for their product is a C-finite sequence of order, 16, it suffices to check the equality for the first, 32, values The first, 32, members of the sequence F(n) are [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309] The first, 32, members of the sequence G(n) are [1, 1, 17, 51, 449, 1853, 12853, 61557, 382024, 1971559, 11585969, 62088471, 355111613, 1939427729, 10943439733, 60338602299, 338172377293, 1873494595072, 10464657396101, 58113694771149, 324052035315389, 1801727076022631, 10038214290617749, 55845947547948897, 311010011115265801, 1730773816266538081, 9636747170211055304, 53636683818362516979, 298610928685279993661, 1662149072277201394907, 9253169548548380483401, 51507590702129135617317] The first, 32, members of the proposed product are [1, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 1031151241, 8940739824, 82741005829, 731164253833, 6675498237130, 59554200469113, 540061286536921, 4841110033666048, 43752732573098281, 393139145126822985, 3547073578562247994, 31910388243436817641, 287665106926232833093, 2589464895903294456096, 23333526083922816720025, 210103825878043857266833, 1892830605678515060701072, 17046328120997609883612969, 153554399246902845860302369, 1382974514097522648618420280, 12457255314954679645007780869, 112199448394764215277422176953] 1, times , 1, is indeed , 1 1, times , 1, is indeed , 1 2, times , 17, is indeed , 34 3, times , 51, is indeed , 153 5, times , 449, is indeed , 2245 8, times , 1853, is indeed , 14824 13, times , 12853, is indeed , 167089 21, times , 61557, is indeed , 1292697 34, times , 382024, is indeed , 12988816 55, times , 1971559, is indeed , 108435745 89, times , 11585969, is indeed , 1031151241 144, times , 62088471, is indeed , 8940739824 233, times , 355111613, is indeed , 82741005829 377, times , 1939427729, is indeed , 731164253833 610, times , 10943439733, is indeed , 6675498237130 987, times , 60338602299, is indeed , 59554200469113 1597, times , 338172377293, is indeed , 540061286536921 2584, times , 1873494595072, is indeed , 4841110033666048 4181, times , 10464657396101, is indeed , 43752732573098281 6765, times , 58113694771149, is indeed , 393139145126822985 10946, times , 324052035315389, is indeed , 3547073578562247994 17711, times , 1801727076022631, is indeed , 31910388243436817641 28657, times , 10038214290617749, is indeed , 287665106926232833093 46368, times , 55845947547948897, is indeed , 2589464895903294456096 75025, times , 311010011115265801, is indeed , 23333526083922816720025 121393, times , 1730773816266538081, is indeed , 210103825878043857266833 196418, times , 9636747170211055304, is indeed , 1892830605678515060701072 317811, times , 53636683818362516979, is indeed , 17046328120997609883612969 514229, times , 298610928685279993661, is indeed , 153554399246902845860302369 832040, times , 1662149072277201394907, is indeed , 1382974514097522648618420280 1346269, times , 9253169548548380483401, is indeed , 12457255314954679645007780869 2178309, times , 51507590702129135617317, is indeed , 112199448394764215277422176953 QED! This took, 0.395, seconds.