login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

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

%I M0155 #689 Jan 24 2024 17:28:41

%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,54018521,87403803

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

%C Cf. A000204 for Lucas numbers beginning with 1.

%C Also the number of independent vertex sets and vertex covers for the cycle graph C_n for n >= 2. - _Eric W. Weisstein_, Jan 04 2014

%C Also the number of matchings in the n-cycle graph C_n for n >= 3. - _Eric W. Weisstein_, Oct 01 2017

%C Also the number of maximal independent vertex sets (and maximal vertex covers) for the n-helm graph for n >= 3. - _Eric W. Weisstein_, May 27 2017

%C Also the number of maximal independent vertex sets (and maximal vertex covers) for the n-sunlet graph for n >= 3. - _Eric W. Weisstein_, Aug 07 2017

%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_{k=0..ceiling((n - 1)/2)} P(3; n - 1 - k, k), 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) = A002390. 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 - 5*F(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 formulas 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 that have close analogs 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 formulas 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 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

%C Lucas numbers are invariant to the following transformation for all values of the integers j and n, including negative values, thus: L(n) = (L(j+n) + (-1)^n * L(j-n))/L(j). The same transformation applied to all sequences of the form G(n+1) = m * G(n) + G(n-1) yields Lucas numbers for m = 1, except where G(j) = 0, regardless of initial values which may be nonintegers. The corresponding sequences for other values of m are: for m = 2, 2*A001333; for m = 3, A006497; for m = 4, 2*A001077; for m = 5, A087130; for m = 6, 2*A005667; for m = 7, A086902. The invariant ones all have G(0) = 2, G(1) = m. A related family of sequences is discussed at A059100. - _Richard R. Forberg_, Nov 23 2014

%C If x=a(n), y=a(n+1), z=a(n+2), then -x^2 - z*x - 3*y*x - y^2 + y*z + z^2 = 5*(-1)^(n+1). - _Alexander Samokrutov_, Jul 04 2015

%C A conjecture on the divisibility of infinite subsequences of Lucas numbers by prime(n)^m, m >= 1, is given in A266587, together with the prime "entry points". - _Richard R. Forberg_, Dec 31 2015

%C A trapezoid has three lengths of sides in order L(n-1), L(n+1), L(n-1). For increasing n a very close approximation to the maximum area will have the fourth side equal to 2*L(n). For a trapezoid with sides L(n-1), L(n-3), L(n-1), the fourth side will be L(n). - _J. M. Bergot_, Mar 17 2016

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

%C Lucas numbers L(n) and Fibonacci numbers F(n), being related by the formulas F(n) = (F(n-1) + L(n-1))/2 and L(n) = 2 F(n+1) - F(n), are a typical pair of "autosequences" (see the link to OEIS Wiki). - _Jean-François Alcover_, Jun 09 2017

%C For n >= 3, the Lucas number L(n) is the dimension of a commutative Hecke algebra of affine type A_n with independent parameters. See Theorem 1.4, Corollary 1.5, and the table on page 524 in the link "Hecke algebras with independent parameters". - _Jia Huang_, Jan 20 2019

%C From _Klaus Purath_, Apr 19 2019: (Start)

%C While all prime numbers appear as factors in the Fibonacci numbers, this is not the case with the Lucas numbers. For example, L(n) is never divisible by the following prime numbers < 150: 5, 13, 17, 37, 53, 61, 73, 89, 97, 109, 113, 137, 149 ... See A053028. Conjecture: Three properties can be determined for these prime numbers:

%C First observation: The prime factors > 3 occur in the Fibonacci numbers with an odd index.

%C Second observation: These are the prime numbers p congruent to 2, 3 (modulo 5), which occur both in Fibonacci(p+1) and in Fibonacci((p+1)/2) as prime factors, or the prime numbers p congruent to 1, 4 (modulo 5), which occur both in Fibonacci((p-1)/2) and in Fibonacci((p-1)/(2^k)) with k >= 2.

%C Third observation: The Pisano period lengths of these prime numbers, given in A001175, are always divisible by 4, but not by 8. In contrast, those of the prime factors of Lucas numbers are divisible either by 2, but not by 4, or by 8. (See also comment in A053028 by N. J. A. Sloane, Feb 21 2004). (End)

%C L(n) is the sum of 4*k consecutive terms of the Fibonacci sequence (A000045) divided by Fibonacci(2*k): (Sum_{i=0..4*k-1, k>=1} F(n+i))/F(2*k) = L(n+2*k+1). Sequences extended to negative indices, following the rule a(n-1) = a(n+1) - a(n). - _Klaus Purath_, Sep 15 2019

%C If one forms a sequence (A) of the Fibonacci type with the initial values A(0) = A022095(n) and A(1) = A000285(n), then A(n+1) = L(n+1)^2 always applies. - _Klaus Purath_, Sep 29 2019

%C From _Kai Wang_, Dec 18 2019: (Start)

%C L((2*m+1)k)/L(k) = Sum_{i=0..m-1} (-1)^(i*(k+1))*L((2*m-2*i)*k) + (-1)^(m*k).

%C Example: k=5, m=2, L(5)=11, L(10)=123, L(20)=15127, L(25)=167761. L(25)/L(5) = 15251, L(20) + L(10) + 1 = 15127 + 123 + 1 = 15251.

%C (End)

%C From _Peter Bala_, Dec 23 2021: (Start)

%C The Gauss congruences a(n*p^k) == a(n*p^(k-1)) ( mod p^k ) hold for all prime p and positive integers n and k.

%C For a positive integer k, the sequence (a(n))n>=1 taken modulo k becomes a purely periodic sequence. For example, taken modulo 11, the sequence becomes [1, 3, 4, 7, 0, 7, 7, 3, 10, 2, 1, 3, 4, 7, 0, 7, 7, 3, 10, 2, ...], a periodic sequence with period 10. (End)

%C For any sequence with recurrence relation b(n) = b(n-1) + b(n-2), it can be shown that the recurrence relation for every k-th term is given by: b(n) = A000032(k) * b(n-k) + (-1)^(k+1) * b(n-2k), extending to negative indices as necessary. - _Nick Hobson_, Jan 19 2024

%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 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.

%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 C. N. Menhinick, The Fibonacci Resonance and other new Golden Ratio discoveries, Onperson, (2015), pages 200-206.

%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

%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="/A000032/b000032.txt">Table of n, a(n) for n = 0..4775</a> (terms 0..500 computed by N. J. A. Sloane)

%H A. Akbary and 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 [math.NT], 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 Ovidiu Bagdasar, Eve Hedderwick and Ioan-Lucian Popa, <a href="https://doi.org/10.1016/j.endm.2018.05.011">On the ratios and geometric boundaries of complex Horadam sequences</a>, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 63-70.

%H S. Barbero, U. Cerruti and N. Murru, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barbero2/barbero7.html">A Generalization of the Binomial Interpolated Operator and its Action on Linear Recurrent Sequences </a>, J. Int. Seq. 13 (2010) # 10.9.7, example 12.

%H Paul Barry, <a href="https://arxiv.org/abs/2004.04577">On a Central Transform of Integer Sequences</a>, arXiv:2004.04577 [math.CO], 2020.

%H A. T. Benjamin, A. K. Eustis and M. A. Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Shattuck/shattuck20.html">Compression Theorems for Periodic Tilings and Consequences</a>, JIS 12 (2009) 09.6.3.

%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 Kh. Bibak and M. H. Shirdareh Haghighi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Bibak/bibak4.html">Some Trigonometric Identities Involving Fibonacci and Lucas Numbers</a>, JIS 12 (2009) 09.8.4.

%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 Paula Burkhardt, Alice Zhuo-Yu Chan, Gabriel Currier, Stephan Ramon Garcia, Florian Luca and Hong Suh, <a href="http://arxiv.org/abs/1505.00018">Visual properties of generalized Kloosterman sums</a>, arXiv:1505.00018 [math.NT], 2015.

%H Frédéric Chapoton, <a href="https://arxiv.org/abs/1809.00575">A note on gamma triangles and local gamma vectors</a>, arXiv:1809.00575 [math.CO], 2018.

%H Charles Cratty, Samuel Erickson, Frehiwet Negass and Lara Pudwell, <a href="http://www.valpo.edu/mathematics-statistics/files/2015/07/Pattern-Avoidance-in-Double-Lists.pdf">Pattern Avoidance in Double Lists</a>, preprint, 2015.

%H M. Dekking, <a href="https://arxiv.org/abs/1906.08437">Base phi representations and golden mean beta-expansions</a>, arXiv:1906.08437 [math.NT], June 2019.

%H B. Demirturk and R. Keskin, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Demirturk/demirturk3.html">Integer Solutions of Some Diophantine Equations via Fibonacci and Lucas Numbers </a>, JIS 12 (2009) 09.8.7.

%H Wiktor Ejsmont and Franz Lehner, <a href="https://arxiv.org/abs/2002.06052">The Trace Method for Cotangent Sums</a>, arXiv:2002.06052 [math.CA], 2020.

%H C. Elsner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Elsner/elsner15.html">On Error Sums for Square Roots of Positive Integers with Applications to Lucas and Pell Numbers</a>, J. Int. Seq. 17 (2014) # 14.4.4

%H G. Everest, Y. Puri and T. Ward, <a href="http://arXiv.org/abs/math.NT/0204173">Integer sequences counting periodic points</a>, arXiv:math/0204173 [math.NT], 2012.

%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 Bakir Farhi, <a href="https://www.emis.de/journals/JIS/VOL22/Farhi/farhi19.html">Summation of Certain Infinite Lucas-Related Series</a>, J. Int. Seq., Vol. 22 (2019), Article 19.1.6.

%H Rigoberto Flórez, Robinson A. Higuita and Antara Mukherjee, <a href="https://arxiv.org/abs/1804.02481">The Geometry of some Fibonacci Identities in the Hosoya Triangle</a>, arXiv:1804.02481 [math.NT], 2018.

%H Robert Frontczak and Taras Goy, <a href="https://doi.org/10.15330/cmp.12.1.34-45">Mersenne-Horadam identities using generating functions</a>, Carpathian Math. Publ. (2020) Vol. 12, No. 1, 34-45.

%H Taras Goy and Mark Shattuck, <a href="https://www.pvamu.edu/aam/wp-content/uploads/sites/182/2019/12/05-R1320_AAM_Shattuck_MS_082819_Published_121119.pdf">Fibonacci and Lucas identities from Toeplitz-Hessenberg matrices</a>, Applications and Applied Mathematics: An International Journal, 14:2 (2019), 699-715.

%H R. P. Grimaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Grimaldi/grimaldi5.html">Tilings, Compositions, and Generalizations</a>, J. Int. Seq. 13 (2010), 10.6.5.

%H Tian-Xiao He, Peter J.-S. Shiue, Zihan Nie and Minghao Chen, <a href="https://doi.org/10.3934/era.2020057">Recursive sequences and Girard-Waring identities with applications in sequence transformation</a>, Electronic Research Archive (2020) Vol. 28, No. 2, 1049-1062.

%H A. M. Hinz, S. Klavžar, U. Milutinović and 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. and 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 Jia Huang, <a href="https://arxiv.org/abs/1405.1636">Hecke algebras with independent parameters</a>, arXiv preprint arXiv:1405.1636 [math.RT], 2014; Journal of Algebraic Combinatorics 43 (2016) 521-551.

%H R. Javonovic, <a href="http://web.archive.org/web/20140418224216/ http://milan.milanovic.org:80/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 Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/lucasNbs.html">The Lucas numbers</a>

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/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 [math.CO], 2011.

%H Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla and Fausto Jarquín-Zárate, <a href="https://arxiv.org/abs/1904.13002">The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d))</a>, arXiv:1904.13002 [math.NT], 2019.

