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 abaixo:

$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 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{\Phi^{(n+1)} - \phi^{(n+1)}}{\Phi - \phi} \right) - 1 = \left( \frac{2}{\sqrt 5} \right) * (\Phi^{(n+1)} - \phi^{(n+1)}) - 1$

onde $\Phi=(1+\sqrt 5)/2$ e $\phi=(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, \ldots$