A000204 - OEIS

%I M2341 N0924 #291 Jun 08 2024 00:01:36

%S 1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349,

%T 15127,24476,39603,64079,103682,167761,271443,439204,710647,1149851,

%U 1860498,3010349,4870847,7881196,12752043,20633239,33385282,54018521,87403803,141422324

%N Lucas numbers (beginning with 1): L(n) = L(n-1) + L(n-2) with L(1) = 1, L(2) = 3.

%C See A000032 for the version beginning 2, 1, 3, 4, 7, ...

%C Also called Schoute's accessory series (see Jean, 1984). - _N. J. A. Sloane_, Jun 08 2011

%C L(n) is the number of matchings in a cycle on n vertices: L(4)=7 because the matchings in a square with edges a, b, c, d (labeled consecutively) are the empty set, a, b, c, d, ac and bd. - _Emeric Deutsch_, Jun 18 2001

%C This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1..m - 1, a(m) = m + 1. The generating function is (x + m*x^m)/(1 - x - x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n - 1 - (m - 1)*i, i - 1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m = 2: A000204, m = 3: A001609, m = 4: A014097, m = 5: A058368, m = 6: A058367, m = 7: A058366, m = 8: A058365, m = 9: A058364.

%C L(n) is the number of points of period n in the golden mean shift. The number of orbits of length n in the golden mean shift is given by the n-th term of the sequence A006206. - _Thomas Ward_, Mar 13 2001

%C Row sums of A029635 are 1, 1, 3, 4, 7, ... - _Paul Barry_, Jan 30 2005

%C a(n) counts circular n-bit strings with no repeated 1's. E.g., for a(5): 00000 00001 00010 00100 00101 01000 01001 01010 10000 10010 10100. Note #{0...} = fib(n+1), #{1...} = fib(n-1), #{000..., 001..., 100...} = a(n-1), #{010..., 101...} = a(n-2). - _Len Smiley_, Oct 14 2001

%C Row sums of the triangle in A182579. - _Reinhard Zumkeller_, May 07 2012

%C If p is prime then L(p) == 1 (mod p). L(2^k) == -1 (mod 2^(k+1)) for k = 0,1,2,... - _Thomas Ordowski_, Sep 25 2013

%C Satisfies Benford's law [Brown-Duncan, 1970; Berger-Hill, 2017]. - _N. J. A. Sloane_, Feb 08 2017

%D P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 69.

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 46.

%D Leonhard Euler, Introductio in analysin infinitorum (1748), sections 216 and 229.

%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 148.

%D Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

%D V. E. Hoggatt, Jr., Fibonacci and Lucas Numbers. Houghton, Boston, MA, 1969.

%D R. V. Jean, Mathematical Approach to Pattern and Form in Plant Growth, Wiley, 1984. See p. 5. - _N. J. A. Sloane_, Jun 08 2011

%D Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001.

%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).

%D S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

%H Indranil Ghosh, <a href="/A000204/b000204.txt">Table of n, a(n) for n = 1..4780</a> (terms 1..500 computed by N. J. A. Sloane)

%H Mohammad K. Azarian, <a href="http://www.m-hikari.com/ijcms/ijcms-2012/45-48-2012/azarianIJCMS45-48-2012.pdf">Identities Involving Lucas or Fibonacci and Lucas Numbers as Binomial Sums</a>, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 45, 2012, pp. 2221-2227.

%H Arno Berger and Theodore P. Hill, <a href="http://www.ams.org/publications/journals/notices/201702/rnoti-p132.pdf">What is Benford's Law?</a>, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.

%H J. Brown and R. L. Duncan, <a href="http://www.fq.math.ca/Scanned/8-5/brown.pdf">Modulo one uniform distribution of the sequence of logarithms of certain recursive sequences</a>, Fibonacci Quarterly 8 (1970) 482-486.

%H Enrico Di Cera and Yong Kong, <a href="https://doi.org/10.1016/S0301-4622(96)02178-3">Theory of multivalent binding in one and two-dimensional lattices</a>, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.

%H G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Ward/ward2.html">Integer Sequences and Periodic Points</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3

%H Sergio Falcon, <a href="http://saspublisher.com/wp-content/uploads/2014/06/SJET24C669-675.pdf">On The Generating Functions of the Powers of the K-Fibonacci Numbers</a>, Scholars Journal of Engineering and Technology (SJET), 2014; 2 (4C):669-675.

%H Scott Garrabrant and Igor Pak, <a href="http://arxiv.org/abs/1407.8222">Counting with irrational tiles</a>, arXiv:1407.8222 [math.CO], 2014.

%H R. K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]

%H Sarah H. Holliday and Takao Komatsu, <a href="http://dx.doi.org/10.1515/INTEG.2011.031">On the Sum of Reciprocal Generalized Fibonacci Numbers</a>, Integers. Volume 11, Issue 4, Pages 441-455.