%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 Matthew Macauley, Jon McCammond and Henning S. Mortveit, <a href="http://www.emis.de/journals/JACO/Volume33_1/hgv665924j44t770.html">Dynamics groups of asynchronous cellular automata</a>, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.

%H T. Mansour and 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 R. S. Melham, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Melham/melham3.html">Finite Reciprocal Sums Involving Summands that are Balanced Products of Generalized Fibonacci Numbers</a>, J. Int. Seq. 17 (2014) # 14.6.5.

%H R. Mestrovic, <a href="http://arxiv.org/abs/1409.3820">Lucas' theorem: its generalizations, extensions and applications (1878--2014)</a>, arXiv preprint arXiv:1409.3820 [math.NT], 2014.

%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 Mariana Nagy, Simon R. Cowell and Valeriu Beiu, <a href="https://arxiv.org/abs/1902.05944">Survey of Cubic Fibonacci Identities - When Cuboids Carry Weight</a>, arXiv:1902.05944 [math.HO], 2019.

%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 OEIS Wiki, <a href="https://oeis.org/wiki/Autosequence">Autosequence</a>

%H Arzu Özkoç, <a href="http://link.springer.com/article/10.1186/s13662-015-0486-7/fulltext.html">Some algebraic identities on quadra Fibona-Pell integer sequence</a>, Advances in Difference Equations, 2015, 2015:148.

