0,4

Also called Lam{\'e}'s sequence.

F(n+2) = number of binary sequences of length n that have no consecutive 0's.

F(n+2) = number of subsets of {1,2,...,n} that contain no consecutive integers.

F(n+1) = number of tilings of a 2 X n rectangle by 2 X 1 dominoes.

F(n+1) = number of matchings in a path graph on n vertices: F(5)=5 because the matchings of the path graph on the vertices A, B, C, D are the empty set, {AB}, {BC}, {CD}, and {AB, CD}. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 18 2001

F(n) = number of compositions of n+1 with no part equal to 1 [Grimaldi]

Positive terms are the solutions to z = 2xy^4 + (x^2)y^3 - 2(x^3)y^2 - y^5 - (x^4)y + 2y for x,y >= 0 (Ribenboim, page 193). When x=F(n), y=F(n + 1) and z>0 then z=F(n + 1).

For Fibonacci search see Knuth, Vol. 3; Horowitz and Sahni; etc.

F(n) is the diagonal sum of the entries in Pascal's triangle at 45 degrees slope. - Amarnath Murthy (amarnath_murthy(AT)yahoo.com), Dec 29 2001

F(n+1) is the number of perfect matchings in ladder graph L_n = P_2 X P_n, - Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002

F(n+1) = number of (3412,132)-, (3412,213)-, and (3412,321)-avoiding involutions in S_n.

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

An INVERT transform of A019590. INVERT([1,1,2,3,5,8,...]) gives A000129. INVERT([1,2,3,5,8,13,21,...]) gives A028859. - Antti Karttunen, Dec 12, 2003

Number of meaningful differential operations of the k-th order on the space R^3. - Branko Malesevic (malesevic(AT)kiklop.etf.bg.ac.yu), Mar 02 2004

F(n)=number of compositions of n-1 with no part greater than 2. Example: F(4)=3 because we have 3 = 1+1+1=1+2=2+1.

F(n) = number of compositions of n into odd parts; e.g. F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004

F(n) = number of binary words of length n beginning with 0 and having all runlengths odd; e.g. F(6) counts 010101, 010111, 010001, 011101, 011111, 000101, 000111, 000001. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004

F(n) = number of Catalan paths between the lines y = 0 and y = 3 from (0,0) to (n, GCD(n,2)). - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004

F(n) = number of (s(0),s(1),...s(n)) such that 0<s(i)<5, |s(i)-s(i-1)|=1, and s(0)=1; e.g. F(6) counts 121212, 121232, 121234, 123212,123232, 123234, 123432, 1223434. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004

A relationship between F(n) and the Mandelbrot set is discussed in the link 'Le nombre d'or dans l'ensemble de Mandelbrot' (in French). - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Sep 19 2004

F(n) = (1/(n-1)!) * [ n^(n-1) - { C(n-2,0) +4*C(n-2,1) +3*C(n-2,2) }*n^(n-2) + { 10*C(n-3,0) +49*C(n-3,1) +95*C(n-3,2) +83*C(n-3,3) +27*C(n-3,4) }*n^(n-3) - { 90*C(n-4,0) +740*C(n-4,1) +2415*C(n-4,2) +4110*C(n-4,3) +3890*C(n-4,4) +1950*C(n-4,5) +405*C(n-4,6) }*n^(n-4) + ..... ]. - Andre F. Labossiere (boronali(AT)laposte.net), Nov 24 2004

For n>0, the continued fraction for F(2n-1)*Phi = [F(2n);L(2n-1),L(2n-1),L(2n-1),...] and the continued fraction for F(2n)*Phi = [F(2n+1);L(2n)-2,L(2n)-2,L(2n)-2,...] where L(i) is the i-th Lucas number (A000204). - Clark Kimberling (ck6(AT)evansville.edu), Nov 28 2004

F(n) = number of permutations p of 1,2,3,...,n such that |k-p(k)|<=1 for k=1,2,...,n. (For <=2 and <=3, see A002524 and A002526.). - Clark Kimberling (ck6(AT)evansville.edu), Nov 28 2004

The ratios F(n+1)/F(n) for n>0 are the convergents to the simple continued fraction expansion of the golden section. - Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Dec 19 2004

Lengths of successive words (starting with a) under the substitution: {a -> ab, b -> a} - J. F. J. Laros (jlaros(AT)liacs.nl), Jan 22 2005

The Fibonacci sequence, like any additive sequence, naturally tends to be geometric with common ratio not a rational power of 10; consequently, for a sufficiently large number of terms, Benford's law of first significant digit {i.e., first digit 1 =< d =< 9 occurring with probability log_10(d+1) - log_10(d)} holds. - Lekraj Beedassy (blekraj(AT)yahoo.com), Apr 29 2005

a(n) = Sum(abs(A108299(n, k)): 0 <= k <= n). - Reinhard Zumkeller (reinhard.zumkeller(AT)lhsystems.com), Jun 01 2005

a(n) = A001222(A000304(n)).

Fib(n+2)=sum(k=0..n, binomial(floor((n+k)/2),k) ), row sums of A04685 4. - Paul Barry (pbarry(AT)wit.ie), Mar 11 2003

Number of order ideals of the "zig-zag" poset. See vol. 1, ch. 3, prob. 23 of Stanley. - Mitch Harris (Harris.Mitchell (AT) mgh.harvard.edu), Dec 27, 2005

F(n+1)/F(n) is also the Farey fraction sequence (see A097545 for explanation) for the golden ratio, which is the only number whose Farey fractions and continued fractions are the same. - Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), May 08 2006