%H R. Jovanovic, <a href="http://milan.milanovic.org/math/Math.php?akcija=SviLukasovi">First 70 Lucas numbers</a>

%H Blair Kelly, <a href="http://mersennus.net/fibonacci//lucas.txt">Factorizations of Lucas numbers</a>

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H Clark Kimberling, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Kimberling/kimberling24.html">Matrix Transformations of Integer Sequences</a>, J. Integer Seqs., Vol. 6, 2003.

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/lucasNbs.html">The Lucas Numbers in Pascal's Triangle</a>.

%H Kantaphon 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 D. H. Lehmer, <a href="/A002487/a002487_1.pdf">On Stern's Diatomic Series</a>, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]

%H Edouard Lucas, <a href="http://www.mathstat.dal.ca/FQ/Books/Complete/simply-periodic.pdf">The Theory of Simply Periodic Numerical Functions</a>, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.

%H Mathilde Noual, <a href="http://arxiv.org/abs/1011.3930">Dynamics in parallel of double Boolean automata circuits</a>, arXiv:1011.3930 [cs.DM], 2010. - _N. J. A. Sloane_, Jul 07 2012

%H Mathilde Noual, <a href="http://dx.doi.org/10.1007/978-3-642-28332-1_37">Dynamics of Circuits and Intersecting Circuits</a>, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444. - _N. J. A. Sloane_, Jul 07 2012

%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 Yash Puri and Thomas Ward, <a href="http://www.fq.math.ca/Scanned/39-5/puri.pdf">A dynamical property unique to the Lucas sequence</a>, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.

%H Yash Puri and Thomas Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

%H José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, <a href="http://arxiv.org/abs/1212.1368">A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake</a>, arXiv preprint arXiv:1212.1368 [cs.DM], 2012.

%H José L. Ramírez and Gustavo N. Rubiano, <a href="http://www.mathematica-journal.com/2014/02/properties-and-generalizations-of-the-fibonacci-word-fractal/">Properties and Generalizations of the Fibonacci Word Fractal</a>, The Mathematica Journal, Vol. 16 (2014).

%H Mark A. Shattuck and Carl G. Wagner, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Shattuck/shattuck56.html">Periodicity and Parity Theorems for a Statistic on r-Mino Arrangements</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.6.

%H N. J. A. Sloane, <a href="/A000204/a000204.html">Illustration of initial terms: the Lucas tree</a>

%H Zdzisław Skupień, <a href="http://dx.doi.org/10.7151/dmgt.1658">Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets</a>, Discussiones Mathematicae Graph Theory. Volume 33, Issue 1, Pages 217-229, ISSN (Print) 2083-5892, DOI: 10.7151/dmgt.1658, April 2013.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LucasNumber.html">Lucas Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Lucasn-StepNumber.html">Lucas n-Step Number</a>

%H Richard J. Yanco, <a href="/A007380/a007380.pdf">Letter and Email to N. J. A. Sloane, 1994</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1).

%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>

%F Expansion of x(1 + 2x)/(1 - x - x^2). - _Simon Plouffe_, dissertation 1992; multiplied by x. - _R. J. Mathar_, Nov 14 2007

%F a(n) = A000045(2n)/A000045(n). - _Benoit Cloitre_, Jan 05 2003

%F For n > 1, L(n) = F(n + 2) - F(n - 2), where F(n) is the n-th Fibonacci number (A000045). - _Gerald McGarvey_, Jul 10 2004

%F a(n+1) = 4*A054886(n+3) - A022388(n) - 2*A022120(n+1) (a conjecture; note that the above sequences have different offsets). - _Creighton Dement_, Nov 27 2004

%F a(n) = Sum_{k=0..floor((n+1)/2)} (n+1)*binomial(n - k + 1, k)/(n - k + 1). - _Paul Barry_, Jan 30 2005

%F L(n) = A000045(n+3) - 2*A000045(n). - _Creighton Dement_, Oct 07 2005

%F L(n) = A000045(n+1) + A000045(n-1). - _John Blythe Dobson_, Sep 29 2007

%F a(n) = 2*Fibonacci(n-1) + Fibonacci(n), n >= 1. - _Zerinvary Lajos_, Oct 05 2007

%F L(n) is the term (1, 1) in the 1 X 2 matrix [2, -1].[1, 1; 1, 0]^n. - _Alois P. Heinz_, Jul 25 2008

%F a(n) = phi^n + (1 - phi)^n = phi^n + (-phi)^(-n) = ((1 + sqrt(5))^n + (1 - sqrt(5))^n)/(2^n) where phi is the golden ratio (A001622). - _Artur Jasinski_, Oct 05 2008

%F a(n) = A014217(n+1) - A014217(n-1). See A153263. - _Paul Curtz_, Dec 22 2008

