This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000204 Lucas numbers (beginning with 1): L(n) = L(n-1) + L(n-2) with L(1) = 1, L(2) = 3. (Formerly M2341 N0924) 288

%I M2341 N0924

%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(binomial(n-1-(m-1)*i, i-1)/i, i=1..n/m). 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 (t.ward(AT)uea.ac.uk), 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 A. Berger and T. 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. 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 E. Di Cera and Y. 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 S. 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 S. Garrabrant, I. 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 C. 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 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 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="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 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 Y. Puri and T. 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 J. L. Ramírez, G. 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 Z. Skupien, <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 R. 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 by _R. J. Mathar_, Nov 14 2007

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

%F For n > 1, L(n) = A000045(n+2) - A000045(n-2) (A000045 = Fibonacci numbers). - _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). Generating floretion: - 0.25'i - 0.5'k - 0.25i' - 0.5j' - 0.5k' - 0.75'ii' + 0.75'jj' + 0.25'kk' + 0.25'jk' - 0.5'ki' + 0.25'kj' - 0.25e. - _Creighton Dement_, Nov 27 2004

%F L(n) = (1/(n-1)!) * [ n^(n-1) - { -C(n-2, 0) + 2*C(n-2, 1) + 3*C(n-2, 2) }*n^(n-2) + { 2*C(n-3, 0) + 15*C(n-3, 1) + 51*C(n-3, 2) + 65*C(n-3, 3) + 27*C(n-3, 4) }*n^(n-3) - { -6*C(n-4, 0) + 148*C(n-4, 1) + 945*C(n-4, 2) + 2292*C(n-4, 3) + 2776*C(n-4, 4) + 1680*C(n-4, 5) + 405*C(n-4, 6) }*n^(n-4) + ... ]. - _André F. Labossière_, Nov 30 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) = (1/sqrt(5))*(2.5+0.5*sqrt(5))*(0.5+0.5*sqrt(5))^n + (1/sqrt(5))*(-2.5+0.5*sqrt(5))*(0.5-0.5*sqrt(5))^n. - _Antonio Alberto Olivares_, Feb 28 2006

%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) = 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+sqrt5)^n-(1-sqrt5)^n)/(2^n*sqrt5)+((1+sqrt5)^(n-1)-(1-sqrt5)^(n-1))/(2^(n-2)*sqrt5). - 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

%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

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

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

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

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

%t a[ 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 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 [a.next() for i in range(39)] # _Peter Luschny_, Dec 17 2015

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

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

%K core,easy,nonn,nice

%O 1,2

%A _N. J. A. Sloane_