On a family of nested recurrences. (English) Zbl 0547.10009

Downey, Peter J.; Griswold, Ralph E.

Fibonacci Q. 22, 310-317 (1984).

Let k be an integer and let \(g_ k(n)\) be a function defined by \(g_ k(n)=n-g_ k(g_ k(n-k))\) for integers \(n\geq 1\) and \(g_ k(n)=0\) for \(n\leq 0\). The authors give a closed form for the numbers \(g_ k(n)\) proving that \(g_ k(n)=\sum^{k-1}_{i=0}[\psi [(n+i)/k]+\psi],\) where \(\psi =(\sqrt{5}-1)/2\) and [x] denotes the greatest integer function. In case \(k=1\) the following interesting result is proved: The set of positive integers n for which \(g_ 1(n)-g_ 1(n-1)\neq 0\) is given by the set \(B_{\phi}=\{[\phi],[2\phi],...\},\) where \(\phi =\psi +1\).

Reviewer: P.Kiss

MSC:

11B39	Fibonacci and Lucas numbers and polynomials and generalizations
11B37	Recurrences

Keywords:

recursive function; nested recursive definition