OFFSET
0,3
COMMENTS
The sequence (5*a(n+1))_{n>=1} = (5, 15, 170, 4935, ...) is realizable in the sense that there is a self-map on a set T:X->X with the property that a(n) = #{x in X:T^nx=x} for all n >= 1. This is the simplest illustrative example of two different phenomena. The Fibonacci sequence sampled along an odd power cannot be made realizable after multiplication by a constant; the Fibonacci sequence sampled along an even power becomes realizable after multiplication by 5 (the discriminant of the sequence). This is now known to be an instance of a more general phenomenon in the following sense. If (a(n)) is a linear recurrence sequence whose characteristic polynomial F has simple zeros then the sequence (Ma(n^s)) satisfies the Dold congruence, where M=|discriminant(F)| and s is an integer multiple of the exponent of the Galois group of the splitting field of F over the rationals. Under an additional hypothesis on the signs of the coefficients of F, the sequence (Ma(n^s)) is realizable. - Thomas Ward, May 06 2022
LINKS
Seiichi Manyama, Table of n, a(n) for n = 0..69
Jakub Byszewski, Grzegorz Graff and Thomas Ward, Dold sequences, periodic points, and dynamics, arXiv:2007.04031 [math.DS], 2020-2021; Bull. Lond. Math. Soc. 53 (2021), no. 5, 1263-1298.
T. Kotek and J. A. Makowsky, Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs, arXiv preprint arXiv:1309.4020 [math.CO], 2013.
Florian Luca and Tom Ward, On (almost) realizable subsequences of linearly recurrent sequences, arXiv:2204.02711 [math.NT], 2022.
Piotr Miska and Tom Ward, Stirling numbers and periodic points, arXiv:2102.07561 [math.NT], 2021; Acta Arith. 201 (2021), no. 4, 421-435.
Patrick Moss and Tom Ward, Fibonacci along even powers is (almost) realizable, arXiv:2011.13068 [math.NT], 2020; Fibonacci Quart. 60 (2022), no. 1, 40-47.
FORMULA
a(n) = Sum_{k=1..T(n-1)+1} binomial(T(n-1), k-1)*F(n-1+k), where F(n) is A000045 and T(n) is A000217. - Tony Foster III, Sep 03 2018
MAPLE
a:= n-> (<<0|1>, <1|1>>^(n^2))[1, 2]:
seq(a(n), n=0..15); # Alois P. Heinz, Jun 10 2018
MATHEMATICA
Table[Fibonacci[n^2], {n, 15}] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)
PROG
(Magma) [Fibonacci(n^2): n in [0..50]]; // Vincenzo Librandi, Apr 09 2011
(PARI) a(n)=fibonacci(n^2) \\ Charles R Greathouse IV, Oct 07 2016
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeff Burch, May 22 2000
STATUS
approved