a(n+2) is the number of paths through 2 plates of glass with n reflections (reflections occurring at plate/plate or plate/air interfaces). Cf. A006356-A006359. - Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu), Jul 06 2006

F(n+1) equals the number of downsets (i.e. decreasing subsets)of an n-element fence, i.e. an ordered set of height 1 on {1,2,...,n} with 1 > 2 < 3 > 4 < ... n and no other comparabilities. Alternatively, F(n+1) equals the number of subsets A of {1,2,...,n} with the property that, if k is in A, then the adjacent elements of {1,2,...,n} belong to A, i.e. both k - 1 and k + 1 are in A (provided they are in {1,2,...,n}). - Brian A. Davey (B.Davey(AT)latrobe.edu.au), Aug 25 2006

Number of Kekule structures in polyphenanthrenes. See the paper by Lukovits and Janezic for details. - Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Aug 22 2006

Inverse: With phi = (sqrt(5) + 1)/2, round(log_phi(sqrt((sqrt(5) a(n) + sqrt(5 a(n)^2 - 4))(sqrt(5) a(n) + sqrt(5 a(n)^2 + 4)))/2)) = n for n >= 3, obtained by rounding the arithmetic mean of the inverses given in A001519 and A001906. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007

Comment from Larry Gerstein (gerstein(AT)math.ucsb.edu), Mar 30 2007: A result of Jacobi from 1848 states that every symmetric matrix over a p.i.d. is congruent to a triple-diagonal matrix. Consider the maximal number T(n) of summands in the determinant of an n X n triple-diagonal matrix. This is the same as the number of summands in such a determinant in which the main-, sub-, and super-diagonal elements are all nonzero. By expanding on the first row we see that the sequence of T(n)'s is the Fibonacci sequence without the initial stammer on the 1's.

Suppose psi=ln(phi). We get the representation F(n)=(2/sqrt(5))*sinh(n*psi) if n is even; F(n)=(2/sqrt(5))*cosh(n*psi) if n is odd. There is a similar representation for Lucas numbers (A000032). Many Fibonacci formulas now easily follow from appropriate sinh- and cosh-formulas. For example: the de Moivre theorem (cosh(x)+sinh(x))^m=cosh(mx)+sinh(mx) produces L(n)^2+5F(n)^2=2L(2n) and L(n)F(n)=F(2n) (setting x=n*psi and m=2). - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Apr 18 2007

Inverse: floor(log_phi(sqr(5)*Fib(n))+0.5)=n, for n>1. Also for n>0, floor(1/2*log_phi(5*Fib(n)*Fib(n+1)))=n. Extension valid for integer n, except n=0,-1: floor(1/2*sign(Fib(n)*Fib(n+1))*log_phi|5*Fib(n)*Fib(n+1)|)=n {where sign(x) = sign of x}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), May 02 2007

F(n+2) = The number of Khalimsky-continuous functions with a two-point codomain. - Shiva Samieinia (shiva(AT)math.su.se), Oct 04 2007

From Kauffman and Lopes, Proposition 8.2, p.21: "The sequence of the determinants of the Fibonacci sequence of rational knots is the Fibonacci sequence (of numbers)." - Jonathan Vos Post (jvospost2(AT)yahoo.com), Oct 26 2007

This is a_1(n) in the Doroslovacki reference.

Let phi = 1.6180339...; then phi^n = (1/phi)*a(n) + a(n+1). Example: phi^4 = 6.8541019...= (.6180339...)*3 + 5. Also phi = 1/1 + 1/2 + 1/(2*5) + 1/(5*13) + 1/(13*34) + 1/(34*89),... - Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 15 2007

The sequence of first differences, fib(n+1)-fib(n), is essentailly the same sequence: 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... - Colm Mulcahy, Mar 03 2008

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

R. B. Banks, Slicing Pizzas, Racing Turtles, and Further Adventues in Applied Mathematics, Princeton Univ. Press, 1999. See p. 84.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

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

Majorie Bicknell and Verner E Hoggatt, Fibonacci's Problem Book, Fibonacci Association, San Jose, Calif., 1974.

S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.

Hongwei Chen, Evaluations of Some Variant Euler Sums, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.3.

B. A. Davey and H. A. Priestley, Introduction to Lattices and Order (2nd edition), CUP, 2002. (See Exercise 1.15.)

B. Davis, 'The law of first digits' in 'Science Today'(subsequently renamed '2001')March 1980 pp. 55, Times of India, Mumbai.

Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.

Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.

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

Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.

R. P. Grimaldi, Compositions without the summand 1, Proceedings Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001). Congr. Numer. 152 (2001), 33-43.

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

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

J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.

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

E. Horowitz and S. Sahni, Fundamentals of Data Structures, Computer Science Press, 1976; p. 338.

C. W. Huegy and D. B. West, A Fibonacci tiling of the plane, Discrete Math., 249 (2002), 111-116.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 78; Vol. 3, Section 6.2.1.

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

Lukovits et al., Nanotubes: Number of Kekule structures and aromaticity, J. Chem. Inf. Comput. Sci, (2003), vol. 43, 609-614. See eq. 2 on page 610.

I. Lukovits and D. Janezic, "Enumeration of conjugated circuits in nanotubes", J. Chem. Inf. Comput. Sci., vol. 44, 410-414 (2004). See Table 1 second column.

B. Malesevic: Some combinatorial aspects of differential operation composition on the space R^n, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 29-33.

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.

P. Ribenboim, The New Book of Prime Number Records, Springer, 1996.

J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.

A. M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.

J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 288.

A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.

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.

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. N. Vorob'ev, Chisla fibonachchi [Russian], Moscow, 1951. English translation, Fibonacci Numbers, Blaisdell, New York and London, 1961.

N. N. Vorobiev, Fibonacci Numbers, Birkhauser (Basel;Boston) 2002.

D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 61-7, Penguin Books 1987.

Tianping Zhang and Yuankui Ma, On Generalized Fibonacci Polynomials and Bernoulli Numbers, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.3.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 49.

N. J. A. Sloane, The first 500 Fibonacci numbers: Table of n, F(n) for n = 0..500

Joerg Arndt, Fxtbook

R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.

Tanya Khovanova, Recursive Sequences

Amazing Mathematical Object Factory, Information on the Fibonacci sequences

M. Anderson et al., The Fibonacci Series

Matt Anderson, Jeffrey Frazier, and Kris Popendorf, The Fibonacci series: the successor formula

Matt Anderson, Jeffrey Frazier, and Kris Popendorf,The Fibonacci series: the section index

P. G. Anderson, Fibonacci Facts

H. Bottomley and N. J. A. Sloane, Illustration of initial terms: the Fibonacci tree

M. Boulanger, Rabbit Puzzle [Broken link?]

Brantacan, Fibonacci Numbers

J. Britton & B. V. Eeckhout, Fibonacci Interactive

C. K. Caldwell, Fibonacci Numbers

C. K. Caldwell, The Prime Glossary, Fibonacci number

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

C. Conner, Fibonacci

E. S. Croot, Notes on Linear Recurrence Sequences

C. Dement, Posting to Math Forum.

R. M. Dickau, Fibonacci numbers

Enthios LLC, Fibonacci Primer

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

D. Foata and G.-N. Han, Nombres de Fibonacci et polynomes orthogonaux,

I. Galkin, "Fibonacci Numbers Spelled Out"

L. Goldsmith, The Fibonacci Numbers

A. P. Hillman & G. L. Alexanderson, Algebra Through Problem Solving, Chapter 2 pp. 11-16, The Fibonacci and Lucas Numbers

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 9

R. Javonovic, Fibonacci Function Calculator

R. Javonovic, The relations between the Fibonacci and the Lucas numbers

R. Jovanovic, First 70 Fibonacci numbers

S. Kak, The Golden Mean and the Physics of Aesthetics

Louis H. Kauffman and Pedro Lopes, Graded forests and rational knots, Oct 19, 2007.

B. Kelly, Fibonacci and Lucas factorizations

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

R. Knott, Fibonacci numbers and the golden section

R. Knott, Mathematics of the Fibonacci Series

R. Knott, Fibonacci numbers with tables of F(0)-F(500).

A. Krowne, PlanetMath.org, Fibonacci sequence

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

M. A. Lerma, Recurrence Relations

D. Litchfield, D. Goldenheim and C. H. Dietrich, Euclid, Fibonacci and Sketchpad, Math. Teacher, 90 (1997).

B. Malesevic, Some combinatorial aspects of differential operation composition on the space R^n .

D. Merlini, R. Sprugnoli and M. C. Verri, Strip tiling and regular grammars, Theoret. Computer Sci. 242, 1-2 (2000) 109-124.

D. Merrill, The Fib-Phi Link Page

Jean-Christophe Michel, Le nombre d'or dans l'ensemble de Mandelbrot (in French, 'The golden number in the Mandelbrot set')

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

H. Mishima, Factorizations of many number sequences

P. Moree, Convoluted convolved Fibonacci numbers

Newton's Institute, Posters in the London Underground

J. Patterson, The Fibonacci Sequence

Ivars Peterson, Fibonacci's Missing Flowers.

S. Plouffe, Project Gutenberg, The First 1001 Fibonacci Numbers

N. Renton, The fibonacci Series

E. S. Rowland, Fibonacci Sequence Calculator up to n=1474

Shiva Samieinia, Digital straight line segments and curves. Licentiate Thesis. Stockholm University, Department of Mathematics, Report 2007:6.

D. Schweizer, First 500 Fibonacci Numbers in blocks of 100.

S. Silvia, Fibonacci sequence

Jaap Spies, SAGE program for computing A000045

Z.-H. Sun, Congruences For Fibonacci Numbers

Roberto Tauraso, A New Domino Tiling Sequence, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.3.

Thesaurus.Maths.org, Fibonacci sequence

K. Tognetti, Fibonacci-His Rabbits and His Numbers and Kepler

Carl G. Wagner, Partition Statistics and q-Bell Numbers (q = -1), J. Integer Seqs., Vol. 7, 2004.

N. P. Watson, First 50 Fibonacci Numbers

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

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

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

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

Wikipedia, Fibonacci number

Willem's Fibonacci site, Fibonacci

G. Xiao, Numerical Calculator, To display F(n), for n up to 78365,operate on "fibonacci(n)"

Index entries for "core" sequences

Index entries for related partition-counting sequences

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

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

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

F(n+1) = Sum(0 <= j <= [n/2]; binomial(n-j, j))

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

[0 1; 1 1]^n [0 1] = [F(n); F(n+1)]

x | F(n) ==> x | F(kn).

A sufficient condition for F(m) to be divisible by a prime p is (p - 1) divides m, if p == 1 or 4 (mod 5); (p + 1) divides m, if p == 2 or 3 (mod 5); or 5 divides m, if p = 5. (This is essentially Theorem 180 in Hardy and Wright.) - Fred W. Helenius (fredh(AT)ix.netcom.com), Jun 29, 2001

a(n)=F(n) has the property: F(n)*F(m) + F(n+1)*F(m+1) = F(n+m+1) - Miklos Kristof (kristmikl(AT)freemail.hu), Nov 13 2003

Kurmang. Aziz. Rashid (Kurmang.Rashid(AT)Btopenworld.com), Feb 21 2004, makes 4 conjectures and gives 3 theorems:

Conjecture 1: for n>=2 sqrt{F(2n+1)+F(2n+2)+F(2n+3)+F(2n+4)+2*(-1)^n}={F(2n+1)+2*(-1)^n}/F(n-1). Conjecture 2: for n>=0, {F(n+2)* F(n+3)}-{F(n+1)* F(n+4)}+ (-1)^n = 0.

Conjecture 3: for n>=0, F(2n+1)^3 - F(2n+1)*[(2*A^2) -1] - [A + A^3]=0, where A= {F(2n+1)+sqrt{5*F(2n+1)^2 +4}}/2

Conjecture 4: for x>=5, if x is a Fibonacci number >= 5 then g*x*[{x+sqrt{5*(x^2) +- 4}}/2]*[2x+{{x+sqrt{5*(x^2) +- 4}}/2}]*[2x+{{3x+3*sqrt {5*(x^2) +- 4}}/2}]^2+[2x+{{x+sqrt{5*(x^2) +- 4}}/2}] +- x*[2x+{{3x+3*sqrt{5*(x^2) +- 4}}/2}]^2 -x*[2x+{{x+sqrt{5*(x^2) +- 4}}/2}]*[x+{{x+sqrt{5*(x^2) +- 4}}/2}]* [2x+ {{3x+3*sqrt{5*(x^2) +- 4}}/2}]^2= 0, where g = {1 + sqrt 5 /2}.

Theorem 1: for n>=0, {F(n+3)^ 2 - F(n+1)^ 2}/F(n+2)={F(n+3)+ F(n+1)}. Theorem 2: for n>=0, F(n+10) = 11* F(n+5) + F(n). Theorem 3: for n>=6, F(n) = 4* F(n-3) + F(n-6).

Conjecture 2 of Rashid is actually a special case of the general law F(n)*F(m) + F(n+1)*F(m+1) = F(n+m+1) (take n <- n+1 and m <- -(n+4) in this law). - Harmel Nestra (harmel.nestra(AT)ut.ee), Apr 22 2005

Conjecture: for all c such that 2-Phi <= c < 2*(2-Phi) we have F(n) = floor(Phi*a(n-1)+c) for n > 2 - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Jul 21 2004

|2*Fib(n) - 9*Fib(n+1)| = 4*A000032(n) + A000032(n+1). - Creighton Dement (creighton.k.dement(AT)uni-oldenburg.de), Aug 13 2004

For x > Phi, Sum n=0..inf F(n)/x^n = x/(x^2 - x - 1) - Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), Oct 27 2004

F(n) = round(phi^n/sqrt(5)). - Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), Dec 02 2004

F(n+1) = exponent of the n-th term in the series f(x, 1) determined by the equation f(x, y) = xy + f(xy, x). - Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Dec 19 2004

a(n-1)=sum(k=0, n, (-1)^k*binomial(n-ceil(k/2), floor(k/2))) - Benoit Cloitre (benoit7848c(AT)orange.fr), May 05 2005

F(n+1)=sum{k=0..n, binomial((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2}; - Paul Barry (pbarry(AT)wit.ie), Aug 28 2005

Fibonacci(n)=Product(1 + 4[cos(j*Pi/n)]^2, j=1..ceil(n/2)-1). [Bicknell and Hoggatt, pp. 47-48] - Emeric Deutsch, Oct 15 2006

F(n)=2^-(n-1)*sum{k=0..floor((n-1)/2), binomial(n,2*k+1)*5^k}; - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Feb 07 2006

a(n)=(b(n+1)+b(n-1))/n where {b(n)} is the sequence A001629 - Sergio Falcon (sfalcon(AT)dma.ulpgc.es), Nov 22 2006

F(n*m) = Sum{k = 0..m, binomial(m,k)*F(n-1)^k*F(n)^(m-k)*F(m-k)}. The generating function of F(n*m) (n fixed, m = 0,1,2...) is G(x) = F(n)*x / ((1-F (n-1)*x)^2-F(n)*x*(1-F(n-1)*x)-( F(n)*x)^2). E.g. F(15) = 610 = F(5*3) = binomial(3,0)* F(4)^0*F(5)^3*F(3) + binomial(3,1)* F(4)^1*F(5)^2*F(2) + binomial(3,2)* F(4)^2*F(5)^1*F(1) + binomial(3,3)* F(4)^3*F(5)^0*F(0) = 1*1*125*2 + 3*3*25*1 + 3*9*5*1 + 1*27*1*0 = 250 + 225 + 135 + 0 = 610 - Miklos Kristof, Feb 12 2007

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

Let L(n)=A000032=Lucas numbers. Then:

For a>=b and odd b F(a+b)+F(a-b)=L(a)*F(b).

For a>=b and even b F(a+b)+F(a-b)=F(a)*L(b).

For a>=b and odd b F(a+b)-F(a-b)=F(a)*L(b).

For a>=b and even b F(a+b)-F(a-b)=L(a)*F(b).

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

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

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

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

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

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

Fib(n)=b(n)+(p-1)*sum{1<k<n, floor(b(k)/p)*Fib(n-k+1)} where b(k) is the digital sum analogue of the Fibonacci recurrence, defined by b(k)=ds_p(b(k-1))+ds_p(b(k-2)), b(0)=0, b(1)=1, ds_p=digital sum base p. Example for base p=10: Fib(n)=A010077(n)+9*sum{1<k<n, A059995(A010077(k))*Fib(n-k+1)}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jul 01 2007

Fib(n)=b(n)+p*sum{1<k<n, floor(b(k)/p)*Fib(n-k+1)} where b(k) is the digital product analogue of the Fibonacci recurrence, defined by b(k)=dp_p(b(k-1))+dp_p(b(k-2)), b(0)=0, b(1)=1, dp_p=digital product base p. Example for base p=10: Fib(n)=A074867(n)+10*sum{1<k<n, A059995(A074867(k))*Fib(n-k+1)}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jul 01 2007

a(n) = denominator of continued fraction [1,1,1,...], (with n ones); e.g. 2/3 = continued fraction [1,1,1]; where barover[1] = [1,1,1...] = .6180339,... - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 29 2007

F(n + 3) = 2F(n + 2) - F(n), F(n + 4) = 3F(n + 2) - F(n), F(n + 8) = 7F(n + 4) - F(n), F(n + 12) = 18F(n + 6) - F(n). - Paul Curtz (bpcrtz(AT)free.fr), Feb 01 2008

1 = 1/(1*2) + 1/(1*3) + 1/(2*5) + 1/(3*8) + 1/(5*13) + ... = 1/2 + 1/3 + 1/10 + 1/24 + 1/65 + 1/168 + ...; where A059929 = (0, 2, 3, 10, 24, 65, 168,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 16 2008

a(2^n) = prod{i=0}^{n-2}B(i) where B(i) is A001566. Example 3*7*47 = Fib(16) - Kenneth J Ramsey (Ramsey2879(AT)msn.com), Apr 23 2008

with(combinat): A000045 := proc(n) fibonacci(n); end;

ZL:=[S, {a = Atom, b = Atom, S = Prod(X, Sequence(Prod(X, b))), X = Sequence(b, card >= 1)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=0..38); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 04 2008

spec := [ B, {B=Sequence(Set(Z, card>1))}, unlabeled ]: seq(combstruct[count](spec, size=n), n=1..39); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 04 2008

Table[ Fibonacci[ k ], {k, 1, 50} ]

(AXIOM) [fibonacci(n) for n in 0..50]

(MAGMA) F := func< n | Fibonacci(n) >;

(PARI) a(n)=fibonacci(n)

(PARI) a(n)=imag(quadgen(5)^n)

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

# Python program from Jaap Spies, Jan 05, 2007 (Change leading dots to blanks.)

def fib():

... """

....... generates an "infinity" of Fibonacci numbers,

....... starting with 1

... """

... x, y = 0, 1

... while 1:

....... x, y = y, x+y

....... yield x

................

f = fib()

a = [f.next() for i in range(1000)] # 1000 or more

a.insert(0, 0)

................

def A000045(n):

... """ returns Fibonacci number with index n, offset 0, 4 """

... return a[n]

................

def A000045_list(N):

... """ returns a list of the first n Fibonacci numbers """

... return a[:N]

................

# (SAGE) Demonstration program from Jaap Spies:

# To see which functions are available type: sloane.A[tab]

# All builtin SAGE programs are called the same way:

# a = sloane.A000045; a # This returns the name of the sequence

# a(n) # This returns the n-th number of the sequence:

# a.list(n) # This returns a list of the first n numbers:

# Copy and paste the following into a worksheet or the interpreter:

a = sloane.A000045; print a

print a(0)

print a(1)

print a(2)

print a(38)

print a.list(39)

Cf. A000213, A000288, A000322, A000383, A060455, A030186, A039834, A020695, A020701, A071679.

Cf. A099731, A100492, A094216, A094638, A000108, A101399, A101400.

First row of array A103323. Second row of array A099390.

Row 2 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).

a(n) = A094718(4, n). a(n) = A101220(0,j,n).

A000032(n)=F(n+1)+F(n-1). Cf. A060441.

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

Cf. A059929.

Adjacent sequences: A000042 A000043 A000044 this_sequence A000046 A000047 A000048

Sequence in context: A107358 A132636 A039834 this_sequence A134805 A020695 A132916

core,nonn,easy,nice,new

njas