%F a(n) = ((1 + sqrt(5))^n - (1 - sqrt(5))^n)/(2^n*sqrt(5)) + ((1 + sqrt(5))^(n - 1) - (1 - sqrt(5))^(n - 1))/(2^(n - 2)*sqrt(5)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009, Jan 14 2009

%F From _Hieronymus Fischer_, Oct 20 2010 (Start)

%F Continued fraction for n odd: [L(n); L(n), L(n), ...] = L(n) + fract(Fib(n) * phi).

%F Continued fraction for n even: [L(n); -L(n), L(n), -L(n), L(n), ...] = L(n) - 1 + fract(Fib(n)*phi). Also: [L(n) - 2; 1, L(n) - 2, 1, L(n) - 2, ...] = L(n) - 2 + fract(Fib(n)*phi). (End)

%F INVERT transform of (1, 2, -1, -2, 1, 2, ...). - _Gary W. Adamson_, Mar 07 2012

%F L(2n - 1) = floor(phi^(2n - 1)); L(2n) = ceiling(phi^(2n)). - _Thomas Ordowski_, Jun 15 2012

%F a(n) = hypergeom([(1 - n)/2, -n/2], [1 - n], -4) for n >= 3. - _Peter Luschny_, Sep 03 2019

%F E.g.f.: 2*(exp(x/2)*cosh(sqrt(5)*x/2) - 1). - _Stefano Spezia_, Jul 26 2022

%e G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 11*x^5 + 18*x^6 + 29*x^7 + 47*x^8 + ...

%p A000204 := proc(n) option remember; if n <=2 then 2*n-1; else procname(n-1)+procname(n-2); fi; end;

%p with(combinat): A000204 := n->fibonacci(n+1)+fibonacci(n-1);

%p # alternative Maple program:

%p L:= n-> (<<1|1>, <1|0>>^n. <<2, -1>>)[1, 1]:

%p seq(L(n), n=1..50);  # _Alois P. Heinz_, Jul 25 2008

%p # Alternative:

%p a := n -> `if`(n=1, 1, `if`(n=2, 3, hypergeom([(1-n)/2, -n/2], [1-n], -4))):

%p seq(simplify(a(n)), n=1..39); # _Peter Luschny_, Sep 03 2019

%t c = (1 + Sqrt[5])/2; Table[Expand[c^n + (1 - c)^n], {n, 30}] (* _Artur Jasinski_, Oct 05 2008 *)

%t Table[LucasL[n, 1], {n, 36}] (* _Zerinvary Lajos_, Jul 09 2009 *)

%t LinearRecurrence[{1, 1},{1, 3}, 50] (* _Sture Sjöstedt_, Nov 28 2011 *)

%t lukeNum[n_] := If[n < 1, 0, LucasL[n]]; (* _Michael Somos_, May 18 2015 *)

%t lukeNum[n_] := SeriesCoefficient[x D[Log[1 / (1 - x - x^2)], x], {x, 0, n}]; (* _Michael Somos_, May 18 2015 *)

%o (PARI) A000204(n)=fibonacci(n+1)+fibonacci(n-1) \\ _Michael B. Porter_, Nov 05 2009

%o (Haskell)

%o a000204 n = a000204_list !! n

%o a000204_list = 1 : 3 : zipWith (+) a000204_list (tail a000204_list)

%o -- _Reinhard Zumkeller_, Dec 18 2011

%o (Sage)

%o def A000204():

%o     x, y = 1, 2

%o     while true:

%o        yield x

%o        x, y = x + y, x

%o a = A000204(); print([next(a) for i in range(39)])  # _Peter Luschny_, Dec 17 2015

%o (Magma) [Lucas(n): n in [1..30]]; // _G. C. Greubel_, Dec 17 2017

%o (Scala) def lucas(n: BigInt): BigInt = {

%o   val zero = BigInt(0)

%o   def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {

%o     case `zero` => a

%o     case _ => fibTail(n - 1, b, a + b)

%o   }

%o   fibTail(n, 2, 1)

%o }

%o (1 to 50).map(lucas(_)) // _Alonso del Arte_, Oct 20 2019

%o (Python)

%o from functools import cache

%o @cache

%o def a(n): return [1, 3][n-1] if n < 3 else a(n-1) + a(n-2)

%o print([a(n) for n in range(1, 41)]) # _Michael S. Branicky_, Nov 13 2022

%Y Cf. A000032, A000045, A061084, A027960, A001609, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A006206, A101033, A101032, A100492, A099731, A094216, A094638, A000108, A090946 (complement).

%K core,easy,nonn,nice

%O 1,2

%A _N. J. A. Sloane_

%E Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

%E Plouffe Maple line edited by _N. J. A. Sloane_, May 13 2008