Numero di Leonardo

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

$L(n):=\{\begin{array}{cc}1& \text{se }n=0;\\ 1& \text{se }n=1;\\ L(n-1)+L(n-2)+1& \text{se }n>1.\end{array}$

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

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

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

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

I primi numeri di Leonardo sono:

$1,1,3,5,9,15,25,41,67,109,177,287,465,753,1219,1973,3193,5167,8361,\dots$