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

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

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

Dando a fórmula de Binet-like:

${\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}$

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

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

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

Referências

1. EWD797
2. EWD796a