Massimo Nocentini

October 3, 2016: conjectures
September 30, 2016: cleaning, matrix-vector product
September 29, 2016: ordered set-wise spec representation, terms cache subs & project
September 28, 2016: graphical representations, simple unfolding

abstract
In this document we explore the sequence of Fibonacci numbers, from the point of view of recurrence unfolding, an algorithmic/symbolical idea under development. We're going to apply such technique aiming to show new interesting identities among these wonderful numbers. Moreover, we collect in this very document some content directly from the OEIS and some funny graphical interpretations of the defining recurrence.



In [1]:

    
%run "../src/start_session.py"
%run "../src/recurrences.py"
%run "../src/sums.py"



In [2]:

    
from oeis import oeis_search, ListData
import knowledge



In [3]:

    
sys.setrecursionlimit(10000000)

OEIS

We start our study asking the OEIS the sequence of Fibonacci numbers, which is denoted by A000045:



In [3]:

    
s = oeis_search(id=45)
s(data_only=True, data_representation=ListData(upper_limit=20))









    



*





    Out[3]:




Results for query: https://oeis.org/search?fmt=json&q=id%3AA000045&start=0
A000045: Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.

by N. J. A. Sloane, 1964
Keywords: core,nonn,nice,easy,hear,changed
Data:
$$
\begin{array}{c|cccccccccccccccccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\
\hline
A000045(n) & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 & 987 & 1597 & 2584 & 4181
\end{array}
$$

Recurrence

Spec

In this section we define the classic recurrence for the sequence of Fibonacci numbers, using on the lhs subscript that makes sense for all $n\in\mathbb{N}$.



In [145]:

    
with bind(IndexedBase('f'), single=True) as f:
    fibonacci_rec_spec = recurrence_spec(recurrence_eq=Eq(f[n+2],f[n+1]+f[n]), recurrence_symbol=f, variables=[n])



In [7]:

    
fibonacci_rec_spec









    Out[7]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{n + 2} = f_{n} + f_{n + 1} \right\}$
$\Gamma = \left\{\begin{array}{c}\end{array}\right\}$

Unfolding



In [146]:

    
unfolded = fibonacci_rec_spec.unfold(depth=5)



In [147]:

    
unfolded









    Out[147]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{n + 2} = f_{n - 10} + 6 f_{n - 9} + 15 f_{n - 8} + 20 f_{n - 7} + 15 f_{n - 6} + 6 f_{n - 5} + f_{n - 4} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{n - 8} = f_{n - 10} + f_{n - 9}\\f_{n - 7} = f_{n - 9} + f_{n - 8}\\f_{n - 6} = f_{n - 8} + f_{n - 7}\\f_{n - 5} = f_{n - 7} + f_{n - 6}\\f_{n - 4} = f_{n - 6} + f_{n - 5}\\f_{n - 3} = f_{n - 5} + f_{n - 4}\\f_{n - 2} = f_{n - 4} + f_{n - 3}\\f_{n - 1} = f_{n - 3} + f_{n - 2}\\f_{n} = f_{n - 2} + f_{n - 1}\\f_{n + 1} = f_{n} + f_{n - 1}\end{array}\right\}$

Involution



In [148]:

    
unfolded.involute(depth=1)









    Out[148]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{n + 2} = 16 f_{n - 10} + 41 f_{n - 9} + 35 f_{n - 8} + 21 f_{n - 7} + 7 f_{n - 6} + f_{n - 5} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{n - 8} = f_{n - 10} + f_{n - 9}\\f_{n - 7} = f_{n - 9} + f_{n - 8}\\f_{n - 6} = f_{n - 8} + f_{n - 7}\\f_{n - 5} = f_{n - 7} + f_{n - 6}\\f_{n - 4} = f_{n - 6} + f_{n - 5}\\f_{n - 3} = f_{n - 5} + f_{n - 4}\\f_{n - 2} = f_{n - 4} + f_{n - 3}\\f_{n - 1} = f_{n - 3} + f_{n - 2}\\f_{n} = f_{n - 2} + f_{n - 1}\\f_{n + 1} = f_{n} + f_{n - 1}\end{array}\right\}$



In [149]:

    
unfolded.involute()









    Out[149]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{n + 2} = 89 f_{n - 10} + 144 f_{n - 9} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{n - 8} = f_{n - 10} + f_{n - 9}\\f_{n - 7} = f_{n - 9} + f_{n - 8}\\f_{n - 6} = f_{n - 8} + f_{n - 7}\\f_{n - 5} = f_{n - 7} + f_{n - 6}\\f_{n - 4} = f_{n - 6} + f_{n - 5}\\f_{n - 3} = f_{n - 5} + f_{n - 4}\\f_{n - 2} = f_{n - 4} + f_{n - 3}\\f_{n - 1} = f_{n - 3} + f_{n - 2}\\f_{n} = f_{n - 2} + f_{n - 1}\\f_{n + 1} = f_{n} + f_{n - 1}\end{array}\right\}$