%H Matthew Parker, <a href="https://oeis.org/A000032/a000032_25K.7z">The first 25K terms (7-Zip compressed file)</a>

%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 Yüksel Soykan, <a href="https://doi.org/10.13140/RG.2.2.19903.87207">On Hyperbolic Numbers With Generalized Fibonacci Numbers Components</a>, Zonguldak Bülent Ecevit University (Turkey, 2019).

%H Yüksel Soykan, <a href="https://doi.org/10.9734/jamcs/2020/v35i130241">Generalized Fibonacci Numbers: Sum Formulas</a>, Journal of Advances in Mathematics and Computer Science (2020) Vol. 35, No. 1, 89-104.

%H Yüksel Soykan, <a href="https://doi.org/10.9734/AJARR/2020/v9i130212">Closed Formulas for the Sums of Squares of Generalized Fibonacci Numbers</a>, Asian Journal of Advanced Research and Reports (2020) Vol. 9, No. 1, 23-39, Article no. AJARR.55441.

%H Yüksel Soykan, <a href="https://doi.org/10.9734/ACRI/2020/v20i230177">Closed Formulas for the Sums of Cubes of Generalized Fibonacci Numbers: Closed Formulas of Sum_{k=0..n} W_k^3 and Sum_{k=1..n} W_(-k)^3</a>, Archives of Current Research International (2020) Vol. 20, Issue 2, 58-69.

%H Yüksel Soykan, <a href="https://doi.org/10.34198/ejms.4220.297331">A Study on Generalized Fibonacci Numbers: Sum Formulas Sum_{k=0..n} k * x^k * W_k^3 and Sum_{k=1..n} k * x^k W_-k^3 for the Cubes of Terms</a>, Earthline Journal of Mathematical Sciences (2020) Vol. 4, No. 2, 297-331.

%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 Robin James Spivey, <a href="https://doi.org/10.7546/nntdm.2019.25.3.170-184">Close encounters of the golden and silver ratios</a>, Notes on Number Theory and Discrete Mathematics (2019) Vol. 25, No. 3, 170-184.

%H Zhi-Hong Sun, <a href="http://web.archive.org/web/20160729040644/ 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 L. C. Washington, <a href="https://www.fq.math.ca/Scanned/19-2/washington.pdf">Benford's Law for Fibonacci and Lucas numbers</a>, Fib. Quarterly, 19-2 1981, pp. 175-177.

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

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%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/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>

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

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lucas_number">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 Shaoxiong Yuan, <a href="https://arxiv.org/abs/1907.12459">Generalized Identities of Certain Continued Fractions</a>, arXiv:1907.12459 [math.NT], 2019.

%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 entries for linear recurrences with constant coefficients</a>, signature (1,1).

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

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

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

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

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

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

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

%F E.g.f.: 2*exp(x/2)*cosh(sqrt(5)*x/2). - _Len Smiley_, Nov 30 2001

%F L(n) = F(n) + 2*F(n - 1) = F(n + 1) + F(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*F(n + 1) - F(n). - _Paul Barry_, Mar 22 2004

%F a(n) = (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)) + 1/2) = 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 Let f(n) = phi^n + phi^(-n), then L(2n) = f(2n) and L(2n + 1) = f(2n + 1) - 2*Sum_{k>=0} C(k)/f(2n + 1)^(2k + 1) where C(n) are Catalan numbers (A000108). - _Gerald McGarvey_, Dec 21 2007, modified by _Davide Colazingari_, Jul 01 2016

%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(Fibonacci(n)*phi)), for n odd. - _Hieronymus Fischer_, Oct 20 2010

