%I #49 May 08 2022 13:01:49
%S 0,1,3,34,987,75025,14930352,7778742049,10610209857723,
%T 37889062373143906,354224848179261915075,8670007398507948658051921,
%U 555565404224292694404015791808,93202207781383214849429075266681969,40934782466626840596168752972961528246147
%N (n^2)-th Fibonacci number.
%C 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
%H Seiichi Manyama, <a href="/A054783/b054783.txt">Table of n, a(n) for n = 0..69</a>
%H Jakub Byszewski, Grzegorz Graff and Thomas Ward, <a href="https://londmathsoc.onlinelibrary.wiley.com/doi/full/10.1112/blms.12531">Dold sequences, periodic points, and dynamics</a>, arXiv:2007.04031 [math.DS], 2020-2021; Bull. Lond. Math. Soc. 53 (2021), no. 5, 1263-1298.
%H T. Kotek and J. A. Makowsky, <a href="http://arxiv.org/abs/1309.4020">Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs</a>, arXiv preprint arXiv:1309.4020 [math.CO], 2013.
%H Florian Luca and Tom Ward, <a href="https://arxiv.org/abs/2204.02711">On (almost) realizable subsequences of linearly recurrent sequences</a>, arXiv:2204.02711 [math.NT], 2022.
%H Piotr Miska and Tom Ward, <a href="https://arxiv.org/abs/2102.07561">Stirling numbers and periodic points</a>, arXiv:2102.07561 [math.NT], 2021; Acta Arith. 201 (2021), no. 4, 421-435.
%H Patrick Moss and Tom Ward, <a href="https://arxiv.org/abs/2011.13068">Fibonacci along even powers is (almost) realizable</a>, arXiv:2011.13068 [math.NT], 2020; Fibonacci Quart. 60 (2022), no. 1, 40-47.
%F 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
%p a:= n-> (<<0|1>, <1|1>>^(n^2))[1, 2]:
%p seq(a(n), n=0..15); # _Alois P. Heinz_, Jun 10 2018
%t Table[Fibonacci[n^2], {n, 15}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 08 2012 *)
%o (Magma) [Fibonacci(n^2): n in [0..50]]; // _Vincenzo Librandi_, Apr 09 2011
%o (PARI) a(n)=fibonacci(n^2) \\ _Charles R Greathouse IV_, Oct 07 2016
%Y Cf. (n^k)-th Fibonacci number: A000045 (k=1), this sequence (k=2), A182149 (k=3), A250490 (k=4), A250491 (k=5), A250492 (k=6), A250493 (k=7), A250494 (k=8).
%Y Cf. A081667.
%Y Cf. A341617 shows a similar property for the Stirling numbers of the second kind.
%K nonn
%O 0,3
%A _Jeff Burch_, May 22 2000