Numero di Leonardo

I numeri di Leonardo sono una sequenza di numeri dati dalla relazione:

${\displaystyle L(n):={\begin{cases}1&{\mbox{se }n=0;\\1&{\mbox{se }n=1;\\L(n-1)+L(n-2)+1&{\mbox{se }n>1.\\\end{cases}$

Edsger W. Dijkstra^[1] li ha utilizzati come parte integrante del suo algoritmo di ordinamento Smoothsort, analizzandoli anche in alcuni dettagli^[2].

Essi sono legati ai numeri di Fibonacci dalla relazione ${\displaystyle L(n)=2*F(n+1)-1,n\geq 0}$. Data la formula tipo Binet:

${\displaystyle L(n)=2*\left({\frac {\Phi ^{(n+1)}-\phi ^{(n+1)}{\Phi -\phi }\right)-1=\left({\frac {2}{\sqrt {5}\right)*(\Phi ^{(n+1)}-\phi ^{(n+1)})-1}$

dove ${\displaystyle \Phi =(1+{\sqrt {5})/2}$ e ${\displaystyle \phi =(1-{\sqrt {5})/2}$ sono le radici di ${\displaystyle x^{2}-x-1=0}$

I primi numeri di Leonardo sono^[3]:

${\displaystyle 1,\;1,\;3,\;5,\;9,\;15,\;25,\;41,\;67,\;109,\;177,\;287,\;465,\;753,\;1219,\;1973,\;3193,\;5167,\;8361,\ldots }$

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica