Leonardo number

The term "Leonardo number" was coined by Dijkstra^{[5][nb 1]}, and the derivation is not given explicitly. Given the close relationship to the famous sequence credited to Leonardo Fibonacci, he may have considered the subject trivial. There is no known nor likely connection to Leonardo da Vinci, the most common subject of that mononym.

The first few Leonardo numbers are

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, ... (sequence A001595 in the OEIS)

The first few Leonardo primes are

3, 5, 41, 67, 109, 1973, 5167, 2692537, 11405773, 126491971, 331160281, 535828591, 279167724889, 145446920496281, 28944668049352441, 5760134388741632239, 63880869269980199809, 167242286979696845953, 597222253637954133837103, ... (sequence A145912 in the OEIS)

The Leonardo numbers form a cycle in any modulo ${\displaystyle n\geq 2}$. An easy way to see it is:

• If a pair of numbers modulo ${\displaystyle n}$ appears twice in the sequence, then there is a cycle.
• If we assume the main statement is false, using the previous statement, then it would imply there are an infinite number of distinct pairs of numbers between ${\displaystyle 0}$ and ${\displaystyle n-1}$, which is false since there are ${\displaystyle n^{2}}$ such pairs.

The cycles for ${\displaystyle n\leq 8}$ are:

The cycle always end on the pair ${\displaystyle (1,n-1)}$, as it is the only pair which can precede the pair ${\displaystyle (1,1)}$.

• The following equation applies:

${\displaystyle L(n)=2L(n-1)-L(n-3)}$

The Leonardo numbers are related to the Fibonacci numbers by the relation ${\displaystyle L(n)=2F(n+1)-1,n\geq 0}$.

From this relation it is straightforward to derive a closed-form expression for the Leonardo numbers, analogous to Binet's formula for the Fibonacci numbers:

${\displaystyle L(n)=2{\frac {\varphi ^{n+1}-\psi ^{n+1}}{\varphi -\psi }}-1={\frac {2}{\sqrt {5}}}\left(\varphi ^{n+1}-\psi ^{n+1}\right)-1=2F(n+1)-1}$

where the golden ratio ${\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2}$ and ${\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2}$ are the roots of the quadratic polynomial ${\displaystyle x^{2}-x-1=0}$.

The Leonardo polynomials ${\displaystyle L_{n}(x)}$ is defined by ^[6]

${\displaystyle L_{n+2}(x)=xL_{n+1}(x)+L_{n}(x)+x}$ with ${\displaystyle L_{0}(x)=1,L_{1}(x)=2x-1.}$

Equivalently, in homogeneous form, the Leonardo polynomials can be writtenas

${\displaystyle L_{n+3}(x)=(x+1)L_{n+2}(x)-(x-1)L_{n+1}(x)-L_{n}(x):}$

where ${\displaystyle L_{0}(x)=1,L_{1}(x)=2x-1}$ and ${\displaystyle L_{2}(x)=2x^{2}+1.}$

${\displaystyle L_{0}(x)=1\,}$

${\displaystyle L_{1}(x)=2x-1\,}$

${\displaystyle L_{2}(x)=2x^{2}+1\,}$

${\displaystyle L_{3}(x)=2x^{3}+4x-1\,}$

${\displaystyle L_{4}(x)=2x^{4}+6x^{2}+1\,}$

${\displaystyle L_{5}(x)=2x^{5}+8x^{3}+6x-1\,}$

${\displaystyle L_{6}(x)=2x^{6}+10x^{4}+12x^{2}+1\,}$

${\displaystyle L_{7}(x)=2x^{7}+12x^{5}+20x^{3}+8x-1\,}$

${\displaystyle L_{8}(x)=2x^{8}+14x^{6}+30x^{4}+20x^{2}+1\,}$

${\displaystyle L_{9}(x)=2x^{9}+16x^{7}+42x^{5}+40x^{3}+10x-1\,}$

${\displaystyle L_{10}(x)=2x^{10}+18x^{8}+56x^{6}+70x^{4}+30x^{2}+1\,}$

${\displaystyle L_{11}(x)=2x^{11}+20x^{9}+72x^{7}+112x^{5}+70x^{3}+12x-1\,}$

Substituting ${\displaystyle x=1}$ in the above polynomials gives the Leonardo numbers and setting ${\displaystyle x=k}$ gives the ${\displaystyle k}$-Leonardo numbers.^[7]