%F L(n) = ceiling(1/(1 - fract(Fibonacci(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)), n != 0. - _Gary Detlefs_, Dec 13 2010

%F L(n) = sqrt(A001254(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 = A014217(n) +((-1)^n+1)/2, where phi = A001622. - _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(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_{k=0..floor(n/2)} binomial(n - k,k)/(n - k), 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 L(n) = F(n) + F(n-1) + F(n-2) + F(n-3). - _Bob Selcoe_, Jun 17 2013

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

%F L(n) = (F(n+1)^2 - F(n-1)^2)/F(n) for n>0. - _Richard R. Forberg_, Nov 17 2014

%F L(n+2) = 1 + A001610(n+1) = 1 + Sum_{k=0..n} L(k). - _Tom Edgar_, Apr 15 2015

%F L(i+j+1) = L(i)*F(j) + L(i+1)*F(j+1) with F(n)=A000045(n). - _J. M. Bergot_, Feb 12 2016

%F a(n) = (L(n+1)^2 + 5*(-1)^n)/L(n+2). - _J. M. Bergot_, Apr 06 2016

%F Dirichlet g.f.: PolyLog(s,-1/phi) + PolyLog(s,phi), where phi is the golden ratio. - _Ilya Gutkovskiy_, Jul 01 2016

%F L(n) = F(n+2) - F(n-2). - _Yuchun Ji_, Feb 14 2016

%F L(n+1) = A087131(n+1)/2^(n+1) = 2^(-n)*Sum_{k=0..n} binomial(n,k)*5^floor((k+1)/2). - _Tony Foster III_, Oct 14 2017

%F L(2*n) = (F(k+2*n) + F(k-2*n))/F(k); n >= 1, k >= 2*n. - _David James Sycamore_, May 04 2018

%F From _Greg Dresden_ and _Shaoxiong Yuan_, Jul 16 2019: (Start)

%F L(3n + 4)/L(3n + 1) has continued fraction: n 4's followed by a single 7.

%F L(3n + 3)/L(3n) has continued fraction: n 4's followed by a single 2.

%F L(3n + 2)/L(3n - 1) has continued fraction: n 4's followed by a single -3. (End)

%F From _Klaus Purath_, Sep 15 2019: (Start)

%F All involved sequences extended to negative indices, following the rule a(n-1) = a(n+1) - a(n).

%F L(n) = (2*L(n+2) - L(n-3))/5.

%F L(n) = (2*L(n-2) + L(n+3))/5.

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

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

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

%F L(n) = 3*F(n-3) + 4*F(n-2).

%F L(n) = 4*F(n+1) - F(n+3).

%F L(n) = (F(n-k) + F(n+k))/F(k) with odd k>0.

%F L(n) = (F(n+k) - F(n-k))/F(k) with even k>0.

%F L(n) = A001060(n-1) - F(n+1).

%F L(n) = (A022121(n-1) - F(n+1))/2.

%F L(n) = (A022131(n-1) - F(n+1))/3.

%F L(n) = (A022139(n-1) - F(n+1))/4.

%F L(n) = (A166025(n-1) - F(n+1))/5.

%F The following two formulas apply for all sequences of the Fibonacci type.

%F (a(n-2*k) + a(n+2*k))/a(n) = L(2*k).

%F (a(n+2*k+1) - a(n-2*k-1))/a(n) = L(2*k+1). (End)

%F L(n) = F(n-k)*L(k+1) + F(n-k-1)*L(k), for all k >= 0, where F(n) = A000045(n). - _Michael Tulskikh_, Dec 06 2019

%F F(n+2*m) = L(m)*F(n+m) + (-1)^(m-1)*F(n) for all n >= 0 and m >= 0. - _Alexander Burstein_, Mar 31 2022

%F a(n) = i^(n-1)*cos(n*c)/cos(c) = i^(n-1)*cos(c*n)*sec(c), where c = Pi/2 + i*arccsch(2). - _Peter Luschny_, May 23 2022

%F From _Yike Li_ and _Greg Dresden_, Aug 25 20022: (Start)

%F L(2*n) = 5*binomial(2*n-1,n) - 2^(2*n-1) + 5*Sum_{j=1..n/5} binomial(2*n,n+5*j) for n>0.

%F L(2*n+1) = 2^(2n) - 5*Sum_{j=0..n/5} binomial(2*n+1,n+5*j+3). (End)

%F From _Andrea Pinos_, Jul 04 2023: (Start)

%F L(n) ~ Gamma(1/phi^n) + gamma.

%F L(n) = Re(phi^n + e^(i*Pi*n)/phi^n). (End)

%e G.f. = 2 + x + 3*x^2 + 4*x^3 + 7*x^4 + 11*x^5 + 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], {n, 0, 36}] (* _Zerinvary Lajos_, Jul 09 2009 *)

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

%t LucasL[Range[0, 20]] (* _Eric W. Weisstein_, Aug 07 2017 *)

%t CoefficientList[Series[(-2 + x)/(-1 + x + x^2), {x, 0, 20}], x] (* _Eric W. Weisstein_, Sep 21 2017 *)

%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

%o (Python)

%o def A000032_gen(): # generator of terms

%o a, b = 2, 1

%o while True:

%o yield a

%o a, b = b, a+b

%o it = A000032_gen()

%o A000032_list = [next(it) for _ in range(50)] # _Cole Dykstra_, Aug 02 2022

%o (Python)

%o from sympy import lucas

%o def A000032(n): return lucas(n) # _Chai Wah Wu_, Sep 23 2023

%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, A002878 (L(2n+1)), A005248 (L(2n)), A006497, A080039, A049684 (summation of Fibonacci(4n+2)), A106291 (Pisano periods), A057854 (complement), A354265 (generalized Lucas numbers).

%Y Cf. sequences with formula Fibonacci(n+k)+Fibonacci(n-k) listed in A280154.

%Y Subsequence of A047201.

%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 | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)