Subsuming



In [150]:

    
subsumed=unfolded.subsume()



In [151]:

    
subsumed









    Out[151]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{n + 2} = f_{n - 10} + 6 f_{n - 9} + 15 f_{n - 8} + 20 f_{n - 7} + 15 f_{n - 6} + 6 f_{n - 5} + f_{n - 4} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{n - 8} = f_{n - 10} + f_{n - 9}\\f_{n - 7} = f_{n - 10} + 2 f_{n - 9}\\f_{n - 6} = 2 f_{n - 10} + 3 f_{n - 9}\\f_{n - 5} = 3 f_{n - 10} + 5 f_{n - 9}\\f_{n - 4} = 5 f_{n - 10} + 8 f_{n - 9}\\f_{n - 3} = 8 f_{n - 10} + 13 f_{n - 9}\\f_{n - 2} = 13 f_{n - 10} + 21 f_{n - 9}\\f_{n - 1} = 21 f_{n - 10} + 34 f_{n - 9}\\f_{n} = 34 f_{n - 10} + 55 f_{n - 9}\\f_{n + 1} = 55 f_{n - 10} + 89 f_{n - 9}\end{array}\right\}$

We can abstract the following conjecture: $ f_{n+k-2d+2} = f_{k} f_{n-2d} + f_{k+1} f_{n-2d+1} $, for $k\in\{0,\ldots, 2d-1\}$

Substitution



In [14]:

    
im=knowledge.fibonacci_numbers_inverted_mapping(start=2, limit=20)
im









    Out[14]:





$$\left \{ 1 : f_{2}, \quad 2 : f_{3}, \quad 3 : f_{4}, \quad 5 : f_{5}, \quad 8 : f_{6}, \quad 13 : f_{7}, \quad 21 : f_{8}, \quad 34 : f_{9}, \quad 55 : f_{10}, \quad 89 : f_{11}, \quad 144 : f_{12}, \quad 233 : f_{13}, \quad 377 : f_{14}, \quad 610 : f_{15}, \quad 987 : f_{16}, \quad 1597 : f_{17}, \quad 2584 : f_{18}, \quad 4181 : f_{19}\right \}$$



In [15]:

    
subsumed.subs(im)









    Out[15]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{n + 2} = f_{n - 10} + 6 f_{n - 9} + 15 f_{n - 8} + 20 f_{n - 7} + 15 f_{n - 6} + 6 f_{n - 5} + f_{n - 4} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{n - 8} = f_{n - 10} + f_{n - 9}\\f_{n - 7} = f_{3} f_{n - 9} + f_{n - 10}\\f_{n - 6} = f_{3} f_{n - 10} + f_{4} f_{n - 9}\\f_{n - 5} = f_{4} f_{n - 10} + f_{5} f_{n - 9}\\f_{n - 4} = f_{5} f_{n - 10} + f_{6} f_{n - 9}\\f_{n - 3} = f_{6} f_{n - 10} + f_{7} f_{n - 9}\\f_{n - 2} = f_{7} f_{n - 10} + f_{8} f_{n - 9}\\f_{n - 1} = f_{8} f_{n - 10} + f_{9} f_{n - 9}\\f_{n} = f_{9} f_{n - 10} + f_{10} f_{n - 9}\\f_{n + 1} = f_{10} f_{n - 10} + f_{11} f_{n - 9}\end{array}\right\}$

Instantiation

Raw



In [16]:

    
unfolded.instantiate(strategy=raw(substitutions={n:20}))









    Out[16]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{22} = f_{10} + 6 f_{11} + 15 f_{12} + 20 f_{13} + 15 f_{14} + 6 f_{15} + f_{16} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{12} = f_{10} + f_{11}\\f_{13} = f_{11} + f_{12}\\f_{14} = f_{12} + f_{13}\\f_{15} = f_{13} + f_{14}\\f_{16} = f_{14} + f_{15}\\f_{17} = f_{15} + f_{16}\\f_{18} = f_{16} + f_{17}\\f_{19} = f_{17} + f_{18}\\f_{20} = f_{18} + f_{19}\\f_{21} = f_{19} + f_{20}\end{array}\right\}$

Based



In [17]:

    
instantiated = unfolded.instantiate(strategy=based(arity=unary_indexed()))



