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

The number of sequences (s(0),s(1),...s(n)) such that 0<s(i)<5, |s(i)-s(i-1)|=1 and s(0)=1 is F(n+1); e.g. F(5+1) = 8 corresponds to 121212, 121232, 121234, 123212, 123232, 123234, 123432, 123434. - Clark Kimberling (ck6(AT)evansville.edu), Jun 22 2004. [Corrected by Neven Juric, Jan 09 2009]

Likewise F(6+1) = 13 corresponds to these thirteen sequences with seven numbers: 1212121, 1212123, 1212321, 1212323, 1212343, 1232121, 1232123, 1232321, 1232323, 1232343, 1234321, 1234323, 1234343. - Neven Juric, Jan 09, 2008.

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

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)gmail.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 (jvospost3(AT)gmail.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

a(n)= the number of different ways to run up a staircase with n steps, taking steps of odd sizes where the order is relevant and there is no other restriction on the number or the size of each step taken. - Mohammad K. Azarian (azarian(AT)evansville.edu), May 21 2008

Equals row sums of triangle A144152. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]

Contribution from Cino Hilliard (hillcino368(AT)gmail.com), Sep 15 2008: (Start)

Except for the initial term, the numerator of the convergents to the recursion x

= 1/(x+1). (End)

Contribution from Ross Drewe (rd(AT)labyrinth.net.au), Oct 05 2008: (Start)

F(n) is the number of possible binary sequences of length n that obey the

sequential construction rule: if last symbol is 0, add the complement (1);

else add 0 or 1. Here 0,1 are metasymbols for any 2-valued symbol set. This

rule has obvious similarities to JFJ Laros's rule, but is based on addition

rather than substitution and creates a tree rather than a single sequence. (End)

F(n) = PRODUCT_{k=1, (n-1)/2} (1 + 4*Cos^2 k*pi/n); where terms = roots to the Fibonacci product polynomials, A152063. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 22 2008]

Fp == 5^((p-1)/2) mod p, p = prime; [Schroeder, p. 90]. [From Gary W. Adamson & Alexander Povolotsky (qntmpkt(AT)yahoo.com), Feb 21 2009]

(Ln)^2 - 5*(Fn)^2 = 4*(-1)^n. Example: 11^2 - 5*5 = -4. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Mar 11 2009]

Output of Kasteleyn's formula for the number of perfect matchings of an m x n grid specializes to the Fibonacci sequence for m=2. [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

(Fib(n),Fib(n+4)) satisfies the Diophantine equation: X^2 + Y^2 - 7XY = 9*(-1)^n. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 06 2009]

Number of units of a(n) belongs to a periodic sequence: 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1.We conclude that a(n) and a(n+60) have the same number of units. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 05 2009]

(Fib(n),Fib(n+2)) satisfies the Diophantine equation: X^2 + Y^2 - 3XY = (-1)^n. [From Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 08 2009]

a(n+2)=A083662(A131577(n)). [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Sep 26 2009]

Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.

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.

N. D. Cahill and D. A. Narayan. "Fibonacci and Lucas Numbers as Tridiagonal Matrix Determinants". Fibonacci Quarterly, 42(3):216-221, 2004. V.E. Hoggatt and C.T. Long. "Divisibility Properties of Generalized Fibonacci Polynomials"; Fibonacci Quaterly, 12:113-130, 1974 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 22 2008]

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.

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

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.

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

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.

A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.

A. S. Posamentier & I. Lehmann, The Fabulous Fibonacci Numbers, Prometheus Books, Amherst, NY 2007.

Aimei Yu and Xuezheng Lv, "The Merrifield-Simmons indices and Hosoya indices of trees with k pendant vertices.", J. Math. Chem., Vol. 41 (2007), pp. 33-43. See page 35. - from Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Sep 01 2008

Manfred R. Schroeder, "Number Theory in Science and Communication", 5-th ed., Springer-Verlag, 2009 [From Gary W. Adamson & Alexander Povolotsky (qntmpkt(AT)yahoo.com), Feb 21 2009]

Mark A. Shattuck, Tiling proofs of some formulas for the Pell numbers of odd index, Integers, 9 (2009), 53-64.

P. W. Kasteleyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica, 27(1961), 1209-1225. [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

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

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

Joerg Arndt, Fxtbook

Author?, Fibonacci numbers from MathTV [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Aug 02 2009]

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 [Broken link]

E. S. Croot, Notes on Linear Recurrence Sequences

C. Dement, Posting to Math Forum.

R. M. Dickau, Fibonacci numbers

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

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

Tina Hill Janzen, Fibonacci sequence / Golden scale [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Aug 02 2009]

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

Tanya Khovanova, Recursive Sequences

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.

Hendrik Lenstra, Profinite Fibonacci Numbers

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

S. Plouffe, Fibonacci numbers [Contains the first 754965 terms]

S. Rabinowitz, Algorithmic Manipulation of Fibonacci Identities (1996). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 06 2008]

