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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000032 Lucas numbers (beginning at 2): L(n) = L(n-1) + L(n-2). (Cf. A000204.)
(Formerly M0155)
797

%I M0155

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

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

%U 1149851,1860498,3010349,4870847,7881196,12752043,20633239,33385282

%N Lucas numbers (beginning at 2): L(n) = L(n-1) + L(n-2). (Cf. A000204.)

%C This is also the Horadam sequence (2, 1, 1, 1). - _Ross La Haye_, Aug 18 2003

%C For distinct primes p, q, L(p) is congruent to 1 mod p, L(2p) is congruent to 3 mod p and L(pq) is congruent 1 + q(L(q) - 1) mod p. Also, L(m) divides F(2km) and L((2k + 1)m), k, m >= 0.

%C a(n) = sum(P(3; n - 1 - k, k), k = 0..ceiling((n - 1)/2)), n >= 1, with a(0) = 2. These are the sums over the SW-NE diagonals in P(3; n, k), the (3, 1) Pascal triangle A093560. Observation by _Paul Barry_, Apr 29 2004. Proof via recursion relations and comparison of inputs. Also SW-NE diagonal sums of the (1, 2) Pascal triangle A029635 (with T(0, 0) replaced by 2).

%C Suppose psi = log(phi). We get the representation L(n) = 2*cosh(n*psi) if n is even; L(n) = 2*sinh(n*psi) if n is odd. There is a similar representation for Fibonacci numbers (A000045). Many Lucas formulas now easily follow from appropriate sinh- and cosh-formulas. For example: the identity cosh^2(x) - sinh^2(x) = 1 implies L(n)^2 - 5F(n)^2 = 4*(-1)^n (setting x = n*psi). - _Hieronymus Fischer_, Apr 18 2007

%C From _John Blythe Dobson_, Oct 02 2007, Oct 11 2007: (Start)

%C The parity of L(n) follows easily from its definition, which shows that L(n) is even when n is a multiple of 3 and odd otherwise.

%C The first six multiplication formulae are:

%C L(2n) = (L(n))^2 - 2*(-1)^n.

%C L(3n) = (L(n))^3 - 3*((-1)^n)*L(n).

%C L(4n) = (L(n))^4 - 4*((-1)^n)*(L(n))^2 + 2.

%C L(5n) = (L(n))^5 - 5*((-1)^n)*(L(n))^3 + 5*L(n).

%C L(6n) = (L(n))^6 - 6*((-1)^n)*(L(n))^4 + 9*(L(n))^2 - 2*(-1)^n.

%C Generally, L(n) | L(mn) if and only if m is odd.

%C In the expansion of L(mn), where m represents the multiplier and n the index of a known value of L(n), the absolute values of the coefficients are the terms in the m-th row of the triangle A034807. When m = 1 and n = 1, L(n) = 1 and all the terms are positive and so the row sums of A034807 are simply the Lucas numbers. (End)

%C From _John Blythe Dobson_, Nov 15 2007: (Start)

%C The comments submitted by Miklos Kristof on Mar 19 2007 for the Fibonacci numbers (A000045) contain four important identities which have close analogues in the Lucas numbers:

%C For a >= b and odd b, L(a + b) + L(a - b) = 5*F(a)*F(b).

%C For a >= b and even b, L(a + b) + L(a - b) = L(a)*L(b).

%C For a >= b and odd b, L(a + b) - L(a - b) = L(a)*L(b).

%C For a >= b and even b, L(a + b) - L(a - b) = 5*F(a)*F(b).

%C A particularly interesting instance of the difference identity for even b is L(a + 30) - L(a - 30) = 5*F(a)*832040, since 5*832040 is divisible by 100, proving that the last two digits of Lucas numbers repeat in a cycle of length 60 (see A106291(100)). (End)

%C From _John Blythe Dobson_, Nov 15 2007: (Start)

%C The Lucas numbers satisfy remarkable difference equations, in some cases best expressed using Fibonacci numbers, of which representative examples are the following:

%C L(n) - L(n - 3) = 2*L(n - 2).

%C L(n) - L(n - 4) = 5*F(n - 2).

%C L(n) - L(n - 6) = 4*L(n - 3).

%C L(n) - L(n - 12) = 40*F(n - 6).

%C L(n) - L(n - 60) = 4160200*F(n - 30).

%C These formulae establish, respectively, that the Lucas numbers form a cyclic residue system of length 3 (mod 2), of length 4 (mod 5), of length 6 (mod 4), of length 12 (mod 40) and of length 60 (mod 4160200). The divisibility of the last modulus by 100 accounts for the fact that the last two digits of the Lucas numbers begin to repeat at L(60).

%C The divisibility properties of the Lucas numbers are very complex and still not fully understood, but several important criteria are established in Zhi-Hong Sun's 2003 survey of congruences for Fibonacci numbers. (End)

%C Sum_{n > 0} a(n)/(n*2^n) = 2*log(2). - _Jaume Oliver Lafont_, Oct 11 2009

%C A010888(a(n)) = A030133(n). - _Reinhard Zumkeller_, Aug 20 2011

%C For n >= 3, also the number of vertex covers for the cycle graph C_n. - _Eric W. Weisstein_, Jan 04 2014

%C The powers of phi, the golden ratio, approach the values of the Lucas numbers, the odd powers from above and the even powers from below. - _Geoffrey Caveney_, Apr 18 2014

%C Inverse binomial transform is (-1)^n * a(n). - _Michael Somos_, Jun 03 2014

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

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 32,50.

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

%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 Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001.

%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 N. J. A. Sloane, <a href="/A000032/b000032.txt">The first 500 Lucas numbers: Table of n, L(n) for n = 0..500</a>

%H A. Akbary, Q. Wang, <a href="http://dx.doi.org/10.1090/S0002-9939-05-08220-1">A generalized Lucas sequence and permutation binomials</a>, Proc. Amer. Math. Soc. 134 (2006) 15-22, sequence a(n) for l=5.

%H A. Aksenov, <a href="http://arxiv.org/abs/1108.5352">The Newman phenomenon and Lucas sequence</a>, arXiv:1108.5352, 2011

%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 G. Everest, Y. Puri and T. Ward, <a href="http://arXiv.org/abs/math.NT/0204173">Integer sequences counting periodic points</a>

%H Sergio Falcon, <a href="http://scik.org/index.php/jmcs/article/view/102/56">On the Lucas triangle and its relationship with the k-Lucas numbers</a>, Journal of Mathematical and Computational Science, 2 (2012), No. 3, pp. 425-434.

%H A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 12. <a href="http://tohbook.info">Book's website</a>

%H V. E. Hoggat, Jr., Marjorie Bicknell, <a href="http://www.jstor.org/stable/2689212">Some congruences of the Fibonacci numbers modulo a prime p</a>, Math. Mag. 47 (4) (1974) 210-214.

%H R. Javonovic, <a href="http://milan.milanovic.org/math/english/function1/function1.html">Lucas Function Calculator</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 R. Knott, <a href="http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/lucasNbs.html">The Lucas numbers</a>

%H R. Knott, <a href="http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/lucas200.html">The First 200 Lucas numbers and their factors</a>

%H Dmitry Kruchinin, <a href="http://arxiv.org/abs/1109.1683">Superposition's properties of logarithmic generating functions</a>, arXiv:1109.1683, 2011.

%H T. Mansour, M. Shattuck, <a href="http://dx.doi.org/10.1007/s12044-014-0166-7">A statistic on n-color compositions and related sequences</a>, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.

%H A. McLeod and W. O. J. Moser, <a href="http://www.jstor.org/stable/27642988">Counting cyclic binary strings</a>, Math. Mag., 80 (No. 1, 2007), 29-37.

