%I #188 May 18 2024 23:43:51
%S 1,1,2,4,6,11,17,29,46,76,122,199,321,521,842,1364,2206,3571,5777,
%T 9349,15126,24476,39602,64079,103681,167761,271442,439204,710646,
%U 1149851,1860497,3010349,4870846,7881196,12752042,20633239,33385281,54018521,87403802
%N a(n) = floor(phi^n), where phi = (1+sqrt(5))/2 is the golden ratio.
%C a(n) = floor(lim_{k->oo} Fibonacci(k)/Fibonacci(k-n)). - _Jon Perry_, Jun 10 2003
%C For n > 1, a(n) is the maximum element in the continued fraction for A000045(n)*phi. - _Benoit Cloitre_, Jun 19 2005
%C a(n) is also the curvature (rounded down) of the circle inscribed in the n-th kite arranged in a spiral, starting with a unit circle, as shown in the illustration in the links section. - _Kival Ngaokrajang_, Aug 29 2013
%C a(n) is the n-th Lucas number (A000032) if n is odd, and a(n) is the n-th Lucas number minus 1 if n is even. (Mario Catalani's formula below expresses this fact.) This is related to the fact that the powers of phi approach the values of the Lucas numbers, the odd powers from above and the even powers from below. - _Geoffrey Caveney_, Apr 18 2014
%C a(n) is the sum of the last summands over all Arndt compositions of n (see the Checa link). - _Daniel Checa_, Dec 25 2023
%H Alois P. Heinz, <a href="/A014217/b014217.txt">Table of n, a(n) for n = 0..4784</a> (first 301 terms from T. D. Noe)
%H Mohammad K. Azarian, <a href="http://www.math-cs.ucmo.edu/~mjms/1998.3/prob.ps">Problem 123</a>, Missouri Journal of Mathematical Sciences, Vol. 10, No. 3, Fall 1998, p. 176. <a href="http://www.math-cs.ucmo.edu/~mjms/2000.1/soln.ps">Solution</a> published in Vol. 12, No. 1, Winter 2000, pp. 61-62.
%H Daniel F. Checa, <a href="https://github.com/dfcheca/Arndt-Compositions">Arndt Compositions: Connections with Fibonacci Numbers, Statistics, and Generalizations</a>, 2023. p. 29.
%H Daniel F. Checa and José L. Ramírez, <a href="http://math.colgate.edu/~integers/y35/y35.pdf">Arndt Compositions: A Generating Functions Approach</a>, Integers (2024) Vol. 24, A35. See p. 14.
%H G. Harman, <a href="http://at.yorku.ca/c/a/d/x/39.htm">One hundred years of normal numbers</a>
%H Kival Ngaokrajang, <a href="/A014217/a014217.pdf">Illustration for n = 0..7</a>
%H Stefan Schuster and Tatjana Malycheva, <a href="https://arxiv.org/abs/2309.02343">Enumeration of saturated and unsaturated substituted N-heterocycles</a>, arXiv:2309.02343 [q-bio.BM], 2023.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,-1).
%F a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4).
%F a(n) = a(n-1) + a(n-2) + (1-(-1)^n)/2 = a(n-1) + a(n-2) + A000035(n).
%F a(n) = A000032(n) - (1 + (-1)^n)/2. - Mario Catalani (mario.catalani(AT)unito.it), Jan 17 2003
%F G.f.: (1-x^2+x^3)/((1+x)*(1-x)*(1-x-x^2)). - _R. J. Mathar_, Sep 06 2008
%F a(2n-1) = (Fibonacci(4n+1)-2)/Fibonacci(2n+2). - _Gary Detlefs_, Feb 16 2011
%F a(n) = floor(Fibonacci(2n+3)/Fibonacci(n+3)). - _Gary Detlefs_, Feb 28 2011
%F a(2n) = Fibonacci(2*n-1) + Fibonacci(2*n+1) - 1. - _Gary Detlefs_, Mar 10 2011
%F a(n+2*k) - a(n) = A203976(k)*A000032(n+k) if k odd, a(n+2*k) - a(n) = A203976(k)*A000045(n+k) if k even, for k > 0. - _Paul Curtz_, Jun 05 2013
%F a(n) = A052952(n) - A052952(n-2) + A052952(n-3). - _R. J. Mathar_, Jun 13 2013
%F a(n+6) - a(n-6) = 40*A000045(n), case k=6 of my formula above. - _Paul Curtz_, Jun 13 2013
%F From _Paul Curtz_, Jun 17 2013: (Start)
%F a(n-3) + a(n+3) = A153382(n).
%F a(n-1) + a(n+2) = A022319(n). (End)
%F For k > 0, a(2k) = A169985(2k)-1 and a(2k+1) = A169985(2k+1) (which is equivalent to Catalani's 2003 formula). - _Danny Rorabaugh_, Apr 15 2015
%F a(n) = ((-1)^(1+n)-1)/2 + ((1-sqrt(5))/2)^n + ((1+sqrt(5))/2)^n. - _Colin Barker_, Nov 05 2017
%F a(n) = floor(2*sinh(n*arccsch(2))). - _Federico Provvedi_, Feb 23 2022
%F E.g.f.: 2*exp(x/2)*cosh(sqrt(5)*x/2) - cosh(x). - _Stefano Spezia_, Jul 26 2022
%F a(n) = floor(Fibonacci(n)*phi) + Fibonacci(n-1) = A074331(n) + A000045(n-1) = A052952(n-1) + A000045(n-1). This is the case k=1 of the formula (also found in A128440): floor(k * phi^n) = floor(Fibonacci(n)*k*phi) + Fibonacci(n-1) * k. - _Chunqing Liu_, Oct 03 2023
%p A014217 := proc(n)
%p option remember;
%p if n <= 3 then
%p op(n+1,[1,1,2,4]) ;
%p else
%p procname(n-1)+2*procname(n-2)-procname(n-3)-procname(n-4) ;
%p end if;
%p end proc: # _R. J. Mathar_, Jun 23 2013
%p #
%p a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|-1|2|1>>^n. <<1, 1, 2, 4>>)[1, 1]:
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Oct 12 2017
%t Table[Floor[GoldenRatio^n], {n, 0, 36}] (* _Vladimir Joseph Stephan Orlovsky_, Dec 12 2008 *)
%t LinearRecurrence[{1, 2, -1, -1}, {1, 1, 2, 4}, 40] (* _Jean-François Alcover_, Nov 05 2017 *)
%o (PARI) my(x='x+O('x^44)); Vec((1-x^2+x^3)/((1+x)*(1-x)*(1-x-x^2))) \\ _Joerg Arndt_, Jul 10 2023
%o (Magma) [Floor( ((1+Sqrt(5))/2)^n ): n in [0..100]]; // _Vincenzo Librandi_, Apr 16 2011
%o (Haskell)
%o a014217 n = a014217_list !! n
%o a014217_list = 1 : 1 : zipWith (+)
%o a000035_list (zipWith (+) a014217_list $ tail a014217_list)
%o -- _Reinhard Zumkeller_, Jan 06 2012
%o (Sage) [floor(golden_ratio^n) for n in range(37)] # _Danny Rorabaugh_, Apr 19 2015
%o (Python)
%o from sympy import floor, sqrt
%o def A014217(n): return floor(((1+sqrt(5))/2)**n) # _Chai Wah Wu_, Dec 17 2021
%Y Cf. A000032, A000045, A001622, A020956, A022319, A052952, A057146, A062114, A128440, A153382, A169985, A169986, A203976, A226328.
%Y First differences give A181716.
%K nonn,easy,nice
%O 0,3
%A _Clark Kimberling_
%E Corrected by _T. D. Noe_, Nov 09 2006
%E Edited by _N. J. A. Sloane_, Aug 29 2008 at the suggestion of _R. J. Mathar_