cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

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_{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.
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
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, 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
Satisfies Benford's law [Brown-Duncan, 1970; Berger-Hill, 2017]. - N. J. A. Sloane, Feb 08 2017

Examples

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

References

  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 69.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 46.
  • 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.
  • 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.
  • 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

Crossrefs

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

Programs

  • Haskell
    a000204 n = a000204_list !! n
a000204_list = 1 : 3 : zipWith (+) a000204_list (tail a000204_list)
-- Reinhard Zumkeller, Dec 18 2011
  • Magma
    [Lucas(n): n in [1..30]]; // G. C. Greubel, Dec 17 2017
  • Maple
    A000204 := proc(n) option remember; if n <=2 then 2*n-1; else procname(n-1)+procname(n-2); fi; end;
with(combinat): A000204 := n->fibonacci(n+1)+fibonacci(n-1);
# alternative Maple program:
L:= n-> (<<1|1>, <1|0>>^n. <<2, -1>>)[1, 1]:
seq(L(n), n=1..50);  # Alois P. Heinz, Jul 25 2008
# Alternative:
a := n -> `if`(n=1, 1, `if`(n=2, 3, hypergeom([(1-n)/2, -n/2], [1-n], -4))):
seq(simplify(a(n)), n=1..39); # Peter Luschny, Sep 03 2019
  • Mathematica
    c = (1 + Sqrt[5])/2; Table[Expand[c^n + (1 - c)^n], {n, 30}] (* Artur Jasinski, Oct 05 2008 *)
Table[LucasL[n, 1], {n, 36}] (* Zerinvary Lajos, Jul 09 2009 *)
LinearRecurrence[{1, 1},{1, 3}, 50] (* Sture Sjöstedt, Nov 28 2011 *)
lukeNum[n_] := If[n < 1, 0, LucasL[n]]; (* Michael Somos, May 18 2015 *)
lukeNum[n_] := SeriesCoefficient[x D[Log[1 / (1 - x - x^2)], x], {x, 0, n}]; (* Michael Somos, May 18 2015 *)
  • PARI
    A000204(n)=fibonacci(n+1)+fibonacci(n-1) \\ Michael B. Porter, Nov 05 2009
  • Python
    from functools import cache
@cache
def a(n): return [1, 3][n-1] if n < 3 else a(n-1) + a(n-2)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Nov 13 2022
  • Python
    [(i:=-1)+(j:=2)] + [(j:=i+j)+(i:=j-i) for  in range(100)] # _Jwalin Bhatt, Apr 02 2025
  • Sage
    def A000204():
    x, y = 1, 2
    while true:
       yield x
       x, y = x + y, x
a = A000204(); print([next(a) for i in range(39)])  # Peter Luschny, Dec 17 2015
  • Scala
    def lucas(n: BigInt): BigInt = {
  val zero = BigInt(0)
  def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {
    case `zero` => a
    case _ => fibTail(n - 1, b, a + b)
  }
  fibTail(n, 2, 1)
}
(1 to 50).map(lucas()) // _Alonso del Arte, Oct 20 2019

Formula

Expansion of x(1 + 2x)/(1 - x - x^2). - Simon Plouffe, dissertation 1992; multiplied by x. - R. J. Mathar, Nov 14 2007
a(n) = A000045(2n)/A000045(n). - Benoit Cloitre, Jan 05 2003
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
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
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) = 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) is the 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 + 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
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
a(n) = hypergeom([(1 - n)/2, -n/2], [1 - n], -4) for n >= 3. - Peter Luschny, Sep 03 2019
E.g.f.: 2*(exp(x/2)*cosh(sqrt(5)*x/2) - 1). - Stefano Spezia, Jul 26 2022

Extensions

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
Plouffe Maple line edited by N. J. A. Sloane, May 13 2008

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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