%H Hisanori Mishima, Factorizations of Lucas Numbers: <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha113.htm">m=1..100</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha114.htm">m=101..200</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha115.htm">n=201..300</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha116.htm">n=301..400</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha117.htm">n=401..478</a>

%H Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences,</a> J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4

%H J. L. Ramirez and V. F. Sirvent, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ramirez/ramirez4.html">Incomplete Tribonacci Numbers and Polynomials</a>, Journal of Integer Sequences, Vol. 17, 2014, #14.4.2.

%H B. Rittaud, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Rittaud2/rittaud11.html">On the Average Growth of Random Fibonacci Sequences</a>, Journal of Integer Sequences, 10 (2007), Article 07.2.4.

%H M. Z. Spivey and L. L. Steil, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html">The k-Binomial Transforms and the Hankel Transform</a>, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.

%H Zhi-Hong Sun, <a href="http://www.hytc.edu.cn/xsjl/szh/ConFn.pdf">Congruences for Fibonacci Numbers</a> [PDF] (Lecture notes, 2009)

%H M. Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/MZV2011IMSc.pdf">Lectures on Multiple Zeta Values</a>, IMSC 2011.

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

%H Roman Witula, Damian Slota and Edyta Hetmaniok, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from255to263.pdf">Bridges between different known integer sequences</a>, Annales Mathematicae et Informaticae, 41 (2013) pp. 255-263.

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%H <a href="/index/Rea#recur1">Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)</a>

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

%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>

%F G.f.: (2 - x)/(1 - x - x^2).

%F L(n) = ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n.

%F L(n) = L(n - 1) + L(n - 2) = (-1)^n * L( - n).

%F E.g.f.: 2*exp(x/2)*cosh(sqrt(5)*x/2). - Len Smiley (smiley(AT)math.uaa.alaska.edu), Nov 30 2001

%F L(n) = Fibonacci(2*n)/Fibonacci(n) for n > 0. - _Jeff Burch_

%F L(n) = Fib(n) + 2*Fib(n - 1) = Fib(n + 1) + Fib(n - 1). - _Henry Bottomley_, Apr 12 2000

%F a(n) = sqrt(F(n)^2 + 4*F(n + 1)*F(n - 1)). - _Benoit Cloitre_, Jan 06 2003 [Corrected by _Gary Detlefs_, Jan 21 2011]

%F a(n) = 2^(1 - n)*sum{k = 0..floor(n/2), C(n, 2k)*5^k}. a(n) = 2T(n, i/2)( - i)^n with T(n, x) Chebyshev's polynomials of the first kind (see A053120) and i^2 = - 1. - _Paul Barry_, Nov 15 2003

%F L(n) = 2*Fib(n + 1) - Fib(n). - _Paul Barry_, Mar 22 2004

%F a(n) = floor((phi)^n + ( - phi)^( - n)). - _Paul Barry_, Mar 12 2005

%F From _Miklos Kristof_, Mar 19 2007: (Start)

%F Let F(n) = A000045 = Fibonacci numbers, L(n) = a(n) = Lucas numbers:

%F L(n + m) + (-1)^m*L(n - m) = L(n)*L(m).

%F L(n + m) - (-1)^m*L(n - m) = 8*F(n)*F(m).

%F L(n + m + k) + (-1)^k*L(n + m - k) + (-1)^m*(L(n - m + k) + (-1)^k*L(n - m - k)) = L(n)*L(m)*L(k).

%F L(n + m + k) - (-1)^k*L(n + m - k) + (-1)^m*(L(n - m + k) - (-1)^k*L(n - m - k)) = 5*F(n)*L(m)*F(k).

%F L(n + m + k) + (-1)^k*L(n + m - k) - (-1)^m*(L(n - m + k) + (-1)^k*L(n - m - k)) = 5*F(n)*F(m)*L(k).

%F L(n + m + k) - (-1)^k*L(n + m - k) - (-1)^m*(L(n - m + k) - (-1)^k*L(n - m - k)) = 5*L(n)*F(m)*F(k). (End)

%F Inverse: floor(log_phi(a(n)) + 0.5) = n, for n>1. Also for n >= 0, floor(1/2*log_phi(a(n)*a(n + 1))) = n. Extension valid for all integers n: floor(1/2*sign(a(n)*a(n + 1))*log_phi|a(n)*a(n + 1)|) = n {where sign(x) = sign of x}. - _Hieronymus Fischer_, May 02 2007

%F Conjecture: Let f(n) = Phi^n + Phi^( - n), then L(2n) = f(2n) and L(2n + 1) = f(2n + 1) - 2*Sum(k = 0..infinity, C(k + 1)/f(2n + 1)^(2k + 1)) where C(n) are Catalan numbers (A000108). - _Gerald McGarvey_, Dec 21 2007

%F Starting (1, 3, 4, 7, 11,...) = row sums of triangle A131774. - _Gary W. Adamson_, Jul 14 2007

%F a(n) = trace of the 2 X 2 matrix [0,1; 1,1]^n. - _Gary W. Adamson_, Mar 02 2008

%F From _Hieronymus Fischer_, Jan 02 2009: (Start)

%F For odd n: a(n) = floor(1/(fract(phi^n))); for even n>0: a(n) = ceiling(1/(1 - fract(phi^n))). This follows from the basic property of the golden ratio phi, which is phi - phi^(-1) = 1 (see general formula described in A001622).

%F a(n) = round(1/(min(fract(phi^n), 1 - fract(phi^n))), for n>1, where fract(x) = x - floor(x). (End)

%F E.g.f.: exp(phi*x) + exp( - x/phi) with phi: = (1 + sqrt(5))/2 (golden section). 1/phi = phi - 1. See another form given in the Smiley e.g.f. comment. - _Wolfdieter Lang_, May 15 2010

%F L(n)/L(n - 1) -> A001622. - _Vincenzo Librandi_, Jul 17 2010

%F a(n) = 2*a(n - 2) + a(n - 3), n>2. - _Gary Detlefs_, Sep 09 2010

%F L(n) = floor(1/fract(Fib(n)*phi)), for n odd. - _Hieronymus Fischer_, Oct 20 2010

%F L(n) = ceiling(1/(1 - fract(Fib(n)*phi))), for n even. - _Hieronymus Fischer_, Oct 20 2010

%F L(n) = 2^n * (cos(Pi/5)^n + cos(3*Pi/5)^n). - _Gary Detlefs_ Nov 29 2010

%F L(n) = (Fibonacci(2*n - 1)*Fibonacci(2*n + 1) - 1)/(Fibonacci(n)*Fibonacci(2*n)). - _Gary Detlefs_ Dec 13 2010

%F L(n) = sqrt(5*Fibonacci(n)^2 - 4*(-1)^(n + 1)). - _Gary Detlefs_ Dec 26 2010

%F L(n) = floor(phi^n) + ((-1)^n + 1)/2, where phi = A001662. - _Gary Detlefs_ Jan 20 2011

%F L(n) = Fibonacci(n + 6) mod Fibonacci(n + 2), n>2. - _Gary Detlefs_ May 19 2011

%F For n >= 2, a(n) = round(phi^n) where phi is the golden ratio. - _Arkadiusz Wesolowski_, Jul 20 2012

%F a(p*k) == a(k) (mod p) for primes p. a(2^s*n) == a(n)^(2^s) (mod 2) for s = 0,1,2.. a(2^k) == - 1 (mod 2^k). a(p^2*k) == a(k) (mod p) for primes p and s = 0,1,2,3.. [Hoggatt and Bicknell]. - _R. J. Mathar_, Jul 24 2012

%F From Gary Detlefs, Dec 21 2012: (Start)

%F L(2*k*n) = phi^(n*k) + (2 - phi)^(n*k).

%F L(k*n) = (F(k)*phi + F(k - 1))^n + (F(k + 1) - F(k)*phi)^n.

%F L(k*n) = (F(n)*phi + F(n - 1))^k + (F(n + 1) - F(n)*phi)^k.

%F where phi = (1 + sqrt(5))/2, F(n) = A000045(n).

%F (End)

%F L(n) = n * sum(binomial(n - k,k)/(n - k), k = 0..floor(n/2)), n>0 [H.W. Gould]. - _Gary Detlefs_, Jan 20 2013

%F G.f.: G(0), where G(k)= 1 + 1/(1 - (x*(5*k-1))/((x*(5*k+4)) - 2/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 15 2013

%F Let F(n) = A000045 = Fibonacci numbers, L(n) = a(n) = Lucas numbers. Then L(n) = F(n) + F(n-1) + F(n-2) + F(n-3), i.e., four consecutive Fibonacci numbers for any n. - _Bob Selcoe_, Jun 17 2013

%F Let b(n) = b(n-1) + b(n-2), with b(0) = 1, b(1) = phi. Then, for n>=1, L(n)= floor(b(n-1)) if n is odd, L(n) = ceil(b(n-1)), if n is even, with convergence. - _Richard R. Forberg_, Jan 20 2014

%F L(n) = round(sqrt(L(2n-1) + L(2n-2))). - _Richard R. Forberg_, Jun 24 2014

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

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

%p seq(simplify(2^n*(cos(Pi/5)^n+cos(3*Pi/5)^n)), n=0..36)

%t a[0] := 2; a[n] := Nest[{Last[ # ], First[ # ] + Last[ # ]} &, {2, 1}, n] // Last

%t Array[2 Fibonacci[ #+1] - Fibonacci[ # ] &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)

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

%t a = 1; lst = {2, a}; s = 5; Do[a = s - (a + 1); AppendTo[lst, a]; s += a, {n, 5!}]; lst (* _Vladimir Joseph Stephan Orlovsky_, Oct 27 2009 *)

%t LinearRecurrence[{1,1},{2,1},40] (* _Harvey P. Dale_, Sep 07 2013 *)

%o (MAGMA) [ Lucas(n) : n in [0..120]];

%o (PARI) {a(n) = if( n<0, (-1)^n * a(-n), if( n<2, 2-n, a(n-1) + a(n-2)))};

%o (PARI) {a(n) = if( n<0, (-1)^n * a(-n), polsym(x^2 - x - 1, n)[n+1])};

%o (PARI) {a(n) = real((2 + quadgen(5)) * quadgen(5)^n)};

%o (PARI) a(n)=fibonacci(n+1)+fibonacci(n-1) \\ _Charles R Greathouse IV_, Jun 11 2011

%o (PARI) polsym(1+x-x^2, 50) \\ _Charles R Greathouse IV_, Jun 11 2011

%o (Sage) [lucas_number2(n,1,-1) for n in range(37)] # _Zerinvary Lajos_, Jun 25 2008

%o (Haskell)

%o a000032 n = a000032_list !! n

%o a000032_list = 2 : 1 : zipWith (+) a000032_list (tail a000032_list)

%o -- _Reinhard Zumkeller_, Aug 20 2011

%Y Cf. A000204. A000045(n) = (2*L(n + 1) - L(n))/5.

%Y First row of array A103324.

%Y a(n) = A101220(2, 0, n), for n > 0.

%Y a(k) = A090888(1, k) = A109754(2, k) = A118654(2, k - 1), for k > 0.

%Y Cf. A131774, A001622, A006497, A080039, A049684 (summation of Fibonacci(4n+2)), A106291 (Pisano periods).

%K nonn,nice,easy,core

%O 0,1

%A _N. J. A. Sloane_, May 24 1994

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 November 28 09:37 EST 2014. Contains 250304 sequences.