This site is supported by donations to The OEIS Foundation.

Now is the time of year when we ask all users of the OEIS for their annual support.
Click here to donate to the OEIS Foundation using PayPal or in other ways.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000045 Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. (Formerly M0692 N0256) 3033
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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, Jun 18 2001 F(n) = number of compositions of n+1 with no part equal to 1. [Cayley, Grimaldi] Positive terms are the solutions to z = 2*x*y^4 + (x^2)*y^3 - 2*(x^3)*y^2 - y^5 - (x^4)*y + 2*y 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, 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, 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, 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, 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, Jun 22 2004 The number of sequences (s(0),s(1),...s(n)) such that 00, 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)-1;1,L(2n)-2,1,L(2n)-2,...]. Also true: F(2n)*Phi=[F(2n+1);-L(2n),L(2n),-L(2n),L(2n),...] where L(i) is the i-th Lucas number (A000204).... - Clark Kimberling, Nov 28 2004. [Corrected by Hieronymus Fischer, Oct 20 2010] 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, 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, 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, Apr 29 2005 a(n) = Sum(abs(A108299(n, k)): 0 <= k <= n). - Reinhard Zumkeller, Jun 01 2005 a(n) = A001222(A000304(n)). Fib(n+2)=sum(k=0..n, binomial(floor((n+k)/2),k)), row sums of A046854. - Paul Barry, Mar 11 2003 Number of order ideals of the "zig-zag" poset. See vol. 1, ch. 3, prob. 23 of Stanley. - Mitch Harris, 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, 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, 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 an odd 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 Davey, Aug 25 2006 Number of Kekule structures in polyphenanthrenes. See the paper by Lukovits and Janezic for details. - Parthasarathy Nambi, 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 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. - Larry Gerstein (gerstein(AT)math.ucsb.edu), Mar 30 2007 Suppose psi=log(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, Apr 18 2007 Inverse: floor(log_phi(sqrt(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, 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, 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, Dec 15 2007 The sequence of first differences, fib(n+1)-fib(n), is essentially 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, May 21 2008 Equals row sums of triangle A144152. - Gary W. Adamson, Sep 12 2008 Except for the initial term, the numerator of the convergents to the recursion x = 1/(x+1). - Cino Hilliard, Sep 15 2008 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. - Ross Drewe, Oct 05 2008 F(n) = PRODUCT_{k=1, (n-1)/2} (1 + 4*cos^2 k*Pi/n); where terms = roots to the Fibonacci product polynomials, A152063. - Gary W. Adamson, Nov 22 2008 Fp == 5^((p-1)/2) mod p, p = prime; [Schroeder, p. 90]. - Gary W. Adamson & Alexander R. Povolotsky, Feb 21 2009 (Ln)^2 - 5*(Fn)^2 = 4*(-1)^n. Example: 11^2 - 5*5 = -4. - Gary W. Adamson, 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. - 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. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 06 2009 (Fib(n),Fib(n+2)) satisfies the Diophantine equation: X^2 + Y^2 - 3XY = (-1)^n. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 08 2009 a(n+2)=A083662(A131577(n)). - Reinhard Zumkeller, Sep 26 2009 Difference between of number of closed walks of length n+1 from a node on a pentagon and number of walks of length n+1 between two adjacent nodes on a pentagon. - Henry Bottomley, Feb 10 2010 F(n+1) = number of Motzkin paths of length n having exactly one weak ascent. A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. A weak ascent in a Motzkin path is a maximal sequence of consecutive U and H steps. Example: a(5)=5 because we have (HHHH), (HHU)D, (HUH)D, (UHH)D, and (UU)DD (the unique weak ascent is shown between parentheses; see A114690). - Emeric Deutsch, Mar 11 2010 (F(n-1)+F(n+1))^2 - 5F(n-2)*F(n+2) = 9*(-1)^n. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Mar 31 2010 Pinter and Ziegler show that essentially the Fibonacci sequence is the unique binary recurrence which contains infinitely many three-term arithmetic progressions. A criterion for general linear recurrences having infinitely many three-term arithmetic progressions is also given. - Jonathan Vos Post, May 22 2010 F(n+1) = number of paths of length n starting at initial node on the path graph P_4. - Johannes W. Meijer, May 27 2010 F(k) = Number of cyclotomic polynomials in denominator of generating function for number of ways to place k nonattacking queens on an n X n board. - Vaclav Kotesovec, Jun 07 2010 As n-> inf., (a(n)/a(n-1) - a(n-1)/a(n)) tends to 1.0. Example: a(12)/a(11) - a(11)/a(12) = 144/89 - 89/144 = .99992197.... - Gary W. Adamson, Jul 16 2010 From Hieronymus Fischer, Oct 20 2010: (Start) Fibonacci numbers are those numbers m such that m*phi is closer to an integer than k*phi for all k, 1<=ka(n) such that m*phi is closer to an integer than a(n)*phi. For all numbers 1<=k |Fib(n)*phi-round(Fib(n)*phi)| holds. Fib(n)*phi - round(Fib(n)*phi) = -((-phi)^(-n)), for n>1. fract(0.5+Fib(n)*phi) = 0.5 -(-phi)^(-n), for n>1. fract(Fib(n)*phi) = (1/2)*(1+(-1)^n)-(-phi)^(-n), n>1. Inverse: n = -log_phi |0.5-fract(0.5+Fib(n)*phi)|. (End) F(A001177(n)*k) mod n = 0, for any integer k. - Gary Detlefs, Nov 27 2010 F(n+k)^2-F(n)^2 = F(k)*F(2n+k), for even k. - Gary Detlefs, Dec 04 2010 F(n+k)^2+F(n)^2 = F(k)*F(2n+k), for odd k. - Gary Detlefs, Dec 04 2010 "Even the Fibonacci sequence - 1,1,2,3,5,8,13 - follows Benford's law." See Pickover. F(n) = round(phi* F(n-1)) for n>1. - Joseph P. Shoulak, Jan 13 2012 For n > 0: a(n) = length of n-th row in Wythoff array A003603. - Reinhard Zumkeller, Jan 26 2012 From Bridget Tenner, Feb 22, 2012: (Start) The number of free permutations of [n]. The number of permutations of [n] for which s_k in supp(w) implies s_{k+-1} not in supp(w). The number of permutations of [n] in which every decomposition into length(w) reflections is actually composed of simple reflections. (End) The sequence F(n+1)^(1/n) is increasing. The sequence F(n+2)^(1/n) is decreasing. - Thomas Ordowski, Apr 19 2012 Two conjectures: For n>1, F(n+2)^2 mod F(n+1)^2 = F(n)*F(n+1)-(-1)^n. For n>0, (F(2n)+F(2n+2))^2 = F(4n+3)+sum_{k=2..2n}F(2k). - Alex Ratushnyak, May 06 2012 The relationship: INVERT transform of (1,1,0,0,0,...) = (1, 2, 3, 5, 8,...), while the INVERT transform of (1,0,1,0,1,0,1,...) = (1, 1, 2, 3, 5, 8,...) is equivalent to: The numbers of compositions using parts 1 and 2 is equivalent to the numbers of compositions using parts == 1 mod 2 (i.e., the odd integers). Generally, the numbers of compositions using parts 1 and k is equivalent to the numbers of compositions of (n+1) using parts 1 mod k. Cf. A000930 for k = 3 and A003269 for k = 4. Example: for k = 2, n = 4 we have the compositions (22; 211, 121; 112; 1111) = 5; but using parts 1 and 3 we have for n = 5: (311, 131, 113, 11111, 5) = 5. - Gary W. Adamson, Jul 05 2012 The sequence F(n) is the binomial transformation of the alternating sequence (-1)^(n-1)*F(n), whereas the sequence F(n+1) is the binomial transformation of the alternating sequence (-1)^n*F(n-1). Both of these facts follow easily from the equalities a(n;1)=F(n+1) and b(n;1)=F(n) where a(n;d) and b(n;d) are so-called "delta-Fibonacci" numbers as defined in comments to A014445 (see also Witula et al.'s papers). - Roman Witula, Jul 24 2012 F(n) is the number of different (n-1)-digit binary numbers such that all substrings of length > 1 have at least one digit equal to 1. Example: for n = 5 there are 8 binary numbers with n - 1 = 4 digits (1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111), only the F(n) = 5 numbers 1010, 1011, 1101, 1110 and 1111 have the desired property. - Hieronymus Fischer, Nov 30 2012 For positive n, F(n+1) equals the determinant of the n X n tridiagonal matrix with 1's along the main diagonal, i's along the superdiagonal and along the subdiagonal where i = sqrt(-1). Example: Det([1,i,0,0; i,1,i,0; 0,i,1,i; 0,0,i,1]) = F(4+1) = 5. - Philippe Deléham, Feb 24 2013 For n>=1, number of compositions of n where there is a drop between every second pair of parts, starting with the first and second part; see example. Also, a(n+1) is the number of compositions where there is a drop between every second pair of parts, starting with the second and third part; see example. - Joerg Arndt, May 21 2013 Central terms of triangles in A162741 and A208245, n > 0. - Reinhard Zumkeller, Jul 28 2013 For n>=4, F(n-1) is the number of simple permutations in the geometric grid class given in A226433. - Jay Pantone, Sep 08 2013 From Wolfdieter Lang, Oct 01 2013: (Start) a(n) are the pentagon (not pentagonal) numbers because the algebraic degree 2 number rho(5) = 2*cos(pi/5) = phi (golden section), the length ratio diagonal/side in a pentagon, has minimal polynomial C(5,x) = x^2 - x - 1 (see A187360, n=5), hence rho(5)^n = a(n-1)*1 + a(n)*rho(5), n >= 0, in the power basis of the algebraic number field Q(rho(5)). One needs a(-1) = 1 here. See also the P. Steinbach reference under A049310. (End) A010056(a(n)) = 1. - Reinhard Zumkeller, Oct 10 2013 REFERENCES 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. Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7,  No. 38, 2012, pp. 1871-1876. Mohammad K. Azarian, Fibonacci Identities as Binomial Sums II, International Journal of Contemporary Mathematical Sciences, Vol. 7,  No. 42, 2012, pp. 2053-2059. Mohammad K. Azarian, Identities Involving Lucas or Fibonacci and Lucas Numbers as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 45, 2012, pp. 2221-2227. P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 70. R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 84. 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. J. Bodeen, S. Butler, T. Kim, X. Sun, S. Wang, Tiling a strip with triangles, 2013; http://orion.math.iastate.edu/butler/papers/triangle_tilings.pdf 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. A. Cayley, Theorems in Trigonometry and on Partitions, Messenger of Mathematics, 5 (1876), pp. 164,188 = Mathematical Papers Vol. 10, n. 634, p. 16. Hongwei Chen, Evaluations of Some Variant Euler Sums, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.3. D. Chmiela, K. Kaczmarek, R. Witula, Binomials Transformation Formulae of Scaled Fibonacci Numbers (submitted 2012). 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. Helaman and Claire Ferguson, "Celebrating Mathematics in Stone and Bronze", Notices of the American Mathematical Society, 57 (2010), 840-850. See page 844. 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. H. Halberstam and K. F. Roth, Sequences, Oxford, 1966; see Appendix. S. Happersett, "Mathematical meditations", Journal of Mathematics and the Arts, 1 (2007), 29 - 33. 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 and C. T. Long. "Divisibility Properties of Generalized Fibonacci Polynomials"; Fibonacci Quarterly, 12:113-130, 1974. 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. 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. M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 63. 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. G. Mantel, Resten van wederkeerige Reeksen, Nieuw Archief v. Wiskunde, 2nd series, I (1894), 172-184. A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469. Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 49. Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 274. A. S. Posamentier & I. Lehmann, The Fabulous Fibonacci Numbers, Prometheus Books, Amherst, NY 2007. 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. Manfred R. Schroeder, "Number Theory in Science and Communication", 5th ed., Springer-Verlag, 2009 Mark A. Shattuck, Tiling proofs of some formulas for the Pell numbers of odd index, Integers, 9 (2009), 53-64. Simson, [No first name given], An explanation of an obscure passage in Albert Girard's Commentary ..., Phil. Trans. Royal Soc., 10 (1753), 430-433. 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). 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. R. Witula, D. Slota, $\delta$-Fibonacci Numbers, Appl. Anal. Discrete Math., 3 (2009), 310-329. Roman Witula, Damian Slota and Edyta Hetmaniok, Bridges between different known integer sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 255-263; http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from255to263.pdf. LINKS 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 J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178. 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. H. Bottomley and N. J. A. Sloane, Illustration of initial terms: the Fibonacci tree Brantacan, Fibonacci Numbers J. Britton & B. V. Eeckhout, Fibonacci Interactive N. D. Cahill, J. R. D'Errico, J. P. Spence, Complex factorizations of the Fibonacci and Lucas numbers, Fib. Quart. 41 (2003) 13 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. 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 G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255. MR1990179 Philipp Fahr and Claus Michael Ringel, Categorification of the Fibonacci Numbers Using Representations of Quivers John Farrier, Fibonacci Pigeons [From Sarah Spolaor, Sep 30 2010] Helaman and Claire Ferguson, Celebrating Mathematics in Stone and Bronze D. Foata and G.-N. Han, Nombres de Fibonacci et polynomes orthogonaux, I. Galkin, "Fibonacci Numbers Spelled Out" Dale Gerdemann, Video of Fibonacci tree Dale Gerdemann, Video of Fibonacci tree(s) (another version) C. J. Glasby, S. P. Glasby, F. Pleijel, Worms by number, Proc. Roy. Soc. B, Proc. Biol. Sci. 275 (1647) (2008) 2071-2076. L. Goldsmith, The Fibonacci Numbers M. Griffiths, A Restricted Random Walk defined via a Fibonacci Process, Journal of Integer Sequences, Vol. 14 (2011), #11.5.4. Guo-Niu Han, Enumeration of Standard Puzzles S. Happersett, Mathematical meditations A. P. Hillman & G. L. Alexanderson, Algebra Through Problem Solving, Chapter 2 pp. 11-16, The Fibonacci and Lucas Numbers A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 12. Book's website INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 9 Tina Hill Janzen, Fibonacci sequence / Golden scale Q.-H. Hou, Z.-W. Sun and H.-M. Wen, On monotonicity of some combinatorial sequences, arXiv:1208.3903. R. Javonovic, Fibonacci Function Calculator R. Jovanovic, First 70 Fibonacci numbers S. Kak, The Golden Mean and the Physics of Aesthetics, arXiv:physics/0411195 Louis H. Kauffman and Pedro Lopes, Graded forests and rational knots, arXiv:0710.3765 Blair 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 A. Krowne, PlanetMath.org, Fibonacci sequence 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). Charles P. McKeague, Fibonacci numbers from MathTV 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') Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013 H. Mishima, Factorizations of Fibonacci numbers n=1..100, n=101..200, n=201..300, n=301..400, n=401..480 P. Moree, Convoluted convolved Fibonacci numbers Newton's Institute, Posters in the London Underground 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. J. Patterson, The Fibonacci Sequence. T. K. Petersen and B. E. Tenner, The depth of a permutation, arXiv:1202.4765v1 [math.CO]. Ivars Peterson, Fibonacci's Missing Flowers. Akos Pinter and Volker Ziegler, On Arithmetic Progressions in Recurrences - A new characterization of the Fibonacci sequence, arXiv:1005.3624 Simon Plouffe, Project Gutenberg, The First 1001 Fibonacci Numbers S. Rabinowitz, Algorithmic Manipulation of Fibonacci Identities (1996). Arulalan Rajan, R. Vittal Rao, Ashok Rao and H. S. Jamadagni, Fibonacci Sequence, Recurrence Relations, Discrete Probability Distributions and Linear Convolution, Arxiv preprint arXiv:1205.5398, 2012. - From N. J. A. Sloane, Oct 23 2012 Marc Renault, Properties of the Fibonacci sequence under various moduli, MSc Thesis, Wake Forest U, 1996. 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. 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. S. Silvia, Fibonacci sequence Jaap Spies, SAGE program for computing A000045 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. 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 C. Vila, Nature by numbers (animation). Christobal Vila, Nature Numbers (Video related to Fibonacci numbers) N. N. Vorob'ev, Fibonacci numbers, Springer's Encyclopaedia of Mathematics. Carl G. Wagner, Partition Statistics and q-Bell Numbers (q = -1), J. Integer Seqs., Vol. 7, 2004. Eric Weisstein's World of Mathematics, Fibonacci Number, Double-Free Set, Fibonacci n-Step Number, Resistor Network Wikipedia, Fibonacci number Willem's Fibonacci site, Fibonacci 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. Tianping Zhang and Yuankui Ma, On Generalized Fibonacci Polynomials and Bernoulli Numbers, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.3. FORMULA G.f.: x / (1 - x - x^2). G.f.: Sum_{n>=0} x^n * Product_{k=1..n} (k + x)/(1 + k*x). - Paul D. Hanna, Oct 26 2013 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)). This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m). - Michael Somos, Apr 07 2012 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, Nov 13 2003 Kurmang. Aziz. Rashid, 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 2 of Rashid Kurmang simplified:  F(n)*F(n+3) = F(n+1)*F(n+2)-(-1)^n. Follows from d'Ocagne's identity: m=n+2. - Alex Ratushnyak, May 06 2012 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, 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, 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, Dec 19 2004 a(n-1)=sum(k=0, n, (-1)^k*binomial(n-ceil(k/2), floor(k/2))). - Benoit Cloitre, May 05 2005 F(n+1)=sum{k=0..n, binomial((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2}. - Paul Barry, 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, 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 From Miklos Kristof, 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= 2 for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. 2^n (\prod _{k=1}^n \sqrt[4]{\cos^2(k\pi/(n+1))+1/4})^2 (Kasteleyn's formula specialized). - Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009 a(n+1) =sum_{k=floor[n/2] mod 5} C(n,k) - sum_{k=floor[(n+5)/2] mod 5} C(n,k) =A173125(n)-A173126(n) =|A054877(n)-A052964(n-1)|. - Henry Bottomley, Feb 10 2010 If p[i]=modp(i,2) and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, May 02 2010 Limit(F(k+n)/F(k), k = infinity) = (L(n) + F(n)*sqrt(5))/2 with the Lucas numbers L(n)= A000032(n). - Johannes W. Meijer, May 27 2010 For n>=1, F(n)=round(log_2(2^{\phi*F(n-1)}+2^{\phi*F(n-2)})), where \phi is Golden ratio. - Vladimir Shevelev, Jun 24 2010, Jun 27 2010 For n>=1, a(n+1)=ceil(phi*a(n)), if n is even and a(n+1)=floor(phi*a(n)), if n is odd (phi=golden ratio). - Vladimir Shevelev, Jul 01 2010 a(n)=2*a(n-2)+a(n-3), n>2. - Gary Detlefs, Sep 08 2010 a(2^n)=Prod{i=0,...,n-1} A000032(2^i). - Vladimir Shevelev, Nov 28 2010 a(n)^2 - a(n-1)^2 = a(n+1)*a(n-2), see A121646. a(n) = sqrt((-1)^k*(a(n+k)^2-a(k)*a(2n+k))), for any k. - Gary Detlefs, Dec 03 2010 F(2*n) = F(n+2)^2 - F(n+1)^2 - 2*F(n)^2. - Richard R. Forberg, Jun 04 2011 From Artur Jasinski, Nov 17 2011: (Start)   (-1)^(n+1) = F(n)^2 + F(n)*F(1+n) - F(1+n)^2.   F(n) = -F(n+2)(-2+(F(n+1))^4 + 2*(F(n+1)^3*F(n+2)) - (F(n+1)*F(n+2))^2 2*F(n+1)(F(n+2))^3 + (F(n+2))^4)-F(n+1). (End) F(n) = 1 + sum_{x=1..n-2} F(x). - Joseph P. Shoulak, Feb 05 2012 F(n) = 4*F(n-2) - 2*F(n-3) - F(n-6). - Gary Detlefs, Apr 01 2012 F(n) = round(phi^(n+1)/(phi+2)). - Thomas Ordowski, Apr 20 2012 From Sergei N. Gladkovskii, Jun 03 2012: (Start) G.f. A(x) = x/(1-x-x^2) = G(0)/sqrt(5) where G(k)= 1 -((-1)^k)*2^k/(a^k - b*x*a^k*2^k/(b*x*2^k - 2*((-1)^k)*c^k/G(k+1))) and a=3+sqrt(5), b=1+sqrt(5), c=3-sqrt(5); (continued fraction, 3rd kind, 3-step). Let E(x) be the e.g.f., i.e., E(x) = 1*x+1/2*x^2+1/3*x^3+1/8*x^4+1/24*x^5+1/90*x^6+13/5040*x^7+... then E(x) = G(0)/sqrt(5); G(k)= 1 -((-1)^k)*2^k/(a^k - b*x*a^k*2^k/(b*x*2^k -  2*((-1)^k)*(k+1)*c^k/G(k+1))), where a=3+sqrt(5), b=1+sqrt(5), c=3-sqrt(5); (continued fraction, 3rd kind, 3-step). (End) From Hieronymus Fischer, Nov 30 2012: (Start) Fib(n) = 1 + sum_{j_1=1..n-2} 1 + sum_{j_1=1..n-2} sum_{j_2=1..j_1-2} 1 + sum_{j_1=1..n-2} sum_{j_2=1..j_1-2} sum_{j_3=1..j_2-2} 1 + … + sum_{j_1=1..n-2} sum_{j_2=1..j_1-2} sum_{j_3=1..j_2-2} … sum_{j_k=1..j_(k-1)-2} 1, where k = floor((n-1)/2). Example: Fib(6) = 1 + sum_{j=1..4} 1 + sum_{j=1..4} sum_{k=1..(j-2)} 1 + 0 = 1 + (1 + 1 + 1 + 1) + (1 + (1 + 1)) = 8. Fib(n) = sum_{j=0..k} S(j+1,n-2j), where k = floor((n-1)/2) and the S(j,n) are the n-th j-simplex sums: S(1,n) = 1 is the 1-simplex sum, S(2,n) = sum_{k=1..n} S(1,k) = 1+1+...+1 = n is the 2-simplex sum, S(3,n) = sum_{k=1..n} S(2,k) = 1+2+3+…+n is the 3-simplex sum (= triangular numbers = A000217), S(4,n) = sum_{k=1..n} S(3,k) = 1+3+6+...+n(n+1)/2 is the 4-simplex sum (= tetrahedral numbers = A000292) and so on. Since S(j,n) = binomial(n-2+j,j-1), the formula above equals the well-known binomial formula, essentially. (End) G.f. A(x) = x / (1 - x / (1 - x / (1 + x))). - Michael Somos, Jan 04 2013 G.f.: 2*x^2/(2-G(0))-x^2+x where G(k) = 1 + x/(1 - x/(x + 2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 09 2013 G.f.: x/(G(0) - x^2) where G(k) =  1 - x/(x + 1/(1 + x/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 15 2013 sum{n>=1}(-1)^(n-1)/(a(n)*a(n+1)) = 1/phi (phi=golden ratio). - Vladimir Shevelev, Feb 22 2013 From Vladimir Shevelev, Feb 24 2013: (Start) (1) Expression a(n+1) via a(n): a(n+1) = (a(n) + sqrt(5*(a(n))^2 + 4*(-1)^n))/2; (2) sum_{k=1,...,n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1); (3) a(n)/a(n+1) = 1/phi + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End) F(n+1) = F(n)/2 + sqrt((-1)^n + 5*F(n)^2/4), n>=0. F(n+1) = U_n(i/2)/i^n, (U:= Chebyshef 2nd kind). - R. W. Gosper, Mar 04 2013 G.f.: -Q(0) where Q(k) = 1 - (1+x)/(1 - x/(x - 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Mar 06 2013 G.f.: x-1-1/x + 1/x/Q(0), where Q(k) = 1 - (k+1)*x/(1 - x/(x - (k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 23 2013 G.f.: x*G(0), where G(k)= 1 + x*(1+x)/(1 - x*(1+x)/(x*(1+x) + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 08 2013 G.f.: x^2 - 1 + 2*x^2/(W(0)-2), where W(k) = 1 + 1/(1 - x*(k + x)/( x*(k+1 + x) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013 G.f.: Q(0) -1, where Q(k) = 1 + x^2 + (k+2)*x -x*(k+1 + x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 06 2013 EXAMPLE 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, which are the 2nd to 6th entries in the sequence. - Cino Hilliard, Sep 15 2008 From Joerg Arndt, May 21 2013: (Start) There are a(7)=13 compositions of 7 where there is a drop between every second pair of parts, starting with the first and second part: 01:  [ 2 1 2 1 1 ] 02:  [ 2 1 3 1 ] 03:  [ 2 1 4 ] 04:  [ 3 1 2 1 ] 05:  [ 3 1 3 ] 06:  [ 3 2 2 ] 07:  [ 4 1 2 ] 08:  [ 4 2 1 ] 09:  [ 4 3 ] 10:  [ 5 1 1 ] 11:  [ 5 2 ] 12:  [ 6 1 ] 13:  [ 7 ] There are abs(a(6+1))=13 compositions of 6 where there is no rise between every second pair of parts, starting with the second and third part: 01:  [ 1 2 1 2 ] 02:  [ 1 3 1 1 ] 03:  [ 1 3 2 ] 04:  [ 1 4 1 ] 05:  [ 1 5 ] 06:  [ 2 2 1 1 ] 07:  [ 2 3 1 ] 08:  [ 2 4 ] 09:  [ 3 2 1 ] 10:  [ 3 3 ] 11:  [ 4 2 ] 12:  [ 5 1 ] 13:  [ 6 ] (End) MAPLE A000045 := proc(n) combinat[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, Apr 04 2008 spec := [ B, {B=Sequence(Set(Z, card>1))}, unlabeled ]: seq(combstruct[count](spec, size=n), n=1..39); - Zerinvary Lajos, Apr 04 2008 MATHEMATICA 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, Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009 *) Table[Fibonacci[n]^5 - Fibonacci[1 + n] + 3 Fibonacci[n]^4 Fibonacci[1 + n] + Fibonacci[n]^3 Fibonacci[1 + n]^2 - 3 Fibonacci[n]^2 Fibonacci[1 + n]^3 -   Fibonacci[n] Fibonacci[1 + n]^4 + Fibonacci[1 + n]^5, {n, 1, 10}] (* Artur Jasinski, Nov 17 2011 *) PROG (AXIOM) [fibonacci(n) for n in 0..50] (MAGMA) [Fibonacci(n): n in [0..38]]; (Maxima) makelist(fib(n), n, 0, 100); /* Martin Ettl, Oct 21 2012 */ (PARI) {a(n) = fibonacci(n)} (PARI) {a(n) = imag(quadgen(5)^n)} (PARI) a(n)=my(phi=quadgen(5)); (phi^n-(-1/phi)^n)/(2*phi-1) \\ Charles R Greathouse IV, Jun 17 2012 (PARI) {a(n)=polcoeff(sum(m=0, n, x^m*prod(k=1, m, k+x +x*O(x^n))/prod(k=1, m, 1+k*x +x*O(x^n))), n)} \\ Paul D. Hanna, Oct 26 2013 (Python) # Jaap Spies, Jan 05 2007 (Change leading dots to blanks.) def fib(): ... """ Generates the Fibonacci numbers, starting with 0 """ ... x, y = 0, 1 ... while 1: ....... yield x ....... x, y = y, x+y . f = fib() a = [f.next() for i in range(100)] . 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: a = sloane.A000045; ## choose sequence print a ## This returns the name of the sequence. print a(38) ## This returns the 38-th number of the sequence. print a.list(39) ## This returns a list of the first 39 numbers. (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] Gerald McGarvey, Sep 29 2009 -} CROSSREFS Cf. A039834 (signed Fibonacci numbers), A000213, A000288, A000322, A000383, A060455, A030186, A039834, A020695, A020701, A071679, A099731, A100492, A094216, A094638, A000108, A101399, A101400, A001611, A000071, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616, A059929, A144152, A152063, A114690, A003893, A000032, A060441, A000930, A003269. 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). a(k) = A090888(0, k+1) = A118654(0, k+1) = A118654(1, k-1) = A109754(0, k) = A109754(1, k-1), for k > 0. Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074. Cf. A001690 (complement). Boustrophedon transforms: A000738, A000744. Sequence in context: A132636 A152163 A039834 * A020695 A212804 A132916 Adjacent sequences:  A000042 A000043 A000044 * A000046 A000047 A000048 KEYWORD core,nonn,easy,nice,changed AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .