Stephan Mertens - Publications Home | Research | Publications | Teaching | Smorgasbord

Asymptotics of Lagged Fibonacci Sequences

Abstract

Consider lagged'' Fibonacci sequences $a(n) = a(n-1)+a(\lfloor n/k\rfloor)$ for $k > 1$. We show that $\lim_{n\to\infty} a(kn)/a(n)\cdot\ln n/n = k\ln k$ and we demonstrate the slow numerical convergence to this limit and how to deal with this slow convergence. We also discuss the connection between two classical results of N.G. de Bruijn and K. Mahler on the asymptotics of $a(n)$.

BiBTeX Entry

@Misc{lagged-fibo
author = {Stephan Mertens and Stefan Boettcher},
title  = {Asymptotics of Lagged Fibonacci Sequences},
year   = {2009},
note   = {\url{http://arXiv.org/abs/0912.2459}}
}