A001610 a(n) = a(n-1) + a(n-2) + 1, with a(0) = 0 and a(1) = 2.

0, 2, 3, 6, 10, 17, 28, 46, 75, 122, 198, 321, 520, 842, 1363, 2206, 3570, 5777, 9348, 15126, 24475, 39602, 64078, 103681, 167760, 271442, 439203, 710646, 1149850, 1860497, 3010348, 4870846, 7881195, 12752042, 20633238, 33385281, 54018520

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• hear

Comments

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]

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

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

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

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

From Gus Wiseman, Feb 12 2019: (Start)

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:

{1}, {2}, {3}, {4}, {5}, {6},

{1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},

{1,3,5}, {2,4,6}.

(End)

Also the rank of the n-Lucas cube graph. - Eric W. Weisstein, Aug 01 2023

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 0..500
• Daniel Birmajer, Juan B. Gil, Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv:1505.06339 [math.NT], 2015.
• Ning-Ning Cao and Feng-Zhen Zhao, Some Properties of Hyperfibonacci and Hyperlucas Numbers, J. Int. Seq. 13 (2010) # 10.8.8.
• Ligia L. Cristea, Ivica Martinjak, and Igor Urbiha, Hyperfibonacci Sequences and Polytopic Numbers, Journal of Integer Sequences, Vol. 19, 2016, Issue 7, #16.7.6.
• Taras Goy and Mark Shattuck, Toeplitz-Hessenberg determinant formulas for the sequence F_n-1, Online J. Anal. Comb. (2025) Vol. 19, Paper 1, 1-26.
• Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
• Fumio Hazama, Spectra of graphs attached to the space of melodies, Discrete Math., 311 (2011), 2368-2383. See Table 2.1.
• Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 96.
• Kantaphon Kuhapatanakul, On the Sums of Reciprocal Generalized Fibonacci Numbers, J. Int. Seq. 16 (2013) #13.7.1.
• Rui Liu and Feng-Zhen Zhao, On the Sums of Reciprocal Hyperfibonacci Numbers and Hyperlucas Numbers, Journal of Integer Sequences, Vol. 15 (2012), #12.4.5. - From _N. J. A. Sloane_, Oct 05 2012
• Richard J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, sequence a_{1,s}, arXiv:0903.2514 [math.NT], 2009-2011.
• El-Mehdi Mehiri, Saad Mneimneh, and Hacène Belbachir, The Towers of Fibonacci, Lucas, Pell, and Jacobsthal, arXiv:2502.11045 [math.CO], 2025. See p. 12.
• Natascha Neumärker, Realizability of Integer Sequences as Differences of Fixed Point Count Sequences, Journal of Integer Sequences 12 (2009) 09.4.5, Example 10.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Adityanarayanan Radhakrishnan, Liam Solus, and Caroline Uhler. Counting Markov equivalence classes for DAG models on trees, arXiv:1706.06091 [math.CO], 2017; Discrete Applied Mathematics 244 (2018): 170-185.
• Vladimir Shevelev, On divisibility of C(n-i-1,i-1) by i, Int. J. of Number Theory, 3 (2007), no.1, 119-139. [_Vladimir Shevelev_, Apr 23 2010]
• Eric Weisstein's World of Mathematics, Graph Rank
• Eric Weisstein's World of Mathematics, Lucas Cube Graph
• John W. Wrench, Jr., Evaluation of Artin's constant and the twin-prime constant, Math. Comp., 15 (1961), 396-398.
• Li-Na Zheng, Rui Liu, and Feng-Zhen Zhao, On the Log-Concavity of the Hyperfibonacci Numbers and the Hyperlucas Numbers, Journal of Integer Sequences, Vol. 17 (2014), #14.1.4.
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Crossrefs

Cf. A000032 (first differences), A000071, A000126, A000204, A000296, A001644, A032190, A169985, A174625, A306357.

Programs

GAP

List([0..40], n-> Lucas(1,-1,n+1)[2] -1); # G. C. Greubel, Jul 12 2019

Haskell

a001610 n = a001610_list !! n
a001610_list =
   0 : 2 : map (+ 1) (zipWith (+) a001610_list (tail a001610_list))
-- Reinhard Zumkeller, Aug 21 2011

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

Magma

[Lucas(n+1) -1: n in [0..40]]; // G. C. Greubel, Jul 12 2019

Mathematica

t = {0, 2}; Do[AppendTo[t, t[[-1]] + t[[-2]] + 1], {n, 2, 40}]; 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 *)
CoefficientList[Series[x (2 - x)/((1 - x - x^2) (1 - x)), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 20 2015 *)
Table[Fibonacci[n] + Fibonacci[n + 2] - 1, {n, 0, 40}] (* Eric W. Weisstein, Feb 13 2018 *)
LinearRecurrence[{2, 0, -1}, {2, 3, 6}, 20] (* Eric W. Weisstein, Feb 13 2018 *)
Table[LucasL[n] - 1, {n, 20}] (* Eric W. Weisstein, Aug 01 2023 *)
LucasL[Range[20]] - 1 (* Eric W. Weisstein, Aug 01 2023 *)

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

PARI

vector(40, n, f=fibonacci; f(n+1)+f(n-1)-1) \\ G. C. Greubel, Jul 12 2019

Sage

[lucas_number2(n+1,1,-1) -1 for n in (0..40)] # G. C. Greubel, Jul 12 2019

Formula

a(n) = A000204(n)-1 = A000032(n+1)-1 = A000071(n+1) + A000045(n).

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]

a(n) = F(n) + F(n+2) - 1 where F(n) is the n-th Fibonacci number. - Zerinvary Lajos, Jan 31 2008

a(n) = A014217(n+1) - A000035(n+1). - Paul Curtz, Sep 21 2008

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

a(n) = Sum_{k=0..n-1} Lucas(k), where Lucas(n) = A000032(n). - Gary Detlefs, Dec 07 2010

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

For n > 1, a(n) = A048162(n+1) + 3. - Toby Gottfried, Apr 13 2013

For n > 0, a(n) = A169985(n + 1) - 1. - Gus Wiseman, Feb 12 2019