Leonardotal

Leonardotal är en heltalsföljd som ges av återkommande:

${\displaystyle L(n)\equiv {\begin{cases}1&{\mbox{if }}n=0\\1&{\mbox{if }}n=1\\L(n-1)+L(n-2)+1&{\mbox{if }}n>1\\\end{cases}}}$

Edsger W. Dijkstra^[1] använde dem som en integrerad del av sin släthetssorterande algoritm,^[2]

Beräkning av andra ordningens återkommande förhållande rekursivt och utan memoisation kräver L(n)-beräkningar för den n:te termen i serien.

De första Leonardotalen är:

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703, 48315633, 78176337, … (talföljd A001595 i OEIS)

Relation till Fibonaccital

Leonardotal är relaterade till Fibonaccital av relationen ${\displaystyle L(n)=2F(n+1)-1,n\geq 0}$.

Ur denna relation är det enkelt att härleda ett uttryck i sluten form för Leonardotal, analogt med Binets formel för Fibonaccital:

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

där det gyllene snittet ${\displaystyle \varphi =\left(1+{\sqrt {5}}\right)/2}$ och ${\displaystyle \psi =\left(1-{\sqrt {5}}\right)/2}$ är rötterna till det kvadratiska polynomet ${\displaystyle x^{2}-x-1=0}$.

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Leonardo number, 22 december 2013.

Externa länkar

• "Sloanes A001595 ", Nätuppslagsverket över heltalsföljder (OEIS) (engelska)