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

Asymptotics of Lagged Fibonacci Sequences

Stephan Mertens and Stefan Boettcher

---

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}}
}

---

Download:
mertens0912.pdf