In this notebook we apply the Binomial transform to the Fibonacci numbers in order to substain the main notebook where these numbers are studied in depth.
In [1]:
import sympy
from sympy import *
from sympy.abc import x, n, z, t, k
init_printing() # for nice printing, a-la' TeX
In [2]:
%run "sums.py"
# duplicated code, put it into "sums.py"
def expand_sum_in_eq(eq_term):
lhs, rhs = eq_term.lhs, eq_term.rhs
return Eq(lhs, expand_Sum(rhs))
f = IndexedBase('f')
fibs = {f[i]:fibonacci(i) for i in range(100)}
In [3]:
transforming_matrix = Matrix([
[1,0,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0,0],
[1,1,1,0,0,0,0,0,0],
[-1,0,1,1,0,0,0,0,0],
[1,0,0,1,1,0,0,0,0],
[-1,0,0,0,1,1,0,0,0],
[1,0,0,0,0,1,1,0,0],
[-1,0,0,0,0,0,1,1,0],
[1,0,0,0,0,0,0,1,1]])
transforming_matrix
Out[3]:
In [7]:
transforming_matrix**(-1)
Out[7]:
In [8]:
def gf(t): return t + 1/(1+t)
gf(t).series(n=10)
Out[8]:
In [9]:
def h(t): return t*(1+2*t+t**2)/(1+t+t**2)
(gf(t)*h(t)**2).series(n=10)
Out[9]:
In [7]:
pascal_matrix = Matrix([
[1,0,0,0,0,0,0,0,0],
[1,1,0,0,0,0,0,0,0],
[1,2,1,0,0,0,0,0,0],
[1,3,3,1,0,0,0,0,0],
[1,4,6,4,1,0,0,0,0],
[1,5,10,10,5,1,0,0,0],
[1,6,15,20,15,6,1,0,0],
[1,7,21,35,35,21,7,1,0],
[1,8,28,56,70,56,28,8,1]])
pascal_matrix
Out[7]:
In [11]:
catalan_matrix = Matrix([
[1,0,0,0,0,0,0,0,0],
[1,1,0,0,0,0,0,0,0],
[2,2,1,0,0,0,0,0,0],
[5,5,3,1,0,0,0,0,0],
[14,14,9,4,1,0,0,0,0],
[42,42,28,14,5,1,0,0,0],
[132,132,90,48,20,6,1,0,0],
[429,429,297,165,75,27,7,1,0],
[1430,1430,1001,572,275,110,35,8,1]])
catalan_matrix
Out[11]:
In [12]:
catalan_inverse_matrix = Matrix([
[1,0,0,0,0,0,0,0,0],
[1,0,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0,0],
[0,-1,1,0,0,0,0,0,0],
[0,0,-2,1,0,0,0,0,0],
[0,0,1,-3,1,0,0,0,0],
[0,0,0,3,-4,1,0,0,0],
[0,0,0,-1,6,-5,1,0,0],
[0,0,0,0,-4,10,-6,1,0]])
catalan_inverse_matrix
Out[12]:
In [13]:
odd_transformed_matrix = pascal_matrix * transforming_matrix
odd_transformed_matrix
Out[13]:
In [14]:
transforming_matrix * pascal_matrix
Out[14]:
In [15]:
(catalan_matrix**(-1) )*odd_transformed_matrix
Out[15]:
In [16]:
catalan_inverse_matrix * odd_transformed_matrix
Out[16]:
In [4]:
fib_matrix = Matrix([fibonacci(i) for i in range(9)])
fib_matrix_sym = Matrix([f[i] for i in range(9)])
fib_matrix, fib_matrix_sym
Out[4]:
In [5]:
a = Wild('a')
std_prod = transforming_matrix * fib_matrix
sym_prod = transforming_matrix * fib_matrix_sym
std_prod, sym_prod, sym_prod.subs({f[0]:0}), sym_prod.subs({f[0]:0}).replace(f[a]+f[a+1],f[a+2])
Out[5]:
In [8]:
rhs=pascal_matrix * transforming_matrix * fib_matrix
rhs_sym = pascal_matrix * sym_prod
rhs, rhs_sym
Out[8]:
In [9]:
a_range = range(1,18,2)
lhs=Matrix([fibonacci(i) for i in a_range]) - Matrix([1 for i in range(9)])
lhs_sym=Matrix([f[i] for i in a_range]) - Matrix([1 for i in range(9)])
lhs, lhs_sym
Out[9]:
In [11]:
Eq(lhs,rhs)
Out[11]:
In [10]:
eq_sym = Eq(lhs_sym, rhs_sym)
eq_sym
Out[10]:
In [18]:
f_minus1_vector = Matrix([f[-1] for i in range(9)])
one_plus_eq = eq_sym#.subs(-Integer(1),f[-1])
one_plus_eq = Eq(one_plus_eq.lhs + f_minus1_vector, one_plus_eq.rhs + f_minus1_vector)
one_plus_eq = Eq(one_plus_eq.lhs.subs(f[-1],1), one_plus_eq.rhs)
Eq(one_plus_eq.lhs, one_plus_eq.rhs.subs(fibs))
Out[18]:
In [11]:
fib0_term = f[0]
eq_sym.subs(fib0_term, fibs[fib0_term])
Out[11]:
Since coefficient in the triangle on the rhs are a part of Pascal triangle, namely A104712, the following is a generalization: $$ f_{2n+1} - 1 = \sum_{k=1}^{n}{{{n+1}\choose{k+1}}f_{k}} $$
In [48]:
gen_odd_fibs = Eq(f[2*n+1]-1, Sum(binomial(n+1, k+1)*f[k], (k,1,n)))
Eq(gen_odd_fibs, Sum(binomial(n+1, n-k)*f[k], (k,1,n)))
Out[48]:
In [58]:
expand_sum_in_eq(gen_odd_fibs.subs(n, 8))
Out[58]:
In [26]:
eq_sym.subs(fibs)
Out[26]:
In [27]:
eq_17 = Eq(f[17],f[-1] + rhs_sym[-1])
eq_18_shift = Eq(f[n], f[n-18]+8*f[n-17]+36*f[n-16]+84*f[n-15]+126*f[n-14]+126*f[n-13]+84*f[n-12]+36*f[n-11]+9*f[n-10]+f[n-9])
eq_17, eq_18_shift
Out[27]:
In [28]:
[eq_18_shift.subs(n,i).lhs.subs(fibs) - eq_18_shift.subs(n,i).rhs.subs(fibs) for i in range(18,32)]
Out[28]:
again, fibonacci numbers, A000045.
In [14]:
from itertools import accumulate
to_accumulate = rhs_sym + ones(9,1)*f[-1]
even_rhs = Matrix(list(accumulate(to_accumulate, lambda folded, current_row: Add(folded, current_row) )))
even_lhs = Matrix([f[i] for i in range(2,19,2)])
even_fibs_matrix_eq = Eq(even_lhs, even_rhs)
even_fibs_matrix_eq
Out[14]:
In [30]:
even_transformed_matrix = Matrix([
[1,0,0,0,0,0,0,0,0],
[2,1,0,0,0,0,0,0,0],
[4,4,1,0,0,0,0,0,0],
[7,10,5,1,0,0,0,0,0],
[11,20,15,6,1,0,0,0,0],
[16,35,35,21,7,1,0,0,0],
[22,56,70,56,28,8,1,0,0],
[29,84,126,126,84,36,9,1,0],
[37,120,210,252,210,120,45,10,1]])
even_transformed_matrix
Out[30]:
In [31]:
even_transforming_matrix = (pascal_matrix**(-1))*even_transformed_matrix
even_transforming_matrix
Out[31]:
In [32]:
(catalan_matrix**(-1) )*even_transformed_matrix
Out[32]:
In [33]:
catalan_inverse_matrix * even_transformed_matrix
Out[33]:
In [34]:
even_transforming_matrix * fib_matrix_sym
Out[34]:
In [47]:
even_vector_eq_sym = Eq(even_lhs - Matrix(list(range(1,10))),
pascal_matrix * even_transforming_matrix * fib_matrix_sym)
even_vector_eq_sym
Out[47]:
In [49]:
even_vector_eq_sym.subs(fib0_term, fibs[fib0_term])
Out[49]:
Since coefficient in the triangle on the rhs are a part of Pascal triangle, namely A104713, the following is a generalization: $$ f_{2n} - n = \sum_{k=1}^{n-1}{{{n+1}\choose{k+2}}f_{k}} $$
In [51]:
gen_even_fibs = Eq(f[2*n]-n, Sum(binomial(n+1, k+2)*f[k], (k,1,n-1)))
Eq(gen_even_fibs, Sum(binomial(n+1, n-k-1)*f[k], (k,1,n-1)))
Out[51]:
In [57]:
expand_sum_in_eq(gen_even_fibs.subs(n, 9))
Out[57]:
In [36]:
even_fibs_matrix_eq_minus1_appear = even_fibs_matrix_eq.subs(fibs)
Eq(even_fibs_matrix_eq.lhs, even_fibs_matrix_eq_minus1_appear, evaluate=False)
Out[36]:
summands on the rhs form a known sequence A054452.
In [37]:
list(accumulate([fibonacci(2*i+1)-1 for i in range(21)]))
Out[37]:
In [23]:
def n_gf(t): return t/(1-t)**2
n_gf(t).series(n=20)
Out[23]:
In [24]:
def odd_fib_gf(t): return t**2/((1-t)**2*(1-3*t+t**2))
odd_fib_gf(t).series(n=20)
Out[24]:
In [25]:
composite_odd_fibs_gf = n_gf(t)+odd_fib_gf(t)
composite_odd_fibs_gf.factor(), composite_odd_fibs_gf.series(n=20)
Out[25]:
In [39]:
def odd_integers_gf(t): return ((n_gf(t)+n_gf(-t))/2).simplify()
odd_integers_gf(t).series(n=20)
Out[39]:
In [40]:
# here is the error: we should use the generating function of F(2n+1) instead of F(n) as done here!
def fib_gf(t): return t/(1-t-t**2)
fib_gf(odd_integers_gf(t)).series(n=20)
Out[40]:
In [41]:
def even_fibs_gf(t): return n_gf(t) + fib_gf(t)/(1-t)
even_fibs_gf(t).series(n=10)
Out[41]:
In [42]:
even_fibs_matrix_eq_minus1_appear.subs(f[-1],1)
Out[42]:
In [43]:
eq_17 = Eq(f[n], 8*f[n-17]+29*f[n-16]+84*f[n-15]+126*f[n-14]+126*f[n-13]+84*f[n-12]+36*f[n-11]+9*f[n-10]+f[n-9])
eq_17
Out[43]:
In [44]:
[eq_17.subs(n,i).lhs.subs(fibs) - eq_17.subs(n,i).rhs.subs(fibs) for i in range(17,31)]
Out[44]:
which is known as A022091.
This work by <a xmlns:cc="http://creativecommons.org/ns#" href="https://github.com/massimo-nocentini/" property="cc:attributionName" rel="cc:attributionURL">Massimo Nocentini</a> is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Based on a work at <a xmlns:dct="http://purl.org/dc/terms/" href="https://github.com/massimo-nocentini/recurrences-unfolding" rel="dct:source">https://github.com/massimo-nocentini/recurrences-unfolding</a>.