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 .