OFFSET
0,2
COMMENTS
Phi = (1+sqrt(5))/2, see A001622.
a(n) is the number of subsets of {1,2,...,n} with no two consecutive elements where n and 1 are considered to be consecutive. - Geoffrey Critzer, Sep 23 2013
Equals the Lucas sequence beginning at 1 (A000204) with 2 inserted between 1 and 3.
The Lucas sequence beginning at 2 (A000032) can be written as L(n) = phi^n + (-1/phi)^n. Since |(-1/phi)^n|<1/2 for n>1, this sequence is {L(n)} (with the first two terms switched). As a consequence, for n>1: a(n) is obtained by rounding phi^n up for even n and down for odd n; a(n) is also the nearest integer to 1/|phi^n - a(n)|. - Danny Rorabaugh, Apr 15 2015
LINKS
Danny Rorabaugh, Table of n, a(n) for n = 0..4000
John Machacek and George D. Nasr, Transversal and Paving Positroids, arXiv:2401.02053 [math.CO], 2024. See p. 23.
Shaoxiong (Steven) Yuan, Generalized Identities of Certain Continued Fractions, arXiv:1907.12459 [math.NT], 2019.
Index entries for linear recurrences with constant coefficients, signature (1,1).
FORMULA
O.g.f.: (1 + x - x^3)/(1 - x - x^2). - Geoffrey Critzer, Sep 23 2013
a(n) = round(sqrt(F(2n) + 2*F(2n-1))), for n >= 0, allowing F(-1) = 1. Also phi^n -> sqrt(F(2n) + 2*F(2n-1)), within < 0.02% by n = 4, therefore converging rapidly. - Richard R. Forberg, Jun 23 2014
For n > 1, a(n) = A001610(n - 1) + 1. - Gus Wiseman, Feb 12 2019
a(n) = A000032(n) for n>=2. - G. C. Greubel, Jul 09 2019
EXAMPLE
a(4) = 7 because we have: {}, {1}, {2}, {3}, {4}, {1,3}, {2,4}. - Geoffrey Critzer, Sep 23 2013
MATHEMATICA
nn=34; CoefficientList[Series[(1+x-x^3)/(1-x-x^2), {x, 0, nn}], x] (* Geoffrey Critzer, Sep 23 2013 *)
Round[GoldenRatio^Range[0, 40]] (* Harvey P. Dale, Jul 13 2014 *)
Table[If[n<=1, n+1, LucasL[n]], {n, 0, 40}] (* G. C. Greubel, Jul 09 2019 *)
PROG
(Magma) [Round(Sqrt(Fibonacci(2*n) + 2*Fibonacci(2*n-1))): n in [0..40]]; // Vincenzo Librandi, Apr 16 2015
(Sage) [round(golden_ratio^n) for n in range(40)] # Danny Rorabaugh, Apr 16 2015
(PARI) my(x='x+O('x^40)); Vec((1+x-x^3)/(1-x-x^2)) \\ G. C. Greubel, Feb 13 2019
(GAP) Concatenation([1, 2], List([2..40], n-> Lucas(1, -1, n)[2] )); # G. C. Greubel, Jul 09 2019
(Python)
from gmpy2 import isqrt, fib2
def A169985(n): return int((m:=isqrt(k:=(lambda x:(x[1]<<1)+x[0])(fib2(n<<1))))+(k-m*(m+1)>=1)) # Chai Wah Wu, Jun 19 2024
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Sep 26 2010
STATUS
approved