A Book of Definite Summation Fibonacci Identities
in the style of Curtis Greene and Herbert Wilf
By Shalosh B. Ekhad
------------------------------------------------
Theorem Number, 1
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(2 n - 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2
G(n) = -1/2 F(n + 1) + 1/2 F(n + 1) - 1/2 F(n) + 1/2 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 2
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(3 n - 3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2
G(n) = 1/3 F(n) (-2 + 3 F(n + 1) - 3 F(n) F(n + 1) + 2 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 3
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(3 n - 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 3 2
G(n) = -1/2 F(n + 1) + 1/2 F(n + 1) - 1/2 F(n) F(n + 1) - 1/2 F(n)
2 3
+ 3/2 F(n) F(n + 1) - 1/2 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 4
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(4 n - 4 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3
G(n) = 3/22 - 3/22 F(n + 1) - 9/22 F(n) + 1/11 F(n) F(n + 1)
27 2 2 13 3 4
+ -- F(n) F(n + 1) - -- F(n) F(n + 1) + 3/11 F(n)
22 11
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 5
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(4 n - 3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
G(n) = -1/3 F(n)
3 2 2 3
(3 F(n + 1) - 4 F(n + 1) + 6 F(n) F(n + 1) - 8 F(n) F(n + 1) + 3 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 6
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(4 n - 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 2 3
G(n) = 1/2 - 1/2 F(n + 1) - 1/2 F(n) F(n + 1) + F(n) F(n + 1)
2 2 2 3 4
- 3/2 F(n) F(n + 1) + 7/2 F(n) F(n + 1) - 3 F(n) F(n + 1) + 1/2 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 7
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(5 n - 5 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3
G(n) = -5/2 F(n) F(n + 1) (-F(n + 1) + F(n))
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 8
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(5 n - 4 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2
G(n) = 3/22 F(n + 1) - 3/22 F(n + 1) + 1/22 F(n) - 4/11 F(n) F(n + 1)
2 45 2 3 3 2
- 4/11 F(n) + -- F(n) F(n + 1) - 5/2 F(n) F(n + 1)
22
20 4 15 5
+ -- F(n) F(n + 1) - -- F(n)
11 22
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 9
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(5 n - 3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2
G(n) = -1/3 F(n) (-5 + 4 F(n + 1) - F(n) F(n + 1) + 2 F(n)
2 2 3
- 25 F(n) F(n + 1) + 25 F(n) F(n + 1))
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 10
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(5 n - 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 2 2
G(n) = - 1/2 + 1/2 F(n + 1) + F(n) - 3/2 F(n) F(n + 1) - 7/2 F(n) F(n + 1)
2 3 3 3 2
+ 15/2 F(n) F(n + 1) + 3/2 F(n) F(n + 1) - 5 F(n) F(n + 1)
4 5
+ 5/2 F(n) F(n + 1) - 5/2 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 11
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(6 n - 6 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
136 4 10 5 272 2 3
G(n) = ---- F(n) F(n + 1) - --- F(n) F(n + 1) + --- F(n) F(n + 1)
319 319 319
225 2 4 136 3 2 360 3 3
+ --- F(n) F(n + 1) + --- F(n) F(n + 1) - --- F(n) F(n + 1)
319 319 319
272 4 915 4 2 70 5
- --- F(n) F(n + 1) + --- F(n) F(n + 1) - -- F(n) F(n + 1)
319 319 29
16 16 2 136 2 136 5
- --- F(n + 1) + --- F(n + 1) + --- F(n) - --- F(n)
319 319 319 319
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 12
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(6 n - 5 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 3 5
G(n) = 36 F(n) F(n + 1) + 4 F(n) F(n + 1) - 33 F(n) F(n + 1)
2 4 2 2 6
- 6 F(n) F(n + 1) - F(n) - 29/2 F(n + 1) + 29/2 F(n + 1)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 13
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(6 n - 4 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 3 2 10 2
G(n) = -3/22 F(n + 1) - 1/22 F(n) - 7/22 F(n) F(n + 1) - -- F(n) F(n + 1)
11
2 415 6 195 2 4 65
+ 19 F(n + 1) - --- F(n + 1) + --- F(n) F(n + 1) - -- F(n) F(n + 1)
22 22 11
480 5 510 3 3 23 2
+ --- F(n) F(n + 1) - --- F(n) F(n + 1) + -- F(n)
11 11 22
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 14
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(6 n - 3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 5 2
G(n) = 1/3 F(n) (-5 F(n + 1) + 6 F(n + 1) + 3 F(n) F(n + 1)
4 2 2 3
- 7 F(n) F(n + 1) - 8 F(n) F(n + 1) + 24 F(n) F(n + 1)
3 2 4 3
- 53 F(n) F(n + 1) + 46 F(n) F(n + 1) - 8 F(n) + 2 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 15
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(6 n - 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
4 5 2 3
G(n) = -9 F(n) F(n + 1) + 105 F(n) F(n + 1) - 8 F(n) F(n + 1)
2 4 2 5 6
+ 45/2 F(n) F(n + 1) + 91/2 F(n + 1) + 7/2 F(n + 1) - 45 F(n + 1)
2 3 2 3 3
+ 1/2 F(n) + 5/2 F(n) + 21/2 F(n) F(n + 1) - 110 F(n) F(n + 1)
- 14 F(n) F(n + 1) - 4 F(n + 1)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 16
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\ 2
G(n) = ) F(j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
G(n) = -F(n) (-F(n + 1) + F(n))
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 17
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 2 2 3
G(n) = - 1/2 + 1/2 F(n + 1) - 1/2 F(n) F(n + 1) - F(n) F(n + 1) + 3/2 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 18
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2
G(n) = -F(n) (-F(n + 1) + F(n)) (F(n + 1) - 2 F(n) F(n + 1) + 2 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 19
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(4 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
21 2 3
G(n) = - 3/22 + 3/22 F(n + 1) + 7/22 F(n) - -- F(n) F(n + 1)
22
129 3 2 177 4 31 5
+ --- F(n) F(n + 1) - --- F(n) F(n + 1) + -- F(n)
22 22 11
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 20
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(5 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
5 4 2 3
G(n) = 5/12 F(n) (-12 F(n) + 2 F(n + 1) + F(n) F(n + 1) + 8 F(n) F(n + 1)
3 2 4
- 61 F(n) F(n + 1) + 62 F(n) F(n + 1))
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 21
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(6 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
14512 2 19010 3 4 45734 2
G(n) = ------ F(n) F(n + 1) + ----- F(n) F(n + 1) + ----- F(n) F(n + 1)
319 319 319
16 3 2568 3 16 45620 6
+ --- F(n + 1) + ---- F(n) - --- - ----- F(n) F(n + 1)
319 319 319 319
104955 2 5 112135 4 3
+ ------ F(n) F(n + 1) - ------ F(n) F(n + 1)
319 319
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 22
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(n + j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2
G(n) = 1/2 F(n) (-1 + 3 F(n + 1) - 5 F(n) F(n + 1) + 3 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 23
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(n + 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2 3
G(n) = 1/2 - 1/2 F(n + 1) + 1/2 F(n) + 1/2 F(n) F(n + 1) + 2 F(n) F(n + 1)
4
- 3 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 24
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(n + 3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
G(n) = F(n)
3 2 2 3 4
(1 - 2 F(n) F(n + 1) + 10 F(n) F(n + 1) - 11 F(n) F(n + 1) + 2 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 25
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(n + 4 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
4 5 2 3
G(n) = 1/11 F(n) F(n + 1) + 5/22 F(n) F(n + 1) - 2/11 F(n) F(n + 1)
40 2 4 3 2 20 3 3
+ -- F(n) F(n + 1) - 1/11 F(n) F(n + 1) - -- F(n) F(n + 1)
11 11
4 485 4 2 5
+ 2/11 F(n) F(n + 1) - --- F(n) F(n + 1) + 25 F(n) F(n + 1)
22
2 56 2 5
- 3/22 F(n + 1) + 3/22 F(n + 1) - -- F(n) + 1/11 F(n)
11
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 26
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(n + 5 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 4 6
G(n) = -1/12 F(n) (2 F(n) F(n + 1) + F(n + 1) + 1795 F(n + 1)
3 2 2
+ 562 F(n) F(n + 1) - 2 F(n) F(n + 1) - F(n) F(n + 1)
2 4 2 5
- 835 F(n) F(n + 1) - 1806 F(n + 1) - 4105 F(n) F(n + 1)
3 3 4 2
+ 4485 F(n) F(n + 1) + F(n) - 97 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 27
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(2 n + j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
3 2
G(n) = -1/2 F(n) (2 F(n + 1) - 4 F(n + 1) - F(n) + 9 F(n) F(n + 1)
2 3
- 11 F(n) F(n + 1) + 5 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 28
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(2 n + 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2
G(n) = 1/2 F(n + 1) - 1/2 F(n + 1) - 1/2 F(n) + F(n) F(n + 1) - F(n)
2 3 3 2 4 5
+ 3/2 F(n) F(n + 1) + 3/2 F(n) F(n + 1) - 7 F(n) F(n + 1) + 9/2 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 29
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(2 n + 3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 4 3 3
G(n) = -29 F(n) F(n + 1) + 199 F(n) F(n + 1) + 27 F(n) F(n + 1)
5 2 6 2
- 192 F(n) F(n + 1) - 83 F(n + 1) + 83 F(n + 1) - 5 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 30
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(2 n + 4 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 1003 2
G(n) = -5/22 F(n) + 2/11 F(n) F(n + 1) - ---- F(n) F(n + 1)
22
1165 3 4 181 3 2 3105 6
+ ---- F(n) F(n + 1) + --- F(n) - 3/22 F(n + 1) - ---- F(n) F(n + 1)
22 22 22
3 7195 2 5 3770 4 3
+ 3/22 F(n + 1) + ---- F(n) F(n + 1) - ---- F(n) F(n + 1)
22 11
1554 2
+ ---- F(n) F(n + 1)
11
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 31
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(3 n + j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 3 2
G(n) = 1/2 F(n) (5 - 3 F(n + 1) + 3 F(n) F(n + 1) - 4 F(n) F(n + 1) - 2 F(n)
2 2 3 4
+ 31 F(n) F(n + 1) - 33 F(n) F(n + 1) + 3 F(n) )
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 32
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(3 n + 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
5 3 3 6
G(n) = -185 F(n) F(n + 1) + 170 F(n) F(n + 1) + 155/2 F(n + 1)
2 2 2 2
- 77 F(n + 1) - 13/2 F(n) + 3/2 F(n) F(n + 1) - 3 F(n) F(n + 1)
2 4 3 3
+ 29 F(n) F(n + 1) - 15/2 F(n) F(n + 1) - 1/2 F(n + 1) + 3/2 F(n)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 33
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(3 n + 3 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 4 6 5
G(n) = -F(n) (-80 F(n) F(n + 1) + 160 F(n + 1) - 365 F(n) F(n + 1)
3 3 2 2
+ 405 F(n) F(n + 1) - 8 F(n) - 161 F(n + 1) + 49 F(n) F(n + 1))
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 34
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(4 n + j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 2 2 4 3
G(n) = 9/2 F(n) F(n + 1) - 85/2 F(n) F(n + 1) - 7 F(n) F(n + 1)
3 5 3 3
+ F(n) F(n + 1) + 3/2 - 505/2 F(n) F(n + 1) + 535/2 F(n) F(n + 1)
2 2 6
- 110 F(n + 1) - 13/2 F(n) + 110 F(n + 1) + 71/2 F(n) F(n + 1)
4
- 3/2 F(n + 1)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 35
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(4 n + 2 j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
4 7 2 3
G(n) = 2 F(n + 1) + 705/2 F(n + 1) - 107/2 F(n) F(n + 1) - 3 F(n) F(n + 1)
2 2 2 5 3
- 17/2 F(n) F(n + 1) + 35/2 F(n) F(n + 1) + 11 F(n) F(n + 1)
3 6 3 4
+ 21/2 F(n) - 860 F(n) F(n + 1) + 1465/2 F(n) F(n + 1) - 5/2
3 2
- 352 F(n + 1) + 307/2 F(n) F(n + 1)
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
Theorem Number, 36
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) = 0, F(1) = 1
Equivalently, the ordinary generating function of F(n) w.r.t. to t is
infinity
-----
\ n t
) F(n) t = ----------
/ 2
----- 1 - t - t
n = 0
Also Let G(n) be the sequence defined by
n - 1
-----
\
G(n) = ) F(j) F(5 n + j)
/
-----
j = 0
then we have the following closed-form expression for G(n)
2 4 4 6
G(n) = -1/2 F(n) (-235 F(n) F(n + 1) + 5 F(n) + 420 F(n + 1)
5 3 3 4
- 955 F(n) F(n + 1) + 1085 F(n) F(n + 1) + 5 F(n + 1)
3 2 2 3 2
- 10 F(n) F(n + 1) + 20 F(n) F(n + 1) - 15 F(n) F(n + 1) - 21 F(n)
2
- 427 F(n + 1) + 128 F(n) F(n + 1))
Proof: Both sides are C-finite, so it is enough to check the
first few terms, and this is left to the dear reader.
------------------------------------------------
I hope that you enjoyed, dear reader, these, 36, beautiful and
deep theorems.
This took, 16.975, seconds .