A014217 a(n) = floor(phi^n), where phi = (1+sqrt(5))/2 is the golden ratio.

1, 1, 2, 4, 6, 11, 17, 29, 46, 76, 122, 199, 321, 521, 842, 1364, 2206, 3571, 5777, 9349, 15126, 24476, 39602, 64079, 103681, 167761, 271442, 439204, 710646, 1149851, 1860497, 3010349, 4870846, 7881196, 12752042, 20633239, 33385281, 54018521, 87403802

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy
• nice

Comments

a(n) = floor(lim_{k->oo} Fibonacci(k)/Fibonacci(k-n)). - Jon Perry, Jun 10 2003

For n > 1, a(n) is the maximum element in the continued fraction for A000045(n)*phi. - Benoit Cloitre, Jun 19 2005

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

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

a(n) is the sum of the last summands over all Arndt compositions of n (see the Checa link). - Daniel Checa, Dec 25 2023

a(n) is the number of (saturated or unsaturated) substituted N-heterocycles in chemistry (N = nitrogen). That means the number of matchings in a cycle graph when the two maximum matchings in every cycle with an even number of vertices are indistinguishable (because the corresponding resonance structures in the molecule are equivalent). - Stefan Schuster, Mar 20 2025

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..4784 (first 301 terms from T. D. Noe)
• Mohammad K. Azarian, Problem 123, Missouri Journal of Mathematical Sciences, Vol. 10, No. 3, Fall 1998, p. 176. Solution published in Vol. 12, No. 1, Winter 2000, pp. 61-62.
• Daniel F. Checa, Arndt Compositions: Connections with Fibonacci Numbers, Statistics, and Generalizations, 2023. p. 29.
• Daniel F. Checa and José L. Ramírez, Arndt Compositions: A Generating Functions Approach, Integers (2024) Vol. 24, A35. See p. 14.
• G. Harman, One hundred years of normal numbers
• Kival Ngaokrajang, Illustration for n = 0..7
• Stefan Schuster and Tatjana Malycheva, Enumeration of saturated and unsaturated substituted N-heterocycles, arXiv:2309.02343 [q-bio.BM], 2023.
• Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1).

Crossrefs

Cf. A000032, A000045, A001622, A020956, A022319, A052952, A057146, A062114, A128440, A153382, A169985, A169986, A203976, A226328.

First differences give A181716.

Programs

Haskell

a014217 n = a014217_list !! n
a014217_list = 1 : 1 : zipWith (+)
   a000035_list (zipWith (+) a014217_list $ tail a014217_list)
-- Reinhard Zumkeller, Jan 06 2012

Magma

[Floor( ((1+Sqrt(5))/2)^n ): n in [0..100]]; // Vincenzo Librandi, Apr 16 2011

Maple

A014217 := proc(n)
    option remember;
    if n <= 3 then
        op(n+1,[1,1,2,4]) ;
    else
        procname(n-1)+2*procname(n-2)-procname(n-3)-procname(n-4) ;
    end if;
end proc: # R. J. Mathar, Jun 23 2013
#
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]:
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 12 2017

Mathematica

Table[Floor[GoldenRatio^n], {n, 0, 36}] (* Vladimir Joseph Stephan Orlovsky, Dec 12 2008 *)
LinearRecurrence[{1, 2, -1, -1}, {1, 1, 2, 4}, 40] (* Jean-François Alcover, Nov 05 2017 *)

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

Python

from sympy import floor, sqrt
def A014217(n): return floor(((1+sqrt(5))/2)**n) # Chai Wah Wu, Dec 17 2021

Sage

[floor(golden_ratio^n) for n in range(37)] # Danny Rorabaugh, Apr 19 2015

Formula

a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4).

a(n) = a(n-1) + a(n-2) + (1-(-1)^n)/2 = a(n-1) + a(n-2) + A000035(n).

a(n) = A000032(n) - (1 + (-1)^n)/2. - Mario Catalani (mario.catalani(AT)unito.it), Jan 17 2003

G.f.: (1-x^2+x^3)/((1+x)*(1-x)*(1-x-x^2)). - R. J. Mathar, Sep 06 2008

a(2n-1) = (Fibonacci(4n+1)-2)/Fibonacci(2n+2). - Gary Detlefs, Feb 16 2011

a(n) = floor(Fibonacci(2n+3)/Fibonacci(n+3)). - Gary Detlefs, Feb 28 2011

a(2n) = Fibonacci(2*n-1) + Fibonacci(2*n+1) - 1. - Gary Detlefs, Mar 10 2011

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

a(n) = A052952(n) - A052952(n-2) + A052952(n-3). - R. J. Mathar, Jun 13 2013

a(n+6) - a(n-6) = 40*A000045(n), case k=6 of my formula above. - Paul Curtz, Jun 13 2013

From Paul Curtz, Jun 17 2013: (Start)

a(n-3) + a(n+3) = A153382(n).

a(n-1) + a(n+2) = A022319(n). (End)

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

a(n) = ((-1)^(1+n)-1)/2 + ((1-sqrt(5))/2)^n + ((1+sqrt(5))/2)^n. - Colin Barker, Nov 05 2017

a(n) = floor(2*sinh(n*arccsch(2))). - Federico Provvedi, Feb 23 2022

E.g.f.: 2*exp(x/2)*cosh(sqrt(5)*x/2) - cosh(x). - Stefano Spezia, Jul 26 2022

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

Extensions

Corrected by T. D. Noe, Nov 09 2006

Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar