0,1

This is also the Horadam sequence (2,1,1,1). - Ross La Haye (rlahaye(AT)new.rr.com), Aug 18 2003

For distinct primes p,q, L(p) is congruent 1 mod p, L(2p) is congruent 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.

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 (pbarry(AT)wit.ie), 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).

Suppose psi=ln(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 (Hieronymus.Fischer(AT)gmx.de), Apr 18 2007

Comments from John Blythe Dobson (j.dobson(AT)uwinnipeg.ca), Oct 02 2007, Oct 11 2007: (Start) 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.

The first six multiplication formulae are:

L(2n) = (L(n))^2 - 2*(-1)^n

L(3n) = (L(n))^3 - 3*((-1)^n)*L(n)

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

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

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

Generally, L(n) | L(mn) iff m is odd. (End)

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)

The comments submitted by Miklos Kristof on Mar 19 2007 for the Fibonacci numbers (A00045) contain four important identities which have close analogues in the Lucas numbers: For a>=b and odd b, L(a+b) + L(a-b) = 5*F(a)*F(b). For a>=b and even b, L(a+b) + L(a-b) = L(a)*L(b). For a>=b and odd b, L(a+b) - L(a-b) = L(a)*L(b). For a>=b and even b, L(a+b) - L(a-b) = 5*F(a)*F(b). - John Blythe Dobson (j.dobson(AT)uwinnipeg.ca), Nov 15 2007. 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 nu mbers repeat in a cycle of length 60.

Further comments from John Blythe Dobson (j.dobson(AT)uwinnipeg.ca), Nov 15 2007: (Start) The Lucas numbers satisfy remarkable difference equations, in some cases best expressed using Fibonacci numbers, of which representative examples are the following:

L(n) - L(n-3) = 2*L(n-2)

L(n) - L(n-4) = 5*F(n-2)

L(n) - L(n-6) = 4*L(n-3)

L(n) - L(n-12) = 40*F(n-6)

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

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

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)

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

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

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

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

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

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

A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80 (No. 1, 2007), 29-37.

Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.4.

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

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

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

G. Everest, Y. Puri and T. Ward, Integer sequences counting periodic points

R. Javonovic, Lucas Function Calculator

B. Kelly, Factorizations of Lucas numbers

Tanya Khovanova, Recursive Sequences

R. Knott, The Lucas numbers

R. Knott, The First 200 Lucas numbers and their factors

Hisanori Mishima, Factorizations of many number sequences

Hisanori Mishima, Factorizations of many number sequences

Hisanori Mishima, Factorizations of many number sequences

Hisanori Mishima, Factorizations of many number sequences

Hisanori Mishima, Factorizations of many number sequences

Zhi-Hong Sun, Congruences for Fibonacci Numbers [PDF] (Lecture notes, 2003)

Dan Sewell Ward, Modified Fibonacci Sequence.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Index entries for sequences related to Chebyshev polynomials.

Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)

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 (gerald.mcgarvey(AT)comcast.net), Dec 21 2007

G.f.: (2-x)/(1-x-x^2). L(n)=((1+sqrt(5))/2)^n + ((1-sqrt(5))/2)^n.

L(n) = L(n-1) + L(n-2) = (-1)^n L(-n).

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

L(n) = Fibonacci(2n)/Fibonacci(n) [ Jeff Burch (gburch(AT)erols.com) ]

L(n) = Fib(n) + 2*Fib(n-1) = Fib(n + 1) + Fib(n-1) - Henry Bottomley (se16(AT)btinternet.com), Apr 12 2000

a(n)=sqrt(F(n-1)^2+4*F(n)*F(n-2)) - Benoit Cloitre (benoit7848c(AT)orange.fr), Jan 06 2003

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 (pbarry(AT)wit.ie), Nov 15 2003

L(n)=2*Fib(n+1)-Fib(n) - Paul Barry (pbarry(AT)wit.ie), Mar 22 2004

a(n)=floor((phi)^n+(-phi)^(-n)) - Paul Barry (pbarry(AT)wit.ie), Mar 12 2005

Comments from Miklos Kristof (kristmikl(AT)freemail.hu), Mar 19 2007: (Start)

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

L(n+m)+(-1)^m*L(n-m)=L(n)*L(m)

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

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)

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)

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)

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)

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 (Hieronymus.Fischer(AT)gmx.de), May 02 2007

Starting (1, 3, 4, 7, 11,...) = row sums of triangle A131774. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jul 14 2007

a(n)=2*fibonacci(n-1)+fibonacci(n), n>=0 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 05 2007

a(n) = trace of the 2 X 2 matrix [0,1; 1,1]^n - Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 02 2008

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

a:=n->2*fibonacci(n-1)+fibonacci(n): seq(a(n), n=0..36); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 05 2007

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

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

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

(PARI) a(n)=if(n<0, (-1)^n*a(-n), if(n<2, 2-n, a(n-1)+a(n-2)))

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

(PARI) a(n)=real((2+quadgen(5))*quadgen(5)^n)

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

First row of array A103324.

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

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

Cf. A131774.

Adjacent sequences: A000029 A000030 A000031 this_sequence A000033 A000034 A000035

Sequence in context: A050041 A058658 A070827 this_sequence A061084 A055391 A134876

nonn,nice,easy,core

njas