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