Marc Renault, Properties of the Fibonacci sequence under various moduli, MSc Thesis, Wake Forest U, 1996. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Feb 07 2009]

N. Renton, The fibonacci Series

B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.

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

N. N. Vorob'ev, Fibonacci numbers, Springer's Encyclopaedia of Mathematics. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 06 2008]

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

Index entries for two-way infinite sequences

Index entries for sequences related to linear recurrences with constant coefficients

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

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

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

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

F(n) = round(phi^n/sqrt(5)).

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+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(AT)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

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

a(n+1)=Sum_{k, 0<=k<=n} A109466(n,k)*(-1)^(n-k). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 26 2008]

Formula from Thomas Wieder (wieder.thomas(AT)t-online.de), Feb 25 2009:

a(n) = sum_{l_1=0}^{n+1} sum_{l_2=0}^{n}...sum_{l_i=0}^{n-i}...sum_{l_n=0}^{1}

delta(l_1,l_2,...,l_i,...,l_n)

where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i + l_(i+1) >= 2 for i=1..n-1

and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.

sage: taylor( mul((x^2)/(1-x^2-x^4) for i in xrange(0,1)),x,0,77)#solution>> x^2 + x^4 + 2*x^6 + 3*x^8 + 5*x^10 + 8*x^12 + 13*x^14 + 21*x^16 + 34*x^18 + 55*x^20 + 89*x^22 + 144*x^24 + 233*x^26 + 377*x^28 +....+ 514229*x^58 + 832040*x^60 + 1346269*x^62 +2178309*x^64 + 3524578*x^66 + 5702887*x^68 + 9227465*x^70 +14930352*x^72 + 24157817*x^74 + 39088169*x^76 etc... [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 01 2009]

2^n (\prod _{k=1}^n \sqrt[4]{\cos^2(k\pi/(n+1))+1/4})^2 (Kasteleyn's formula specialized) [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

Contribution from Cino Hilliard (hillcino368(AT)gmail.com), Sep 15 2008: (Start)

For x = 0,1,2,3,4 x=1/(x+1) = 1, 1/2, 2/3, 3/5, 5/8, These fractions have

numerators 1,1,2,3,5 the 2nd to 6-th entries in the sequence. (End)

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

sage: [lucas_number1(n, 1, -1) for n in xrange(0, 39)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 22 2009]

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

2^(n) Product[((Cos[Pi k/(n + 1)])^2 + (Cos[Pi 1/3])^2)^(1/4), {k, n}] Product[((Cos[Pi k/(n + 1)])^2 + (Cos[Pi 2/3])^2)^(1/4), {k, n}] (Kasteleyn's formula specialized) [From Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009]

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

sage: from sage.combinat.sloane_functions import recur_gen2 sage: it = recur_gen2(0, 1, 1, 1) sage: [it.next() for i in range(30)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 25 2008

(PARI) x=0; for(j=0, 100, x=1/(x+1); print1(numerator(x)", ")) [From Cino Hilliard (hillcino368(AT)gmail.com), Sep 15 2008]

Contribution from Cino Hilliard (hillcino368(AT)hotmail.com), Apr 29 2009: (Start)

(PARI) /*Generate Fibonnaci Sequence without arrays */

fib(n) =

{

local(a=0, b=1);

print1(a", "b", ");

for(x=3, n, c=a+b;

print1(c", ");

a=b; b=c;

);

}

(Sage) taylor( mul((x^2)/(1-x^2-x^4) for i in xrange(0, 1)), x, 0, 77)# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 01 2009]

Contribution from Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), Sep 29 2009: (Start)

(Haskell) Based on code

-- from http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

-- which also has other versions.

fib :: Int -> Integer

fib n = fibs !! n

.. where

.... fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

{- Example of use: map fib [0..38] -} (End)

Cf. A039834 (signed Fibonacci numbers).

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.

A144152 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]

A152063 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 22 2008]

Sequence in context: A132636 A152163 A039834 this_sequence A020695 A132916 A069041

Adjacent sequences: A000042 A000043 A000044 this_sequence A000046 A000047 A000048

core,nonn,easy,nice,new

N. J. A. Sloane (njas(AT)research.att.com).

Edited by Charles R Greathouse IV (charles.greathouse(AT)case.edu), Oct 30 2009