Theorem: Let F(n) be the sequence defined by the recurrence F(n) = 2 a F(n - 1) - F(n - 2) subject to the initial conditions F(0) = 1, F(1) = 2 a Equivalently, the ordinary generating function of F(n) w.r.t. to t is infinity ----- \ n 1 ) F(n) t = -------------- / 2 ----- 1 - 2 a t + t n = 0 Also Let G(n) be the sequence defined by the recurrence G(n) = 2 b G(n - 1) - G(n - 2) subject to the initial conditions G(0) = 1, G(1) = 2 b Equivalently, the ordinary generating function of G(n) w.r.t. to t is infinity ----- \ n 1 ) G(n) t = -------------- / 2 ----- 1 - 2 b t + t n = 0 Let H(n)=F(n)G(n), then infinity ----- 2 \ n 1 - t ) H(n) t = --------------------------------------------------- / 2 2 2 3 4 ----- 1 - 4 a b t - (-4 a + 2 - 4 b ) t - 4 a b t + t n = 0 or equivalently, H(n) is the sequence defined by the recurrence 2 2 H(n) = 4 a b H(n - 1) + (-4 a + 2 - 4 b ) H(n - 2) + 4 a b H(n - 3) - H(n - 4) subject to the initial conditions 2 2 H(0) = 1, H(1) = 4 a b, H(2) = (-1 + 4 a ) (-1 + 4 b ), 3 3 H(3) = (-4 a + 8 a ) (-4 b + 8 b ) 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 2 3 2 4 3 5 [1, 2 a, -1 + 4 a , -4 a + 8 a , -12 a + 16 a + 1, -32 a + 32 a + 6 a, 4 6 2 5 7 3 -80 a + 64 a + 24 a - 1, -192 a + 128 a + 80 a - 8 a] The first, 8, members of the sequence G(n) are 2 3 2 4 3 5 [1, 2 b, -1 + 4 b , -4 b + 8 b , -12 b + 16 b + 1, -32 b + 32 b + 6 b, 4 6 2 5 7 3 -80 b + 64 b + 24 b - 1, -192 b + 128 b + 80 b - 8 b] The first, 8, members of the propsed product are 2 2 2 2 3 3 3 3 [1, 4 a b, 1 - 4 b - 4 a + 16 a b , 16 a b - 32 a b - 32 a b + 64 a b , 2 2 2 4 2 4 2 4 4 4 2 144 a b - 192 a b - 12 a - 192 a b + 256 a b + 16 a - 12 b 4 3 3 3 5 3 5 3 5 5 + 16 b + 1, 1024 a b - 1024 a b - 192 a b - 1024 a b + 1024 a b 5 3 5 4 4 4 6 + 192 a b - 192 a b + 192 a b + 36 a b, 6400 a b - 5120 a b 4 2 4 6 4 6 6 6 2 6 - 1920 a b + 80 a - 5120 a b + 4096 a b + 1536 a b - 64 a 2 4 2 6 2 2 2 4 6 2 - 1920 a b + 1536 a b + 576 a b - 24 a + 80 b - 64 b - 24 b + 1, 5 5 5 7 5 3 5 7 5 36864 a b - 24576 a b - 15360 a b + 1536 a b - 24576 a b 7 7 7 3 7 3 5 3 7 + 16384 a b + 10240 a b - 1024 a b - 15360 a b + 10240 a b 3 3 3 5 7 3 + 6400 a b - 640 a b + 1536 a b - 1024 a b - 640 a b + 64 a b] 1, times , 1, is indeed , 1 2 a, times , 2 b, is indeed , 4 a b 2 2 2 2 2 2 -1 + 4 a , times , -1 + 4 b , is indeed , 1 - 4 b - 4 a + 16 a b 3 3 -4 a + 8 a , times , -4 b + 8 b , is indeed , 3 3 3 3 16 a b - 32 a b - 32 a b + 64 a b 2 4 2 4 2 2 -12 a + 16 a + 1, times , -12 b + 16 b + 1, is indeed , 144 a b 2 4 2 4 2 4 4 4 2 4 - 192 a b - 12 a - 192 a b + 256 a b + 16 a - 12 b + 16 b + 1 3 5 3 5 3 3 -32 a + 32 a + 6 a, times , -32 b + 32 b + 6 b, is indeed , 1024 a b 3 5 3 5 3 5 5 5 3 - 1024 a b - 192 a b - 1024 a b + 1024 a b + 192 a b - 192 a b 5 + 192 a b + 36 a b 4 6 2 4 6 2 -80 a + 64 a + 24 a - 1, times , -80 b + 64 b + 24 b - 1, is indeed , 4 4 4 6 4 2 4 6 4 6 6 6400 a b - 5120 a b - 1920 a b + 80 a - 5120 a b + 4096 a b 6 2 6 2 4 2 6 2 2 2 4 + 1536 a b - 64 a - 1920 a b + 1536 a b + 576 a b - 24 a + 80 b 6 2 - 64 b - 24 b + 1 5 7 3 5 7 3 -192 a + 128 a + 80 a - 8 a, times , -192 b + 128 b + 80 b - 8 b, 5 5 5 7 5 3 5 is indeed , 36864 a b - 24576 a b - 15360 a b + 1536 a b 7 5 7 7 7 3 7 3 5 - 24576 a b + 16384 a b + 10240 a b - 1024 a b - 15360 a b 3 7 3 3 3 5 7 3 + 10240 a b + 6400 a b - 640 a b + 1536 a b - 1024 a b - 640 a b + 64 a b QED! Here is the analogous result for Chebychev polynomials of the first kind Theorem: Let F(n) be the sequence defined by the recurrence F(n) = 2 a F(n - 1) - F(n - 2) subject to the initial conditions F(0) = 1, F(1) = a Equivalently, the ordinary generating function of F(n) w.r.t. to t is infinity ----- \ n 1 - a t ) F(n) t = -------------- / 2 ----- 1 - 2 a t + t n = 0 Also Let G(n) be the sequence defined by the recurrence G(n) = 2 b G(n - 1) - G(n - 2) subject to the initial conditions G(0) = 1, G(1) = b Equivalently, the ordinary generating function of G(n) w.r.t. to t is infinity ----- \ n 1 - b t ) G(n) t = -------------- / 2 ----- 1 - 2 b t + t n = 0 Let H(n)=F(n)G(n), then infinity ----- 2 2 2 3 \ n 1 - 3 a b t + (2 a - 1 + 2 b ) t - a b t ) H(n) t = --------------------------------------------------- / 2 2 2 3 4 ----- 1 - 4 a b t - (-4 a + 2 - 4 b ) t - 4 a b t + t n = 0 or equivalently, H(n) is the sequence defined by the recurrence 2 2 H(n) = 4 a b H(n - 1) + (-4 a + 2 - 4 b ) H(n - 2) + 4 a b H(n - 3) - H(n - 4) subject to the initial conditions 2 2 H(0) = 1, H(1) = a b, H(2) = (-1 + 2 a ) (-1 + 2 b ), 3 3 H(3) = (-3 a + 4 a ) (-3 b + 4 b ) 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 2 3 2 4 3 5 [1, a, -1 + 2 a , -3 a + 4 a , -8 a + 8 a + 1, -20 a + 16 a + 5 a, 4 6 2 5 7 3 -48 a + 32 a + 18 a - 1, -112 a + 64 a + 56 a - 7 a] The first, 8, members of the sequence G(n) are 2 3 2 4 3 5 [1, b, -1 + 2 b , -3 b + 4 b , -8 b + 8 b + 1, -20 b + 16 b + 5 b, 4 6 2 5 7 3 -48 b + 32 b + 18 b - 1, -112 b + 64 b + 56 b - 7 b] The first, 8, members of the propsed product are 2 2 2 2 3 3 3 3 [1, a b, 1 - 2 b - 2 a + 4 a b , 9 a b - 12 a b - 12 a b + 16 a b , 2 2 2 4 2 4 2 4 4 4 2 4 64 a b - 64 a b - 8 a - 64 a b + 64 a b + 8 a - 8 b + 8 b + 1, 3 3 3 5 3 5 3 5 5 5 400 a b - 320 a b - 100 a b - 320 a b + 256 a b + 80 a b 3 5 4 4 4 6 4 2 4 - 100 a b + 80 a b + 25 a b, 2304 a b - 1536 a b - 864 a b + 48 a 6 4 6 6 6 2 6 2 4 2 6 - 1536 a b + 1024 a b + 576 a b - 32 a - 864 a b + 576 a b 2 2 2 4 6 2 5 5 5 7 + 324 a b - 18 a + 48 b - 32 b - 18 b + 1, 12544 a b - 7168 a b 5 3 5 7 5 7 7 7 3 7 - 6272 a b + 784 a b - 7168 a b + 4096 a b + 3584 a b - 448 a b 3 5 3 7 3 3 3 5 7 - 6272 a b + 3584 a b + 3136 a b - 392 a b + 784 a b - 448 a b 3 - 392 a b + 49 a b] 1, times , 1, is indeed , 1 a, times , b, is indeed , a b 2 2 2 2 2 2 -1 + 2 a , times , -1 + 2 b , is indeed , 1 - 2 b - 2 a + 4 a b 3 3 -3 a + 4 a , times , -3 b + 4 b , is indeed , 3 3 3 3 9 a b - 12 a b - 12 a b + 16 a b 2 4 2 4 -8 a + 8 a + 1, times , -8 b + 8 b + 1, is indeed , 2 2 2 4 2 4 2 4 4 4 2 4 64 a b - 64 a b - 8 a - 64 a b + 64 a b + 8 a - 8 b + 8 b + 1 3 5 3 5 3 3 -20 a + 16 a + 5 a, times , -20 b + 16 b + 5 b, is indeed , 400 a b 3 5 3 5 3 5 5 5 3 - 320 a b - 100 a b - 320 a b + 256 a b + 80 a b - 100 a b 5 + 80 a b + 25 a b 4 6 2 4 6 2 -48 a + 32 a + 18 a - 1, times , -48 b + 32 b + 18 b - 1, is indeed , 4 4 4 6 4 2 4 6 4 6 6 2304 a b - 1536 a b - 864 a b + 48 a - 1536 a b + 1024 a b 6 2 6 2 4 2 6 2 2 2 4 + 576 a b - 32 a - 864 a b + 576 a b + 324 a b - 18 a + 48 b 6 2 - 32 b - 18 b + 1 5 7 3 5 7 3 -112 a + 64 a + 56 a - 7 a, times , -112 b + 64 b + 56 b - 7 b, 5 5 5 7 5 3 5 7 5 is indeed , 12544 a b - 7168 a b - 6272 a b + 784 a b - 7168 a b 7 7 7 3 7 3 5 3 7 + 4096 a b + 3584 a b - 448 a b - 6272 a b + 3584 a b 3 3 3 5 7 3 + 3136 a b - 392 a b + 784 a b - 448 a b - 392 a b + 49 a b QED! And here it is for the product of the First kind times the second kind Theorem: Let F(n) be the sequence defined by the recurrence F(n) = 2 a F(n - 1) - F(n - 2) subject to the initial conditions F(0) = 1, F(1) = a Equivalently, the ordinary generating function of F(n) w.r.t. to t is infinity ----- \ n 1 - a t ) F(n) t = -------------- / 2 ----- 1 - 2 a t + t n = 0 Also Let G(n) be the sequence defined by the recurrence G(n) = 2 b G(n - 1) - G(n - 2) subject to the initial conditions G(0) = 1, G(1) = 2 b Equivalently, the ordinary generating function of G(n) w.r.t. to t is infinity ----- \ n 1 ) G(n) t = -------------- / 2 ----- 1 - 2 b t + t n = 0 Let H(n)=F(n)G(n), then infinity ----- 2 2 \ n 1 - 2 a b t + (-1 + 2 a ) t ) H(n) t = --------------------------------------------------- / 2 2 2 3 4 ----- 1 - 4 a b t - (-4 a + 2 - 4 b ) t - 4 a b t + t n = 0 or equivalently, H(n) is the sequence defined by the recurrence 2 2 H(n) = 4 a b H(n - 1) + (-4 a + 2 - 4 b ) H(n - 2) + 4 a b H(n - 3) - H(n - 4) subject to the initial conditions 2 2 H(0) = 1, H(1) = 2 a b, H(2) = (-1 + 2 a ) (-1 + 4 b ), 3 3 H(3) = (-3 a + 4 a ) (-4 b + 8 b ) 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 2 3 2 4 3 5 [1, a, -1 + 2 a , -3 a + 4 a , -8 a + 8 a + 1, -20 a + 16 a + 5 a, 4 6 2 5 7 3 -48 a + 32 a + 18 a - 1, -112 a + 64 a + 56 a - 7 a] The first, 8, members of the sequence G(n) are 2 3 2 4 3 5 [1, 2 b, -1 + 4 b , -4 b + 8 b , -12 b + 16 b + 1, -32 b + 32 b + 6 b, 4 6 2 5 7 3 -80 b + 64 b + 24 b - 1, -192 b + 128 b + 80 b - 8 b] The first, 8, members of the propsed product are 2 2 2 2 3 3 3 3 [1, 2 a b, 1 - 4 b - 2 a + 8 a b , 12 a b - 24 a b - 16 a b + 32 a b , 2 2 2 4 2 4 2 4 4 4 2 4 96 a b - 128 a b - 8 a - 96 a b + 128 a b + 8 a - 12 b + 16 b 3 3 3 5 3 5 3 5 5 5 + 1, 640 a b - 640 a b - 120 a b - 512 a b + 512 a b + 96 a b 3 5 4 4 4 6 4 2 - 160 a b + 160 a b + 30 a b, 3840 a b - 3072 a b - 1152 a b 4 6 4 6 6 6 2 6 2 4 + 48 a - 2560 a b + 2048 a b + 768 a b - 32 a - 1440 a b 2 6 2 2 2 4 6 2 5 5 + 1152 a b + 432 a b - 18 a + 80 b - 64 b - 24 b + 1, 21504 a b 5 7 5 3 5 7 5 7 7 - 14336 a b - 8960 a b + 896 a b - 12288 a b + 8192 a b 7 3 7 3 5 3 7 3 3 3 + 5120 a b - 512 a b - 10752 a b + 7168 a b + 4480 a b - 448 a b 5 7 3 + 1344 a b - 896 a b - 560 a b + 56 a b] 1, times , 1, is indeed , 1 a, times , 2 b, is indeed , 2 a b 2 2 2 2 2 2 -1 + 2 a , times , -1 + 4 b , is indeed , 1 - 4 b - 2 a + 8 a b 3 3 -3 a + 4 a , times , -4 b + 8 b , is indeed , 3 3 3 3 12 a b - 24 a b - 16 a b + 32 a b 2 4 2 4 2 2 2 4 -8 a + 8 a + 1, times , -12 b + 16 b + 1, is indeed , 96 a b - 128 a b 2 4 2 4 4 4 2 4 - 8 a - 96 a b + 128 a b + 8 a - 12 b + 16 b + 1 3 5 3 5 3 3 -20 a + 16 a + 5 a, times , -32 b + 32 b + 6 b, is indeed , 640 a b 3 5 3 5 3 5 5 5 3 - 640 a b - 120 a b - 512 a b + 512 a b + 96 a b - 160 a b 5 + 160 a b + 30 a b 4 6 2 4 6 2 -48 a + 32 a + 18 a - 1, times , -80 b + 64 b + 24 b - 1, is indeed , 4 4 4 6 4 2 4 6 4 6 6 3840 a b - 3072 a b - 1152 a b + 48 a - 2560 a b + 2048 a b 6 2 6 2 4 2 6 2 2 2 4 + 768 a b - 32 a - 1440 a b + 1152 a b + 432 a b - 18 a + 80 b 6 2 - 64 b - 24 b + 1 5 7 3 5 7 3 -112 a + 64 a + 56 a - 7 a, times , -192 b + 128 b + 80 b - 8 b, 5 5 5 7 5 3 5 7 5 is indeed , 21504 a b - 14336 a b - 8960 a b + 896 a b - 12288 a b 7 7 7 3 7 3 5 3 7 + 8192 a b + 5120 a b - 512 a b - 10752 a b + 7168 a b 3 3 3 5 7 3 + 4480 a b - 448 a b + 1344 a b - 896 a b - 560 a b + 56 a b QED! The three theorems and proofs took altogether, 0.953, seconds .