In [18]:

    
instantiated









    Out[18]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{12} = f_{0} + 6 f_{1} + 15 f_{2} + 20 f_{3} + 15 f_{4} + 6 f_{5} + f_{6} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{2} = f_{0} + f_{1}\\f_{3} = f_{1} + f_{2}\\f_{4} = f_{2} + f_{3}\\f_{5} = f_{3} + f_{4}\\f_{6} = f_{4} + f_{5}\\f_{7} = f_{5} + f_{6}\\f_{8} = f_{6} + f_{7}\\f_{9} = f_{7} + f_{8}\\f_{10} = f_{8} + f_{9}\\f_{11} = f_{9} + f_{10}\end{array}\right\}$

Computing



In [19]:

    
almost_valued = instantiated.subsume(additional_terms={f[0]:Integer(0), f[1]:Integer(1)})
almost_valued









    Out[19]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{12} = f_{0} + 6 f_{1} + 15 f_{2} + 20 f_{3} + 15 f_{4} + 6 f_{5} + f_{6} \right\}$
$\Gamma = \left\{\begin{array}{c}f_{0} = 0\\f_{1} = 1\\f_{2} = 1\\f_{3} = 2\\f_{4} = 3\\f_{5} = 5\\f_{6} = 8\\f_{7} = 13\\f_{8} = 21\\f_{9} = 34\\f_{10} = 55\\f_{11} = 89\end{array}\right\}$



In [20]:

    
almost_valued.involute()









    Out[20]:




$\left(\Theta, \Gamma\right)_{n}^{f}$ where: 
$\Theta = \left\{ f_{12} = 144 \right\}$
$\Gamma = \left\{\begin{array}{c}f_{0} = 0\\f_{1} = 1\\f_{2} = 1\\f_{3} = 2\\f_{4} = 3\\f_{5} = 5\\f_{6} = 8\\f_{7} = 13\\f_{8} = 21\\f_{9} = 34\\f_{10} = 55\\f_{11} = 89\end{array}\right\}$

Collecting



In [ ]:

    
ipython_latex_description(fibonacci_rec_spec, depths=range(13), arity=unary_indexed())

Spec as symbolic matrix-vector product



In [5]:

    
m, v, r, eqs = fibonacci_rec_spec.matrix_vector_product(depth=10, arity=unary_indexed(), 
                                                        segment=[n-k for k in range(-2, 19)])



In [6]:

    
latex_array_src(eqs)









    Out[6]:





\begin{array}{c} f_{n + 2} = f_{n + 2}\\f_{n + 2} = f_{n} + f_{n + 1}\\f_{n + 2} = f_{n} + f_{n - 2} + 2 f_{n - 1}\\f_{n + 2} = f_{n - 4} + 3 f_{n - 3} + 3 f_{n - 2} + f_{n - 1}\\f_{n + 2} = f_{n - 6} + 4 f_{n - 5} + 6 f_{n - 4} + 4 f_{n - 3} + f_{n - 2}\\f_{n + 2} = f_{n - 8} + 5 f_{n - 7} + 10 f_{n - 6} + 10 f_{n - 5} + 5 f_{n - 4} + f_{n - 3}\\f_{n + 2} = f_{n - 10} + 6 f_{n - 9} + 15 f_{n - 8} + 20 f_{n - 7} + 15 f_{n - 6} + 6 f_{n - 5} + f_{n - 4}\\f_{n + 2} = f_{n - 12} + 7 f_{n - 11} + 21 f_{n - 10} + 35 f_{n - 9} + 35 f_{n - 8} + 21 f_{n - 7} + 7 f_{n - 6} + f_{n - 5}\\f_{n + 2} = f_{n - 14} + 8 f_{n - 13} + 28 f_{n - 12} + 56 f_{n - 11} + 70 f_{n - 10} + 56 f_{n - 9} + 28 f_{n - 8} + 8 f_{n - 7} + f_{n - 6}\\f_{n + 2} = f_{n - 16} + 9 f_{n - 15} + 36 f_{n - 14} + 84 f_{n - 13} + 126 f_{n - 12} + 126 f_{n - 11} + 84 f_{n - 10} + 36 f_{n - 9} + 9 f_{n - 8} + f_{n - 7}\\f_{n + 2} = f_{n - 18} + 10 f_{n - 17} + 45 f_{n - 16} + 120 f_{n - 15} + 210 f_{n - 14} + 252 f_{n - 13} + 210 f_{n - 12} + 120 f_{n - 11} + 45 f_{n - 10} + 10 f_{n - 9} + f_{n - 8} \end{array}



In [7]:

    
m, v, r









    Out[7]:





