login
This site is supported by donations to The OEIS Foundation.

 

Logo


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)
259
1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

Also called Schoute's accessory series (see Jean, 1984). - N. J. A. Sloane, Jun 08 2011

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

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.

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

Row sums of A029635 are 1,1,3,4,7,... - Paul Barry, Jan 30 2005

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 (smiley(AT)math.uaa.alaska.edu), Oct 14 2001

Row sums of the triangle in A182579. - Reinhard Zumkeller, May 07 2012

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

REFERENCES

Mohammad K. Azarian, Identities Involving Lucas or Fibonacci and Lucas Numbers as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 45, 2012, pp. 2221-2227.

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

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

E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.

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

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

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

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

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

Sarah H. Holliday and Takao Komatsu, On the Sum of Reciprocal Generalized Fibonacci Numbers, Integers. Volume 11, Issue 4, Pages 441-455, DOI: 10.1515/INTEG.2011.031.

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

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

Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.

J. L. Ramírez, G. N. Rubiano, Properties and Generalizations of the Fibonacci Word Fractal, The Mathematica Journal, Vol. 16 (2014).

Z. Skupien, Sums of Powered Characteristic Roots Count Distance-Independent Circular Sets, Discussiones Mathematicae Graph Theory. Volume 33, Issue 1, Pages 217-229, ISSN (Print) 2083-5892, DOI: 10.7151/dmgt.1658, April 2013.

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

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

LINKS

N. J. A. Sloane, The first 500 Lucas numbers: Table of n, L(n) for n = 1..500

G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3

R. Jovanovic, First 70 Lucas numbers

Blair Kelly, Factorizations of Lucas numbers

Tanya Khovanova, Recursive Sequences

C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.

R. D. Knott, The Lucas Numbers in Pascal's Triangle.

Mathilde Noual, Dynamics of Circuits and Intersecting Circuits, in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444, ArXiv 1011.3930. - N. J. A. Sloane, Jul 07 2012

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368, 2012

Mark A. Shattuck and Carl G. Wagner, Periodicity and Parity Theorems for a Statistic on r-Mino Arrangements, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.6.

N. J. A. Sloane, Illustration of initial terms: the Lucas tree

Eric Weisstein's World of Mathematics, Lucas Number

Eric Weisstein's World of Mathematics, Lucas n-Step Number

Index entries for "core" sequences

Index to sequences with linear recurrences with constant coefficients, signature (1,1).

FORMULA

Expansion of x(1+2x)/(1-x-x^2). - Simon Plouffe, dissertation 1992; multiplied by x by R. J. Mathar, Nov 14 2007

a(n) = A000045(2n)/A000045(n). - Benoit Cloitre, Jan 05 2003

For n > 1, L(n) = A000045(n+2) - A000045(n-2) (A000045 = Fibonacci numbers). - Gerald McGarvey, Jul 10 2004

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

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

a(n) = sum{k=0..floor((n+1)/2), (n+1)*binomial(n-k+1, k)/(n-k+1)}. - Paul Barry, Jan 30 2005

L(n) = A000045(n+3) - 2*A000045(n). - Creighton Dement, Oct 07 2005

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

L(n) = A000045(n+1) + A000045(n-1). - John Blythe Dobson, Sep 29 2007

a(n) = 2*fibonacci(n-1)+fibonacci(n), n>=1. - Zerinvary Lajos, Oct 05 2007

L(n) = term (1,1) in the 1 x 2 matrix [2,-1].[1,1; 1,0]^n. - Alois P. Heinz, Jul 25 2008

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

a(n) = A014217(n+1)-A014217(n-1). See A153263. - Paul Curtz, Dec 22 2008

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

From Hieronymus Fischer, Oct 20 2010 (Start)

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

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)

INVERT transform of (1, 2, -1, -2, 1, 2,...). - Gary W. Adamson, Mar 07 2012

L(2n-1) = floor(phi^(2n-1)); L(2n) = ceiling(phi^(2n)). - Thomas Ordowski, Jun 15 2012

MAPLE

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

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

L[1]:=1: L[2]:=3: for n from 3 to 34 do L[n]:=L[n-1]+L[n-2] od:seq(L[n], n=1..34);

a:=n->2*fibonacci(n-1)+fibonacci(n): seq(a(n), n=1..34); # Zerinvary Lajos, Oct 05 2007

A000204:=-z*(1+2*z)/(-1+z+z**2); # Simon Plouffe in his 1992 dissertation.

L:= n-> (Matrix([[2, -1]]).Matrix ([[1, 1], [1, 0]])^n)[1, 1]; seq (L(n), n=1..50); # Alois P. Heinz, Jul 25 2008

MATHEMATICA

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

Table[LucasL[n, 1], {n, 1, 36}] (* Zerinvary Lajos, Jul 09 2009 *)

LinearRecurrence[{1, 1}, {1, 3}, 50] (* Sture Sjöstedt, Nov 28 2011 *)

PROG

(PARI) A000204(n)=fibonacci(n+1)+fibonacci(n-1) \\ Michael B. Porter, Nov 05 2009

(Haskell)

a000204 n = a000204_list !! n

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

-- Reinhard Zumkeller, Dec 18 2011

CROSSREFS

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

Sequence in context: A093090 A193686 * A075193 A042433 A024319 A041209

Adjacent sequences:  A000201 A000202 A000203 * A000205 A000206 A000207

KEYWORD

core,easy,nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

More terms from André F. Labossière, Nov 30 2004

Plouffe Maple line edited by N. J. A. Sloane, May 13 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 24 23:54 EDT 2014. Contains 248516 sequences.