Números de Leonardo

Na matemática, os números de Leonardo são uma sequência (sucessão, em Portugal) definida como recursiva pela fórmula

$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 usou-os como parte integrante de seu algoritmo de ordenação smoothsort, e também os analisou em detalhe.

Eles estão relacionados com os números de Fibonacci pela relação $L(n)=2*F(n+1)-1,n\ge 0$.

Dando a fórmula de Binet-like:

$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$

onde $\mathrm{\Phi }=(1+\sqrt{5})/2$ e $\varphi =(1-\sqrt{5})/2$ são as raízes de $x^2-x-1=0$.

Os números iniciais da série de Leonardo são

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

Predefinição:Classes de números naturais