$$\left ( \left[\begin{array}{ccccccccccccccccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 1 & 5 & 10 & 10 & 5 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1\end{array}\right], \quad \left[\begin{matrix}f_{n + 2}\\f_{n + 1}\\f_{n}\\f_{n - 1}\\f_{n - 2}\\f_{n - 3}\\f_{n - 4}\\f_{n - 5}\\f_{n - 6}\\f_{n - 7}\\f_{n - 8}\\f_{n - 9}\\f_{n - 10}\\f_{n - 11}\\f_{n - 12}\\f_{n - 13}\\f_{n - 14}\\f_{n - 15}\\f_{n - 16}\\f_{n - 17}\\f_{n - 18}\end{matrix}\right], \quad \left[\begin{matrix}f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\\f_{n + 2}\end{matrix}\right]\right )$$



In [8]:

    
example={n:30}
to_check = Eq(m*v.subs(example), r.subs(example))
to_check









    Out[8]:





$$\left[\begin{matrix}f_{32}\\f_{30} + f_{31}\\f_{28} + 2 f_{29} + f_{30}\\f_{26} + 3 f_{27} + 3 f_{28} + f_{29}\\f_{24} + 4 f_{25} + 6 f_{26} + 4 f_{27} + f_{28}\\f_{22} + 5 f_{23} + 10 f_{24} + 10 f_{25} + 5 f_{26} + f_{27}\\f_{20} + 6 f_{21} + 15 f_{22} + 20 f_{23} + 15 f_{24} + 6 f_{25} + f_{26}\\f_{18} + 7 f_{19} + 21 f_{20} + 35 f_{21} + 35 f_{22} + 21 f_{23} + 7 f_{24} + f_{25}\\f_{16} + 8 f_{17} + 28 f_{18} + 56 f_{19} + 70 f_{20} + 56 f_{21} + 28 f_{22} + 8 f_{23} + f_{24}\\f_{14} + 9 f_{15} + 36 f_{16} + 84 f_{17} + 126 f_{18} + 126 f_{19} + 84 f_{20} + 36 f_{21} + 9 f_{22} + f_{23}\\f_{12} + 10 f_{13} + 45 f_{14} + 120 f_{15} + 210 f_{16} + 252 f_{17} + 210 f_{18} + 120 f_{19} + 45 f_{20} + 10 f_{21} + f_{22}\end{matrix}\right] = \left[\begin{matrix}f_{32}\\f_{32}\\f_{32}\\f_{32}\\f_{32}\\f_{32}\\f_{32}\\f_{32}\\f_{32}\\f_{32}\\f_{32}\end{matrix}\right]$$



In [9]:

    
to_check.subs(knowledge.fibonacci_numbers(), simultaneous=True)









    Out[9]:





$$\mathrm{True}$$

Spec as based matrix-vector product



In [10]:

    
m, v, r, eqs = fibonacci_rec_spec.matrix_vector_product(depth=10, arity=unary_indexed(), 
                                                        segment=[Integer(k) for k in range(0, 11)],
                                                        based_instantiation=True)



In [11]:

    
latex_array_src(eqs)









    Out[11]:





\begin{array}{c} f_{0} = f_{0}\\f_{2} = f_{0} + f_{1}\\f_{4} = f_{0} + 2 f_{1} + f_{2}\\f_{6} = f_{0} + 3 f_{1} + 3 f_{2} + f_{3}\\f_{8} = f_{0} + 4 f_{1} + 6 f_{2} + 4 f_{3} + f_{4}\\f_{10} = f_{0} + 5 f_{1} + 10 f_{2} + 10 f_{3} + 5 f_{4} + f_{5}\\f_{12} = f_{0} + 6 f_{1} + 15 f_{2} + 20 f_{3} + 15 f_{4} + 6 f_{5} + f_{6}\\f_{14} = f_{0} + 7 f_{1} + 21 f_{2} + 35 f_{3} + 35 f_{4} + 21 f_{5} + 7 f_{6} + f_{7}\\f_{16} = f_{0} + 8 f_{1} + 28 f_{2} + 56 f_{3} + 70 f_{4} + 56 f_{5} + 28 f_{6} + 8 f_{7} + f_{8}\\f_{18} = f_{0} + 9 f_{1} + 36 f_{2} + 84 f_{3} + 126 f_{4} + 126 f_{5} + 84 f_{6} + 36 f_{7} + 9 f_{8} + f_{9}\\f_{20} = f_{0} + 10 f_{1} + 45 f_{2} + 120 f_{3} + 210 f_{4} + 252 f_{5} + 210 f_{6} + 120 f_{7} + 45 f_{8} + 10 f_{9} + f_{10} \end{array}



In [12]:

    
m,v,r









    Out[12]:





$$\left ( \left[\begin{array}{ccccccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 5 & 10 & 10 & 5 & 1 & 0 & 0 & 0 & 0 & 0\\1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 & 0 & 0\\1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & 0 & 0 & 0\\1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 & 0\\1 & 9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 & 0\\1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1\end{array}\right], \quad \left[\begin{matrix}f_{0}\\f_{1}\\f_{2}\\f_{3}\\f_{4}\\f_{5}\\f_{6}\\f_{7}\\f_{8}\\f_{9}\\f_{10}\end{matrix}\right], \quad \left[\begin{matrix}f_{0}\\f_{2}\\f_{4}\\f_{6}\\f_{8}\\f_{10}\\f_{12}\\f_{14}\\f_{16}\\f_{18}\\f_{20}\end{matrix}\right]\right )$$

Identities and conjectures

Relation with binomial coefficients



In [13]:

    
m = symbols('m')
thm = Eq(f[n], Sum(binomial(m,k)*f[n-2*m+k], (k,0,m)))
thm









    Out[13]:





$$f_{n} = \sum_{k=0}^{m} {\binom{m}{k}} f_{k - 2 m + n}$$

which is known but left as an exercise by Benjamin and Quinn, in the following form:



In [143]:

    
benjamin_quinn_thm = thm.subs({n:n+m})
benjamin_quinn_thm









    Out[143]:





$$f_{m + n} = \sum_{k=0}^{m} {\binom{m}{k}} f_{k - m + n}$$

instantiating $m=n$ we get a closed representation of the matrix-vector product seen before:



In [144]:

    
benjamin_quinn_thm.subs({m:n})









    Out[144]:





$$f_{2 n} = \sum_{k=0}^{n} {\binom{n}{k}} f_{k}$$

A little application of the previous identity is in the following cells:



In [19]:

    
def expand_sum_in_eq(eq_term, in_lhs=False, in_rhs=True):
    lhs, rhs = eq_term.lhs, eq_term.rhs
    return Eq(expand_Sum(lhs) if in_lhs else lhs, expand_Sum(rhs) if in_rhs else rhs)

symbolic expansion of the Sum object:



In [20]:

    
expanded_eq = expand_sum_in_eq(thm.subs({m:20}))
expanded_eq









    Out[20]:





$$f_{n} = f_{n - 40} + 20 f_{n - 39} + 190 f_{n - 38} + 1140 f_{n - 37} + 4845 f_{n - 36} + 15504 f_{n - 35} + 38760 f_{n - 34} + 77520 f_{n - 33} + 125970 f_{n - 32} + 167960 f_{n - 31} + 184756 f_{n - 30} + 167960 f_{n - 29} + 125970 f_{n - 28} + 77520 f_{n - 27} + 38760 f_{n - 26} + 15504 f_{n - 25} + 4845 f_{n - 24} + 1140 f_{n - 23} + 190 f_{n - 22} + 20 f_{n - 21} + f_{n - 20}$$

instantiate to let $f_{0}$ appears in the identity (our concept of based instantiation):



In [21]:

    
subsed = expanded_eq.subs(n, 40)
subsed









    Out[21]:





$$f_{40} = f_{0} + 20 f_{1} + 190 f_{2} + 1140 f_{3} + 4845 f_{4} + 15504 f_{5} + 38760 f_{6} + 77520 f_{7} + 125970 f_{8} + 167960 f_{9} + 184756 f_{10} + 167960 f_{11} + 125970 f_{12} + 77520 f_{13} + 38760 f_{14} + 15504 f_{15} + 4845 f_{16} + 1140 f_{17} + 190 f_{18} + 20 f_{19} + f_{20}$$

finally, check the consistency using the sequence of Fibonacci numbers:



In [22]:

    
subsed.subs(knowledge.fibonacci_numbers())









    Out[22]:





$$\mathrm{True}$$

Looking at bottom left to top right diagonal sums

Another well known recurrence about those numbers involving Pascal triangle is the following: $$ f_{n+1} = \sum_{k\geq 0}{{{n-k}\choose{k}}}$$ namely, a fibonacci number equals the sum in diagonals. Here we do something similar...



In [23]:

    
fibs = knowledge.fibonacci_numbers()

we build the sum for each diagonal, manually: it is ugly, so we hope to refactor it and introduce a function to do so:



In [26]:

    
f2_diag = f[0]
f4_diag = f[0]+f[1]
f6_diag = f[0]+2*f[1]
f8_diag = f[0]+3*f[1]+f[2]
f10_diag = f[0]+4*f[1]+3*f[2]
f12_diag = f[0]+5*f[1]+6*f[2]+f[3]
f14_diag = f[0]+6*f[1]+10*f[2]+4*f[3]
f16_diag = f[0]+7*f[1]+15*f[2]+10*f[3]+f[4]
f18_diag = f[0]+8*f[1]+21*f[2]+20*f[3]+5*f[4]
f20_diag = f[0]+9*f[1]+28*f[2]+35*f[3]+15*f[4]+f[5]
f22_diag = f[0]+10*f[1]+36*f[2]+56*f[3]+35*f[4]+6*f[5]
f24_diag = f[0]+11*f[1]+45*f[2]+84*f[3]+70*f[4]+21*f[5]+f[6]
f26_diag = f[0]+12*f[1]+55*f[2]+120*f[3]+126*f[4]+56*f[5]+7*f[6]

diagonals = [Eq(f2_diag, f2_diag.subs(fibs)),
             Eq(f4_diag, f4_diag.subs(fibs)),
             Eq(f6_diag, f6_diag.subs(fibs)),
             Eq(f8_diag, f8_diag.subs(fibs)),
             Eq(f10_diag, f10_diag.subs(fibs)),
             Eq(f12_diag, f12_diag.subs(fibs)),
             Eq(f14_diag, f14_diag.subs(fibs)),
             Eq(f16_diag, f16_diag.subs(fibs)),
             Eq(f18_diag, f18_diag.subs(fibs)),
             Eq(f20_diag, f20_diag.subs(fibs)),
             Eq(f22_diag, f22_diag.subs(fibs)),
             Eq(f24_diag, f24_diag.subs(fibs)),
             Eq(f26_diag, f26_diag.subs(fibs))]

latex_array_src(diagonals)









    Out[26]:





\begin{array}{c} f_{0} = 0\\f_{0} + f_{1} = 1\\f_{0} + 2 f_{1} = 2\\f_{0} + 3 f_{1} + f_{2} = 4\\f_{0} + 4 f_{1} + 3 f_{2} = 7\\f_{0} + 5 f_{1} + 6 f_{2} + f_{3} = 13\\f_{0} + 6 f_{1} + 10 f_{2} + 4 f_{3} = 24\\f_{0} + 7 f_{1} + 15 f_{2} + 10 f_{3} + f_{4} = 45\\f_{0} + 8 f_{1} + 21 f_{2} + 20 f_{3} + 5 f_{4} = 84\\f_{0} + 9 f_{1} + 28 f_{2} + 35 f_{3} + 15 f_{4} + f_{5} = 157\\f_{0} + 10 f_{1} + 36 f_{2} + 56 f_{3} + 35 f_{4} + 6 f_{5} = 293\\f_{0} + 11 f_{1} + 45 f_{2} + 84 f_{3} + 70 f_{4} + 21 f_{5} + f_{6} = 547\\f_{0} + 12 f_{1} + 55 f_{2} + 120 f_{3} + 126 f_{4} + 56 f_{5} + 7 f_{6} = 1021 \end{array}

looking at the sequence composed by coeffients in the rhs of each equation we recognize A059633. According to the reference, the sequence is built by the following recurrence: $a_{n} = 2a_{n-1}-a_{n-3}+a_{n-4}$, as the following expansion confirms:



In [27]:

    
def A059633_gf(x): 
    return 1/(1-2*x+x**3-x**4)

A059633_gf(t).series(t,n=14)









    Out[27]:





$$1 + 2 t + 4 t^{2} + 7 t^{3} + 13 t^{4} + 24 t^{5} + 45 t^{6} + 84 t^{7} + 157 t^{8} + 293 t^{9} + 547 t^{10} + 1021 t^{11} + 1906 t^{12} + 3558 t^{13} + \mathcal{O}\left(t^{14}\right)$$

therefore we can conjecture the following identity: $$ \sum_{k\geq 0}{{{n-k}\choose{k}}}f_{k} = [t^{n}]\frac{t}{1-2t+t^{3}-t^{4}}$$

Matrix characterization of $f_{2n+1}, \forall n \in\mathbb{N}$



In [28]:

    
def do_memberwise_on_eqs(an_eq, another_eq, operator=lambda x, y: Add(x,y,evaluate=True)):
    return Eq(operator(an_eq.lhs, another_eq.lhs), operator(an_eq.rhs, another_eq.rhs))

def swap_eq(eq_term): return Eq(eq_term.rhs, eq_term.lhs)



In [29]:

    
reduce(do_memberwise_on_eqs, eqs)









    Out[29]:





$$f_{0} + f_{2} + f_{4} + f_{6} + f_{8} + f_{10} + f_{12} + f_{14} + f_{16} + f_{18} + f_{20} = 11 f_{0} + 55 f_{1} + 165 f_{2} + 330 f_{3} + 462 f_{4} + 462 f_{5} + 330 f_{6} + 165 f_{7} + 55 f_{8} + 11 f_{9} + f_{10}$$



In [32]:

    
even_subscript_fibonacci_eq = Eq(f[2*n+1]-1, Sum(f[2*k],(k,0,n)))
even_subscript_fibonacci_eq









    Out[32]:





$$f_{2 n + 1} - 1 = \sum_{k=0}^{n} f_{2 k}$$



In [65]:

    
example = even_subscript_fibonacci_eq.subs(n,21)
example_expanded = expand_sum_in_eq(example)
example_expanded, example_expanded.subs(fibs)









    Out[65]:





$$\left ( f_{43} - 1 = f_{0} + f_{2} + f_{4} + f_{6} + f_{8} + f_{10} + f_{12} + f_{14} + f_{16} + f_{18} + f_{20} + f_{22} + f_{24} + f_{26} + f_{28} + f_{30} + f_{32} + f_{34} + f_{36} + f_{38} + f_{40} + f_{42}, \quad \mathrm{True}\right )$$



In [123]:

    
from itertools import accumulate

enum_range = range(0,50,2)

def worker(accumulated_pair, current_pair):
    index, current = current_pair
    _, accumulated = accumulated_pair
    
    summed_eq = do_memberwise_on_eqs(accumulated, current)
    
    return index, summed_eq

def subs_fib_thm(pair):
    index, current_eq = pair
    expanded_thm = expand_sum_in_eq(even_subscript_fibonacci_eq.subs({n:Integer(index)/2}))
    return index, current_eq, expanded_thm

#def eq_to_subs_dict(eq_term): return {eq_term.lhs:eq_term.rhs}

def apply_subs_on_lhs(triple):
    index, current_eq, thm = triple
    return current_eq.subs({thm.rhs:thm.lhs})

def latex_array_env_of_eqs(mapped):
    from string import Template
    template = Template(r"""\begin{array}{c}$content\end{array}""")
    return template.substitute(content="\n".join(mapped))



In [131]:

    
triangle = accumulate(zip(enum_range, eqs), worker)



In [132]:

    
triangle = map(subs_fib_thm, triangle)



In [133]:

    
triangle = list(map(apply_subs_on_lhs, triangle))
triangle[0] = Eq(f[1]-1,f[0])



In [134]:

    
latex_array_src(triangle)









    Out[134]:





\begin{array}{c} f_{1} - 1 = f_{0}\\f_{3} - 1 = 2 f_{0} + f_{1}\\f_{5} - 1 = 3 f_{0} + 3 f_{1} + f_{2}\\f_{7} - 1 = 4 f_{0} + 6 f_{1} + 4 f_{2} + f_{3}\\f_{9} - 1 = 5 f_{0} + 10 f_{1} + 10 f_{2} + 5 f_{3} + f_{4}\\f_{11} - 1 = 6 f_{0} + 15 f_{1} + 20 f_{2} + 15 f_{3} + 6 f_{4} + f_{5}\\f_{13} - 1 = 7 f_{0} + 21 f_{1} + 35 f_{2} + 35 f_{3} + 21 f_{4} + 7 f_{5} + f_{6}\\f_{15} - 1 = 8 f_{0} + 28 f_{1} + 56 f_{2} + 70 f_{3} + 56 f_{4} + 28 f_{5} + 8 f_{6} + f_{7}\\f_{17} - 1 = 9 f_{0} + 36 f_{1} + 84 f_{2} + 126 f_{3} + 126 f_{4} + 84 f_{5} + 36 f_{6} + 9 f_{7} + f_{8}\\f_{19} - 1 = 10 f_{0} + 45 f_{1} + 120 f_{2} + 210 f_{3} + 252 f_{4} + 210 f_{5} + 120 f_{6} + 45 f_{7} + 10 f_{8} + f_{9}\\f_{21} - 1 = 11 f_{0} + 55 f_{1} + 165 f_{2} + 330 f_{3} + 462 f_{4} + 462 f_{5} + 330 f_{6} + 165 f_{7} + 55 f_{8} + 11 f_{9} + f_{10} \end{array}



In [135]:

    
all(map(lambda eq: eq.subs(fibs), triangle))









    Out[135]:





True



In [136]:

    
to_matrix_notation(triangle, f , range(0, 11))









    Out[136]:





$$\left ( \left[\begin{array}{ccccccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\4 & 6 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\5 & 10 & 10 & 5 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 & 0 & 0 & 0\\7 & 21 & 35 & 35 & 21 & 7 & 1 & 0 & 0 & 0 & 0\\8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 & 0 & 0\\9 & 36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 & 0 & 0\\10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 & 0\\11 & 55 & 165 & 330 & 462 & 462 & 330 & 165 & 55 & 11 & 1\end{array}\right], \quad \left[\begin{matrix}f_{0}\\f_{1}\\f_{2}\\f_{3}\\f_{4}\\f_{5}\\f_{6}\\f_{7}\\f_{8}\\f_{9}\\f_{10}\end{matrix}\right], \quad \left[\begin{matrix}f_{1} - 1\\f_{3} - 1\\f_{5} - 1\\f_{7} - 1\\f_{9} - 1\\f_{11} - 1\\f_{13} - 1\\f_{15} - 1\\f_{17} - 1\\f_{19} - 1\\f_{21} - 1\end{matrix}\right]\right )$$



In [137]:

    
triangle = [eq.subs({f[0]:fibs[f[0]]}, simultaneous=True) for eq in triangle[1:]]
latex_array_src(triangle)









    Out[137]:





\begin{array}{c} f_{3} - 1 = f_{1}\\f_{5} - 1 = 3 f_{1} + f_{2}\\f_{7} - 1 = 6 f_{1} + 4 f_{2} + f_{3}\\f_{9} - 1 = 10 f_{1} + 10 f_{2} + 5 f_{3} + f_{4}\\f_{11} - 1 = 15 f_{1} + 20 f_{2} + 15 f_{3} + 6 f_{4} + f_{5}\\f_{13} - 1 = 21 f_{1} + 35 f_{2} + 35 f_{3} + 21 f_{4} + 7 f_{5} + f_{6}\\f_{15} - 1 = 28 f_{1} + 56 f_{2} + 70 f_{3} + 56 f_{4} + 28 f_{5} + 8 f_{6} + f_{7}\\f_{17} - 1 = 36 f_{1} + 84 f_{2} + 126 f_{3} + 126 f_{4} + 84 f_{5} + 36 f_{6} + 9 f_{7} + f_{8}\\f_{19} - 1 = 45 f_{1} + 120 f_{2} + 210 f_{3} + 252 f_{4} + 210 f_{5} + 120 f_{6} + 45 f_{7} + 10 f_{8} + f_{9}\\f_{21} - 1 = 55 f_{1} + 165 f_{2} + 330 f_{3} + 462 f_{4} + 462 f_{5} + 330 f_{6} + 165 f_{7} + 55 f_{8} + 11 f_{9} + f_{10} \end{array}



In [139]:

    
to_matrix_notation(triangle, f, range(1,11))









    Out[139]:





$$\left ( \left[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\6 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\10 & 10 & 5 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\15 & 20 & 15 & 6 & 1 & 0 & 0 & 0 & 0 & 0\\21 & 35 & 35 & 21 & 7 & 1 & 0 & 0 & 0 & 0\\28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 & 0 & 0\\36 & 84 & 126 & 126 & 84 & 36 & 9 & 1 & 0 & 0\\45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 & 0\\55 & 165 & 330 & 462 & 462 & 330 & 165 & 55 & 11 & 1\end{matrix}\right], \quad \left[\begin{matrix}f_{1}\\f_{2}\\f_{3}\\f_{4}\\f_{5}\\f_{6}\\f_{7}\\f_{8}\\f_{9}\\f_{10}\end{matrix}\right], \quad \left[\begin{matrix}f_{3} - 1\\f_{5} - 1\\f_{7} - 1\\f_{9} - 1\\f_{11} - 1\\f_{13} - 1\\f_{15} - 1\\f_{17} - 1\\f_{19} - 1\\f_{21} - 1\end{matrix}\right]\right )$$

which is the sequence A153861. Some details about the undergoing Binomial transform are described in this companion notebook.

Graphical representations

The following quoted content is kept from a page in the OEIS.

Figure drawn by Henry Bottomley, July 27 2000. If turned sideways (so that the red node at the left is at the bottom), this may be regarded as the Fibonacci Tree, which grows according to the rules that:

every red node turns blue after a year

every blue node produces one blue node and one red node after a year

initially there is a single red node

At the $n$th year there are $F_n$ nodes.

Here is a different representation of the same tree, also from the same source:

This grows according to the rules that every mature branch sprouts a new branch at the end of each year, and new branches take a year to reach maturity.Mature branches are indicated by heavy lines. At the end of the nth year there are $F_n$ branches:

Another version of the Fibonacci tree can be constructed as follows:

Start with a node labeled 0. From any given node, draw branches extending up from it labeled $n+1$ and $2n$. In this way every node is labeled with a unique nonnegative integer, and every nonnegative integer appears exactly once. This is the "state diagram" for the process "if $n$ is even divide by 2, if $n$ is odd subtract 1".

Another funny image, taken from a italian book for children, is the following:

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.