|
%I M0764 N0291 #163 Feb 08 2024 01:33:50
%S 0,2,3,6,10,17,28,46,75,122,198,321,520,842,1363,2206,3570,5777,9348,
%T 15126,24475,39602,64078,103681,167760,271442,439203,710646,1149850,
%U 1860497,3010348,4870846,7881195,12752042,20633238,33385281,54018520
%N a(n) = a(n-1) + a(n-2) + 1, with a(0) = 0 and a(1) = 2.
%C For prime p, p divides a(p-1). - _T. D. Noe_, Apr 11 2009 [This result follows immediately from the fact that A032190(n) = (1/n)*Sum_{d|n} a(d-1)*phi(n/d). - _Petros Hadjicostas_, Sep 11 2017]
%C Generalization. If a(0,x)=0, a(1,x)=2 and, for n>=2, a(n,x)=a(n-1,x)+x*a(n-2,x)+1, then we obtain a sequence of polynomials Q_n(x)=a(n,x) of degree floor((n-1)/2), such that p is prime iff all coefficients of Q_(p-1)(x) are multiple of p (sf. A174625). Thus a(n) is the sum of coefficients of Q_(n-1)(x). - _Vladimir Shevelev_, Apr 23 2010
%C Odd composite numbers n such that n divides a(n-1) are in A005845. - _Zak Seidov_, May 04 2010; comment edited by _N. J. A. Sloane_, Aug 10 2010
%C a(n) is the number of ways to modify a circular arrangement of n objects by swapping one or more adjacent pairs. E.g., for 1234, new arrangements are 2134, 2143, 1324, 4321, 1243, 4231 (taking 4 and 1 to be adjacent) and a(4) = 6. - _Toby Gottfried_, Aug 21 2011
%C For n>2, a(n) equals the number of Markov equivalence classes with skeleton the cycle on n+1 nodes. See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - _Liam Solus_, Aug 23 2018
%C From _Gus Wiseman_, Feb 12 2019: (Start)
%C For n > 0, also the number of nonempty subsets of {1, ..., n + 1} containing no two cyclically successive elements (cyclically successive means 1 succeeds n + 1). For example, the a(5) = 17 stable subsets are:
%C {1}, {2}, {3}, {4}, {5}, {6},
%C {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},
%C {1,3,5}, {2,4,6}.
%C (End)
%C Also the rank of the n-Lucas cube graph. - _Eric W. Weisstein_, Aug 01 2023
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001610/b001610.txt">Table of n, a(n) for n = 0..500</a>
%H Daniel Birmajer, Juan B. Gil, Michael D. Weiner, <a href="http://arxiv.org/abs/1505.06339">Linear recurrence sequences with indices in arithmetic progression and their sums</a>, arXiv:1505.06339 [math.NT], 2015.
%H N-N. Cao, F-Z. Zhao, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Cao2/cao5r.html">Some Properties of Hyperfibonacci and Hyperlucas Numbers</a>, J. Int. Seq. 13 (2010) # 10.8.8.
%H Ligia L. Cristea, Ivica Martinjak, and Igor Urbiha, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Urbiha/urbiha4.html">Hyperfibonacci Sequences and Polytopic Numbers</a>, Journal of Integer Sequences, Vol. 19, 2016, Issue 7, #16.7.6.
%H P. Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence</a>, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
%H F. Hazama, <a href="http://dx.doi.org/10.1016/j.disc.2011.06.008">Spectra of graphs attached to the space of melodies</a>, Discrete Math., 311 (2011), 2368-2383. See Table 2.1.
%H Dov Jarden, <a href="/A001602/a001602.pdf">Recurring Sequences</a>, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 96.
%H K. Kuhapatanakul, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Kuhapatanakul/kuha4.html">On the Sums of Reciprocal Generalized Fibonacci Numbers</a>, J. Int. Seq. 16 (2013) #13.7.1.
%H Rui Liu and Feng-Zhen Zhao, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Liu/liu10.html">On the Sums of Reciprocal Hyperfibonacci Numbers and Hyperlucas Numbers</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.4.5. - From _N. J. A. Sloane_, Oct 05 2012
%H R. J. Mathar, <a href="http://arxiv.org/abs/0903.2514">Hardy-Littlewood constants embedded into infinite products over all positive integers</a>, sequence a_{1,s}, arXiv:0903.2514 [math.NT], 2009-2011.
%H N. Neumärker, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Neumarker/neumarker3.html">Realizability of Integer Sequences as Differences of Fixed Point Count Sequences</a>, Journal of Integer Sequences 12 (2009) 09.4.5, Example 10.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A. Radhakrishnan, L. Solus, and C. Uhler. <a href="https://arxiv.org/abs/1706.06091">Counting Markov equivalence classes for DAG models on trees</a>, Discrete Applied Mathematics 244 (2018): 170-185.
%H V. Shevelev, <a href="http://dx.doi.org/10.1142/S179304210700078X">On divisibility of C(n-i-1,i-1) by i</a>, Int. J. of Number Theory, 3 (2007), no.1, 119-139. [_Vladimir Shevelev_, Apr 23 2010]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphRank.html">Graph Rank</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LucasCubeGraph.html">Lucas Cube Graph</a>
%H J. W. Wrench, Jr., <a href="http://dx.doi.org/10.1090/S0025-5718-1961-0124305-0">Evaluation of Artin's constant and the twin-prime constant</a>, Math. Comp., 15 (1961), 396-398.
%H Li-Na Zheng, Rui Liu, and Feng-Zhen Zhao, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Zheng/zheng5.html">On the Log-Concavity of the Hyperfibonacci Numbers and the Hyperlucas Numbers</a>, Journal of Integer Sequences, Vol. 17 (2014), #14.1.4.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).
%F a(n) = A000204(n)-1 = A000032(n+1)-1 = A000071(n+1) + A000045(n).
%F G.f.: x*(2-x)/((1-x-x^2)*(1-x)) = (2*x-x^2)/(1-2*x+x^3). [_Simon Plouffe_ in his 1992 dissertation]
%F a(n) = F(n) + F(n+2) - 1 where F(n) is the n-th Fibonacci number. - _Zerinvary Lajos_, Jan 31 2008
%F a(n) = A014217(n+1) - A000035(n+1). - _Paul Curtz_, Sep 21 2008
%F a(n) = Sum_{i=1..floor((n+1)/2)} ((n+1)/i)*C(n-i,i-1). In more general case of polynomials Q_n(x)=a(n,x) (see our comment) we have Q_n(x) = Sum_{i=1..floor((n+1)/2)}((n+1)/i)*C(n-i,i-1)*x^(i-1). - _Vladimir Shevelev_, Apr 23 2010
%F a(n) = Sum_{k=0..n-1} Lucas(k), where Lucas(n) = A000032(n). - _Gary Detlefs_, Dec 07 2010
%F a(0)=0, a(1)=2, a(2)=3; for n>=3, a(n) = 2*a(n-1) - a(n-3). - _George F. Johnson_, Jan 28 2013
%F For n > 1, a(n) = A048162(n+1) + 3. - _Toby Gottfried_, Apr 13 2013
%F For n > 0, a(n) = A169985(n + 1) - 1. - _Gus Wiseman_, Feb 12 2019
%t t = {0, 2}; Do[AppendTo[t, t[[-1]] + t[[-2]] + 1], {n, 2, 40}]; t
%t RecurrenceTable[{a[n] == a[n - 1] +a[n - 2] +1, a[0] == 0, a[1] == 2}, a, {n, 0, 40}] (* _Robert G. Wilson v_, Apr 13 2013 *)
%t CoefficientList[Series[x (2 - x)/((1 - x - x^2) (1 - x)), {x, 0, 40}], x] (* _Vincenzo Librandi_, Mar 20 2015 *)
%t Table[Fibonacci[n] + Fibonacci[n + 2] - 1, {n, 0, 40}] (* _Eric W. Weisstein_, Feb 13 2018 *)
%t LinearRecurrence[{2, 0, -1}, {2, 3, 6}, 20] (* _Eric W. Weisstein_, Feb 13 2018 *)
%t Table[LucasL[n] - 1, {n, 20}] (* _Eric W. Weisstein_, Aug 01 2023 *)
%t LucasL[Range[20]] - 1 (* _Eric W. Weisstein_, Aug 01 2023 *)
%o (Haskell)
%o a001610 n = a001610_list !! n
%o a001610_list =
%o 0 : 2 : map (+ 1) (zipWith (+) a001610_list (tail a001610_list))
%o -- _Reinhard Zumkeller_, Aug 21 2011
%o (Magma) I:=[0,2]; [n le 2 select I[n] else Self(n-1)+Self(n-2)+1: n in [1..40]]; // _Vincenzo Librandi_, Mar 20 2015
%o (Magma) [Lucas(n+1) -1: n in [0..40]]; // _G. C. Greubel_, Jul 12 2019
%o (PARI) a(n)=([0,1,0; 0,0,1; -1,0,2]^n*[0;2;3])[1,1] \\ _Charles R Greathouse IV_, Sep 08 2016
%o (PARI) vector(40, n, f=fibonacci; f(n+1)+f(n-1)-1) \\ _G. C. Greubel_, Jul 12 2019
%o (Sage) [lucas_number2(n+1,1,-1) -1 for n in (0..40)] # _G. C. Greubel_, Jul 12 2019
%o (GAP) List([0..40], n-> Lucas(1,-1,n+1)[2] -1); # _G. C. Greubel_, Jul 12 2019
%Y Cf. A000032 (first differences), A000071, A000126, A000204, A000296, A001644, A032190, A169985, A174625, A306357.
%K nonn,easy,hear
%O 0,2
%A _N. J. A. Sloane_
|
