

A000045


Fibonacci numbers: F(n) = F(n1) + F(n2) with F(0) = 0 and F(1) = 1.
(Formerly M0692 N0256)


4155



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, 63245986, 102334155
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Also sometimes called Lamé'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 (i.e., Hosoya index) 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 kth order on the space R^3.  Branko Malesevic, Mar 02 2004
F(n)=number of compositions of n1 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 0<s(i)<5, s(i)s(i1)=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, 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, Sep 19 2004
For n>0, the continued fraction for F(2n1)*Phi = [F(2n);L(2n1),L(2n1),L(2n1),...] 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 ith Lucas number (A000204)....  Clark Kimberling, Nov 28 2004 [corrected by Hieronymus Fischer, Oct 20 2010]
F(n+1) (for n >= 1) = number of permutations p of 1,2,3,...,n such that kp(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}.  Jeroen F.J. Laros, 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 (See BrownDuncan, 1970,  N. J. A. Sloane, Feb 12 2017)
a(n) = Sum(abs(A108299(n, k)): 0 <= k <= n).  Reinhard Zumkeller, Jun 01 2005
a(n) = A001222(A000304(n)).
F(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 "zigzag" 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. A006356A006359.  Mitch Harris, Jul 06 2006
F(n+1) equals the number of downsets (i.e., decreasing subsets) of an nelement 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 Kekulé 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 triplediagonal matrix. Consider the maximal number T(n) of summands in the determinant of an n X n triplediagonal matrix. This is the same as the number of summands in such a determinant in which the main, sub and superdiagonal 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)*F(n)) + 1/2) = n, for n > 1. Also for n > 0, floor((1/2)*log_phi(5*F(n)*F(n+1))) = n. Extension valid for integer n, except n=0,1: floor((1/2)*sign(F(n)*F(n+1))*log_phi5*F(n)*F(n+1)) = n (where sign(x) = sign of x).  Hieronymus Fischer, May 02 2007
F(n+2) = The number of Khalimskycontinuous functions with a twopoint 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 = (sqrt(5)+1)/2 = 1.6180339...; then phi^n = (1/phi)*a(n) + a(n+1). Example: phi^4 = 6.8541019... = (0.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, F(n+1)F(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 2valued 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..(n1)/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^((p1)/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.  SarahMarie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009
(F(n),F(n+4)) satisfies the Diophantine equation: X^2 + Y^2  7XY = 9*(1)^n.  Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 06 2009
(F(n),F(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 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 xaxis. 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(n1) + F(n+1))^2  5F(n2)*F(n+2) = 9*(1)^n.  Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Mar 31 2010
From the Pinter and Ziegler reference's abstract: authors "show that essentially the Fibonacci sequence is the unique binary recurrence which contains infinitely many threeterm arithmetic progressions. A criterion for general linear recurrences having infinitely many threeterm 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(n1)  a(n1)/a(n)) tends to 1.0. Example: a(12)/a(11)  a(11)/a(12) = 144/89  89/144 = 0.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<=k<m. More formally: a(0)=0, a(1)=1, a(2)=1, a(n+1)=minimal m>a(n) such that m*phi is closer to an integer than a(n)*phi.
For all numbers 1 <= k < F(n), the inequality k*phiround(k*phi) > F(n)*phiround(F(n)*phi) holds.
F(n)*phi  round(F(n)*phi) = ((phi)^(n)), for n > 1.
Fract(1/2 + F(n)*phi) = 1/2 (phi)^(n), for n > 1.
Fract(F(n)*phi) = (1/2)*(1 + (1)^n)  (phi)^(n), n > 1.
Inverse: n = log_phi 1/2  fract(1/2 + F(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
F(n) = round(phi* F(n1)) for n > 1.  Joseph P. Shoulak, Jan 13 2012
For n > 0: a(n) = length of nth 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
From Ravi Kumar Davala, Jan 30 2014: (Start)
Proof of Ratushnyak's first conjecture: For n > 1, F(n+2)^2  F(n)*F(n+1) + (1)^n = 2F(n+1)^2.
Consider: F(n+2)^2  F(n)*F(n+1)  2F(n+1)^2
= F(n+2)^2  F(n+1)^2  F(n+1)^2  F(n)*F(n+1)
= (F(n+2) + F(n+1))*(F(n+2)  F(n+1))  F(n+1)*(F(n+1) + F(n))
= F(n+3)*F(n)  F(n+1)*F(n+2) = (1)^n.
Proof of second conjecture: L(n) stands for Lucas number sequence from A000032.
Consider the fact that
L(2n+1)^2 = L(4n+2)  2
(F(2n) + F(2n+2))^2 = F(4n+1) + F(4n+3)  2
(F(2n) + F(2n+2))^2 = (Sum_{k = 2..2n} F(2k)) + F(4n+3).
(End)
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)^(n1)*F(n), whereas the sequence F(n+1) is the binomial transformation of the alternating sequence (1)^n*F(n1). 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 socalled "deltaFibonacci" numbers as defined in comments to A014445 (see also the papers of Witula et al.).  Roman Witula, Jul 24 2012
F(n) is the number of different (n1)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(n1) is the number of simple permutations in the geometric grid class given in A226433.  Jay Pantone, Sep 08 2013
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(n1)*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.  Wolfdieter Lang, Oct 01 2013
A010056(a(n)) = 1.  Reinhard Zumkeller, Oct 10 2013
Define F(n) to be F(n) for n odd and F(n) for n even. Then for all n and k, F(n+2k)^2  F(n)^2 = F(n+k)*( F(n+3k)  F(nk) ).  Charlie Marion, Dec 20 2013
( F(n), F(n+2k) ) satisfies the Diophantine equation: X^2 + Y^2  L(2k)*X*Y = F(4k)^2*(1)^n. This generalizes Bouhamida’s comments dated Sep 06 2009 and Sep 08 2009.  Charlie Marion, Jan 07 2014
For any prime p there is an infinite periodic subsequence within F(n) divisible by p, that begins at index n = 0 with value 0, and its first nonzero term at n = A001602(i), and period k = A001602(i). Also see A236479.  Richard R. Forberg, Jan 26 2014
Range of row n of the circular Pascal array of order 5.  Shaun V. Ault, May 30 2014 [orig. KiceyKlimko 2011, and observations by Glen Whitehead; more general work found in AultKicey 2014]
Nonnegative range of the quintic polynomial 2*y  y^5 + 2*x*y^4 + x^2*y^3  2*x^3*y^2  x^4*y with x, y >= 0, see Jones 1975.  Charles R Greathouse IV, Jun 01 2014
The expression round(1/(F(k+1)/F(n) + F(k)/F(n+1))), for n > 0, yields a Fibonacci sequence with k1 leading zeros (with rounding 0.5 to 0).  Richard R. Forberg, Aug 04 2014
Conjecture: For n > 0, F(n) is the number of all admissible residue classes for which specific finite subsequences of the Collatz 3n + 1 function consists of n+2 terms. This has been verified for 0 < n < 51. For details see Links.  Mike Winkler, Oct 03 2014
a(4)=3 and a(6)=8 are the only Fibonacci numbers that are of the form prime+1.  Emmanuel Vantieghem, Oct 02 2014
a(1)=1=a(2), a(3)=2 are the only Fibonacci numbers that are of the form prime1.  Emmanuel Vantieghem, Jun 07 2015
Any consecutive pair (m, k) of the Fibonacci sequence a(n) illustrates a fair equivalence between m miles and k kilometers. For instance, 8 miles ~ 13 km; 13 miles ~ 21 km. Lekraj Beedassy, Oct 06 2014
Lim_{n > oo} (log F(n+1)/log F(n))^n = e.  Thomas Ordowski, Oct 06 2014
a(n+1) counts closed walks on K_2, containing one loop on the other vertex. Equivalently the (1,1)_entry of A^(n+1) where the adjacency matrix of digraph is A=(0,1; 1,1).  David Neil McGrath, Oct 29 2014
a(n1) counts closed walks on the graph G(1vertex;lloop,2loop).  David Neil McGrath, Nov 26 2014
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1x) = P[x], and C(x)= [1sqrt(14x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(1)(x) = Cinv[Pinv(x)] = Cinv[P(x)].
Mot(x) = C[P(x)] = C[Pinv(x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(1)(x) = Pinv[Cinv(x)] = (x  x^2) / (1  x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(1)(x) = P[Cinv(x)].
Fib(x) = Fin[Cinv(Cinv(x))] = P[Cinv(x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1xx^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(1)(x) = C[Pinv(x)] = BTC(x) and Fib(x) = BTC^(1)(x).
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1  t*x) = P(x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1t]], and that for A104597, Pinv[Cinv(x),t+1].
(End)
In keeping with historical accounts (see the references by P. Singh and S. Kak), the generalized Fibonacci sequence a, b, a + b, a + 2b, 2a + 3b, 3a + 5b, ... can also be described as the GopalaHemachandra numbers H(n) = H(n1) + H(n2), with F(n) = H(n) for a = b = 1, and Lucas sequence L(n) = H(n) for a = 2, b = 1.  Lekraj Beedassy, Jan 11 2015
D. E. Knuth writes: "Before Fibonacci wrote his work, the sequence F_{n} had already been discussed by Indian scholars, who had long been interested in rhythmic patterns that are formed from onebeat and twobeat notes. The number of such rhythms having n beats altogether is F_{n+1}; therefore both Gopāla (before 1135) and Hemachandra (c. 1150) mentioned the numbers 1, 2, 3, 5, 8, 13, 21, ... explicitly." (TAOCP Vol. 1, 2nd ed.)  Peter Luschny, Jan 11 2015
F(n+1) equals the number of binary words of length n avoiding runs of zeros of odd lengths.  Milan Janjic, Jan 28 2015
From Russell Jay Hendel, Apr 12 2015: (Start)
We prove Conjecture 1 of Rashid listed in the Formula section.
We use the following notation: F(n)=A000045(n), the Fibonacci numbers, and L(n) = A000032(n), the Lucas numbers. The fundamental FibonacciLucas recursion asserts that G(n) = G(n1)+ G(n2), with "L" or "F" replacing "G".
We need the following prerequisites which we label (A), (B),(C), (D). The prerequisites are formulas in the Koshy book listed in the References section. (A) F(m1)+F(m+1) = L(m) (Koshy, p. 97, #32), (B) L(2m)+2(1)^m = L(m)^2 (Koshy p. 97, #41), (C) F(m+k)F(mk) = (1)^n F(k)^2 (Koshy, p. 113, #24, Tagiuri's identity), and (D) F(n)^2+F(n+1)^2 = F(2n+1) (Koshy, p. 97, #30).
We must also prove (E), L(n+2) F(n1) = F(2n+1)+2(1)^n. To prove (E), first note that by (A), proof of (E) is equivalent to proving that F(n+1)F(n1) + F(n+3)F(n1) = F(2n+1)+2(1)^n. But by (C) with k=1, we have F(n+1)F(n1) = F(n)^2 +(1)^n. Applying (C) again with k=2 and m=n+1, we have F(n+3)F(n1) = F(n+1)+(1)^n. Adding these two applications of (C) together and using (D) we have, F(n+1)F(n1) + F(n+3)F(n1) = F(n)^2 + F(n+1)^2 + 2(1)^n = F(2n+1)+2(1)^n, completing the proof of (E).
We now prove Conjecture 1. By (A) and the FibonacciLucas recursion, we have F(2n+1)+F(2n+2)+F(2n+3)+F(2n+4) = [F(2n+1)+F(2n+3)] + [F(2n+2)+F(2n+4)] = L(2n+2)+L(2n+3)=L(2n+4). But then by (B), with m=2n+4, we have sqrt(L(2n+4)+2(1)^n)) = L(n+2). Finally by (E), we have L(n+2) F(n1)= F(2n+1)+2*(1)^n. Dividing both sides by F(n1), we have (F(2n+1)+2*(1)^n)/F(n1) = L(n+2) = sqrt(F(2n+1)+F(2n+2)+F(2n+3)+F(2n+4)+2(1)^n), as required.
(End)
In Fibonacci's Liber Abaci the rabbit problem appears in the translation of L. E. Sigler on pp. 404405, and a remark [27] on p. 637.  Wolfdieter Lang, Apr 17 2015
a(n) counts partially ordered partitions of (n1) into parts 1,2,3 where only the order of adjacent 1's and 2's are unimportant. (See example.)  David Neil McGrath, Jul 27 2015
F(n) divides F(nk). Proved by Marjorie Bicknell and Verner E Hoggatt Jr.  Juhani Heino, Aug 24 2015
F(n) is the number of UDUequivalence classes of ballot paths of length n. Two ballot paths of length n with steps U = (1,1), D = (1,1) are UDUequivalent whenever the positions of UDU are the same in both paths.  Kostas Manes, Aug 25 2015
Cassini's identity F(2n+1) * F(2n+3) = F(2n+2)^2 + 1 is the basis for a geometrical paradox (or dissection fallacy) in A262342.  Jonathan Sondow, Oct 23 2015
For n >= 4, F(n) is the number of updown words on alphabet {1,2,3} of length n2.  Ran Pan, Nov 23 2015
F(n+2) is the number of terms in p(n), where p(n)/q(n) is the nth convergent of the formal infinite continued fraction [a(0),a(1),...]; e.g., p(3) = a(0)a(1)a(2)a(3) + a(0)a(1) + a(0)a(3) + a(2)a(3) + 1 has F(5) terms. Also, F(n+1) is the number of terms in q(n).  Clark Kimberling, Dec 23 2015
F(n+1) (for n >= 1) is the permanent of an n X n matrix M with M(i,j)=1 if ij <= 1 and 0 otherwise.  Dmitry Efimov, Jan 08 2016
A trapezoid has three sides of lengths in order F(n), F(n+2), F(n). For increasing n a very close approximation to the maximum area will have the fourth side equal to 2*F(n+1). For a trapezoid with lengths of sides in order F(n+2), F(n), F(n+2), the fourth side will be F(n+3).  J. M. Bergot, Mar 17 2016
(1) Join two triangles with lengths of sides L(n), F(n+3), L(n+2) and F(n+2), L(n+1), L(n+2) (where L(n)=A000032(n)) along the common side of length L(n+2) to create an irregular quadrilateral. Its area is approximately (5*F(2*n1)  (F(2*n7)  F(2*n13))/5. (2) Join two triangles with lengths of sides L(n), F(n+2), F(n+3) and L(n+1), F(n+1, F(n+3) along the common side F(n+3) to form an irregular quadrilateral. Its area is approximately 4*F(2*n1)  2*(F(2*n7) + F(2*n18)).  J. M. Bergot, Apr 06 2016
From Clark Kimberling, Jun 13 2016: (Start)
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*.
Let g(n) be the set of nodes in the nth generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2, x}, g(3) = {3, 2x, x+1, x^2}, etc.
Let T(r) be the tree obtained by substituting r for x.
If a positive integer N is not a square and r = sqrt(N), then the number of (not necessarily distinct) integers in g(n) is A000045(n), for n > = 1. See A274142. (End)
Consider the partitions of n, with all summands initially listed in nonincreasing order. Freeze all the 1's in place and then allow all the other summands to change their order, without displacing any of the 1's. The resulting number of arrangements is a(n+1).  Gregory L. Simay, Jun 14 2016
Limit of the matrix power M^k shown in A163733, Sep 14 2016; as k>inf. results in a single column vector equal to the Fibonacci sequence.  Gary W. Adamson, Sep 19 2016
F(n) and Lucas numbers L(n), being related by the formulas F(n) = (F(n1) + L(n1))/2 and L(n) = 2 F(n+1)  F(n), are a typical pair of "autosequences" (see the link to OEIS Wiki).  JeanFrançois Alcover, Jun 10 2017
Also the number of independent vertex sets and vertex covers in the (n2)path graph.  Eric W. Weisstein, Sep 22 2017


REFERENCES

Abrate, Marco; Barbero, Stefano; Cerruti, Umberto; Murru, Nadir. Colored compositions, Invert operator and elegant compositions with the "black tie". Discrete Math. 335 (2014), 17. MR3248794
Andrews, George E. Fibonacci numbers and the RogersRamanujan identities. Fibonacci Quart. 42 (2004), no. 1, 319. MR2060558(2005b:11161)
S. V. Ault and C. Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics (2014).
Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 7879. 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. 1217.
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 18711876.
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums II, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 42, 2012, pp. 20532059.
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. 22212227.
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.
Marjorie Bicknell and Verner E Hoggatt, Fibonacci's Problem Book, Fibonacci Association, San Jose, Calif., 1974.
J. Brown and R. Duncan, Modulo one uniform distribution of the sequence of logarithms of certain recursive sequences, Fibonacci Quarterly 8 (1970) 482486.
A. Cayley, Theorems in Trigonometry and on Partitions, Messenger of Mathematics, 5 (1876), pp. 164, 188 = Mathematical Papers Vol. 10, n. 634, p. 16.
D. Chmiela, K. Kaczmarek, R. Witula, Binomials Transformation Formulas 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 p. 55, Times of India, Mumbai.
Persi Diaconis, http://statweb.stanford.edu/~cgates/PERSI/papers/probabilizingfibonacci.pdf, Probabilizing Fibonacci Numbers, 2017.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.
R. P. Grimaldi, Compositions without the summand 1, Proceedings Thirtysecond Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001). Congr. Numer. 152 (2001), 3343.
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), 371380.
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.
P. W. Kasteleyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica, 27 (1961), 12091225.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 63.
C. Kicey and K. Klimko, Some geometry of Pascal's triangle, Pi Mu Epsilon Journal, 13(4):229245 (2011).
D. E. Knuth, The Art of Computer Programming. AddisonWesley, 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.
Leonardo of Pisa [Leonardo Pisano], Liber Abaci [The Book of Calculation], 1202.
Lukovits et al., Nanotubes: Number of Kekulé structures and aromaticity, J. Chem. Inf. Comput. Sci, (2003), vol. 43, 609614. See eq. 2 on page 610.
I. Lukovits and D. Janezic, "Enumeration of conjugated circuits in nanotubes", J. Chem. Inf. Comput. Sci., vol. 44, 410414 (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), 2933.
G. Mantel, Resten van wederkeerige Reeksen, Nieuw Archief v. Wiskunde, 2nd series, I (1894), 172184.
C. N. Menhinick, The Fibonacci Resonance and other new Golden Ratio discoveries, Onperson, (2015), pages 200206.
A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405469.
S. Mneimneh, Fibonacci in The Curriculum: Not Just a Bad Recurrence, in Proceeding SIGCSE '15 Proceedings of the 46th ACM Technical Symposium on Computer Science Education, Pages 253258.
Hilary I. Okagbue, Muminu O. Adamu, Sheila A. Bishop, Abiodun A. Opanuga, Digit and Iterative Digit Sum of Fibonacci numbers, their identities and powers, International Journal of Applied Engineering Research ISSN 09734562 Volume 11, Number 6 (2016) pp 46234627.
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 padic Analysis, SpringerVerlag, 2000; p. 213.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 288.
Manfred R. Schroeder, "Number Theory in Science and Communication", 5th ed., SpringerVerlag, 2009
L. E. Sigler, Fibonacci's Liber Abaci, Springer, 2003, pp. 404405 and [26] on p. 627.
Simson, [No first name given], An explanation of an obscure passage in Albert Girard's Commentary ..., Phil. Trans. Royal Soc., 10 (1753), 430433.
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.
Van Ravenstein, Tony. "The three gap theorem (Steinhaus conjecture)." Journal of the Australian Mathematical Society (Series A) 45.03 (1988): 360370.
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. 617, Penguin Books 1987.
R. Witula, D. Slota, deltaFibonacci Numbers, Appl. Anal. Discrete Math., 3 (2009), 310329.


LINKS

N. J. A. Sloane, The first 2000 Fibonacci numbers: Table of n, F(n) for n = 0..2000
Matt Anderson, Jeffrey Frazier and Kris Popendorf, The Fibonacci series: the section index [broken link]
P. G. Anderson, Fibonacci Facts
Joerg Arndt, Matters Computational (The Fxtbook)
S. Barbero, U. Cerruti, N. Murru, Transforming Recurrent Sequences by Using the Binomial and Invert Operators, J. Int. Seq. 13 (2010) # 10.7.7, example 17.
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 IntegerSequenceBased Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
P. Barry, Generalized Catalan Numbers, Hankel Transforms and Somos4 Sequences , J. Int. Seq. 13 (2010) #10.7.2.
A. T. Benjamin, A. K. Eustis, M. A. Shattuck, Compression Theorems for Periodic Tilings and Consequences, JIS 12 (2009) 09.6.3
E. R. Berlekamp, A contribution to mathematical psychometrics, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]
Kh. Bibak, M. H. Shirdareh Haghighi, Some Trigonometric Identities Involving Fibonacci and Lucas Numbers, JIS 12 (2009) 09.8.4
Marjorie Bicknell and Verner E Hoggatt Jr, To Prove: F(n) Divides F(nk), A Primer for the Fibonacci Numbers: IX (1973)
J. Bodeen, S. Butler, T. Kim, X. Sun, S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7
H. Bottomley and N. J. A. Sloane, Illustration of initial terms: the Fibonacci tree
William Boyles, Table of n, a(n) for n = 0..9983
Brantacan, Fibonacci Numbers [broken link]
J. Britton & B. V. Eeckhout, Fibonacci Interactive [broken link]
S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142154.
N. D. Cahill, J. R. D'Errico, J. P. Spence, Complex factorizations of the Fibonacci and Lucas numbers, Fib. Quart. 41 (2003) 13.
N. D. Cahill and D. A. Narayan, Fibonacci and Lucas Numbers as Tridiagonal Matrix Determinants, Fibonacci Quarterly, 42(3):216221, 2004.
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.
Hongwei Chen, Evaluations of Some Variant Euler Sums, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.3.
J. H. Conway and N. J. A. Sloane, Notes on the ParaFibonacci and related sequences
J. H. Conway, Allan Wechsler, Marc LeBrun, Dan Hoey, N. J. A. Sloane, On Kimberling Sums and ParaFibonacci Sequences, Correspondence and Postings to MathFun Mailing List, Nov 1996 to Jan 1997
H. S. M. Coxeter, The Golden Section, Phyllotaxis and Wythoff's Game, Scripta Math. 19 (1953), 135143. [Annotated scanned copy]
E. S. Croot, Notes on Linear Recurrence Sequences
Paul Cubre, The Zdensities of the Fibonacci sequence, M. A. Thesis, Wake Forest University, May 2012;
C. Dement, Posting to Math Forum [broken link].
B. Demirturk, R. Keskin, Integer Solutions of Some Diophantine Equations via Fibonacci and Lucas Numbers, JIS 12 (2009) 09.8.7
R. M. Dickau, Fibonacci numbers
R. Doroslovacki, Binary sequences without 011...110 (k1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 34, 9398.
A.S. Elsenhans and J. Jahnel, The Fibonacci sequence modulo p^2  an investigation by computer for p < 10^14.
Nathaniel D. Emerson, A Family of MetaFibonacci Sequences Defined by VariableOrder 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. 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, Notices of the American Mathematical Society, 57 (2010), 840850. See page 844
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
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)
Dale Gerdemann, Golden Ratio Base Contains Zeckendorf and Negative Indexed Bunder Forms
C. J. Glasby, S. P. Glasby, F. Pleijel, Worms by number, Proc. Roy. Soc. B, Proc. Biol. Sci. 275 (1647) (2008) 20712076.
L. Goldsmith, The Fibonacci Numbers [broken link]
Hank Green, The Fibonacci Sequence: Nature's Code (2012).
M. Griffiths, A Restricted Random Walk defined via a Fibonacci Process, Journal of Integer Sequences, Vol. 14 (2011), #11.5.4.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2Binary trees: bijections and related issues, Discr. Math., 308 (2008), 12091221.
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697712. [Annotated scanned copy]
GuoNiu Han, Enumeration of Standard Puzzles [broken link]
GuoNiu Han, Enumeration of Standard Puzzles [Cached copy]
S. Happersett, Mathematical meditations
Brady Haran and Colm Mulcahy, Little Fibs  Numberphile (2016)
A. P. Hillman & G. L. Alexanderson, Algebra Through Problem Solving, Chapter 2 pp. 1116, The Fibonacci and Lucas Numbers [broken link]
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
V. E. Hoggatt and C. T. Long, Divisibility Properties of Generalized Fibonacci Polynomials, Fibonacci Quarterly, 12:113120, 1974.
Q.H. Hou, Z.W. Sun and H.M. Wen, On monotonicity of some combinatorial sequences, arXiv:1208.3903 [math.CO], 20122014.
C. W. Huegy and D. B. West, A Fibonacci tiling of the plane, Discrete Math., 249 (2002), 111116.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 9
Tina Hill Janzen, Fibonacci sequence / Golden scale [broken link]
James P. Jones, Diophantine representation of the Fibonacci numbers, Fibonacci Quarterly 13:1 (1975), pp. 8488.
R. Jovonovic, Fibonacci Function Calculator [broken link]
R. Jovonovic, The relations between the Fibonacci and the Lucas numbers [broken link]
R. Jovanovic, First 70 Fibonacci numbers [broken link]
Ivana Jovović and Branko Malešević, Some Enumerations of Nontrivial Composition of the Differential Operations and the Directional Derivative, Notes on Number Theory and Discrete Mathematics 23, no. 1 (2017), 2838. See Remark 2.9.
S. Kak, The Golden Mean and the Physics of Aesthetics, arXiv:physics/0411195 [physics.histph], 2004.
Louis H. Kauffman and Pedro Lopes, Graded forests and rational knots, arXiv:0710.3765 [math.GT], 20072009.
Blair Kelly, Fibonacci and Lucas factorizations
R. Keskin, Z. Yosma, On Fibonacci and Lucas Numbers of the form c*x^2, J. Int. Seq. 14 (2011) # 11.9.3.
Tanya Khovanova, Recursive Sequences
C. Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.
C. Kimberling, Strong divisibility sequences and some conjectures, Fib. Quart., 17 (1979), 1317.
Ron Knott, Fibonacci numbers and the golden section
Ron Knott, Mathematics of the Fibonacci Series
Ron Knott, Fibonacci numbers with tables of F(0)F(500).
A. Krowne, PlanetMath.org, Fibonacci sequence [broken link]
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 5967. [Annotated and corrected scanned copy]
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). [broken link]
F. Luca, V. J. M. Huguet, F. Nicolae, On the Euler Function of Fibonacci Numbers, JIS 12 (2009) 09.6.6
Edouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184240.
B. Malesevic, Some combinatorial aspects of differential operation composition on the space R^n [broken link].
Charles P. McKeague, Fibonacci numbers from MathTV
Graeme McRae, Sum of 2m consecutive Fibonacci numbers
D. Merlini, R. Sprugnoli and M. C. Verri, Strip tiling and regular grammars, Theoret. Computer Sci. 242, 12 (2000) 109124. [broken link]
D. Merrill, The FibPhi Link Page [broken link]
JeanChristophe Michel, Le nombre d'or dans l'ensemble de Mandelbrot (in French, 'The golden number in the Mandelbrot set')
Kerry Mitchell, SpirolateralType 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, arXiv:math/0311205 [math.CO], 2003.
R. Mullen, On Determining Paint by Numbers Puzzles with Nonunique Solutions, JIS 12 (2009) 09.6.5
Newton Institute, Posters in the London Underground
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci nstep and Lucas nstep Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
OEIS Wiki, Autosequence
J. J. O'Connor and E. F. Robertson, Mac Tutor History of Mathematics, Archarya Hemachandra
Arzu Özkoç, Some algebraic identities on quadra FibonaPell integer sequence, Advances in Difference Equations, 2015, 2015:148.
Ram Krishna Pandey, On Some Magnified Fibonacci Numbers Modulo a Lucas Number, Journal of Integer Sequences, Vol. 16 (2013), #13.1.7.
J. Patterson, The Fibonacci Sequence. [broken link]
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]
T. K. Petersen and B. E. Tenner, The depth of a permutation, arXiv:1202.4765v1 [math.CO], 20122014.
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 [math.NT], 2010.
Simon Plouffe, Project Gutenberg, The First 1001 Fibonacci Numbers [broken link]
Project Nayuki, Fast Fibonacci algorithms (fast doubling is faster than matrix multiplication).
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 [math.PR], 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.
Rosetta Code, A collection of codes to compute fibonacci numbers with different computer languages
E. S. Rowland, Fibonacci Sequence Calculator up to n=1474
Michelle RudolphLilith, On the Product Representation of Number Sequences, with Application to the Fibonacci Family, arXiv preprint arXiv:1508.07894, 2015
Shiva Samieinia, Digital straight line segments and curves. Licentiate Thesis. Stockholm University, Department of Mathematics, Report 2007:6.
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.
D. Schweizer, First 500 Fibonacci Numbers in blocks of 100. [broken link]
Mark A. Shattuck, Tiling proofs of some formulas for the Pell numbers of odd index, Integers, 9 (2009), 5364.
Mark A. Shattuck and Carl G. Wagner, Periodicity and Parity Theorems for a Statistic on rMino Arrangements, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.6.
S. Silvia, Fibonacci sequence [broken link]
Parmanand Singh, The socalled Fibonacci numbers in ancient and medieval India, Historia Mathematica, Volume 12 (3), 1985, 229244.
Jaap Spies, Sage program for computing A000045
Michael Z. Spivey and Laura L. Steil, The kBinomial 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 [broken link]
K. Tognetti, Letter to N. J. A. Sloane (with attachments), May 25 1994
K. Tognetti, The Search for the Golden Sequence, Draft Manuscript, May 25 1994.
K. Tognetti, FibonacciHis Rabbits and His Numbers and Kepler
Tony van Ravenstein, The three gap theorem (Steinhaus conjecture), Journal of the Australian Mathematical Society (Series A) 45.03 (1988): 360370. [Annotated scanned copy]
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.
A. Y. Z. Wang, P. Wen, On the partial finite sums of the reciprocals of the Fibonacci numbers, Journal of Inequalities and Applications, 2015.
Carl G. Wagner, Partition Statistics and qBell Numbers (q = 1), J. Integer Seqs., Vol. 7, 2004.
Robert Walker, Inharmonic "Golden Rhythmicon"  Fibonacci Sequence in Pairs Approaching Golden Ratio  With Bounce
Eric Weisstein's World of Mathematics, Fibonacci Number, DoubleFree Set, Fibonacci nStep Number, Resistor Network
Eric Weisstein's World of Mathematics, Hosoya Index
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Path Graph
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, Fibonacci number
Wikipedia, Cassini and Catalan identities
Willem's Fibonacci site, Fibonacci
Mike Winkler, On the structure and the behaviour of Collatz 3n + 1 sequences  Finite subsequences and the role of the Fibonacci sequence, arXiv:1412.0519 [math.GM], 2014.
Roman Witula, Damian Slota and Edyta Hetmaniok, Bridges between different known integer sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 255263.
R. Yanco, Letter and Email to N. J. A. Sloane, 1994
R. Yanco and A. Bagchi, Kth order maximal independent sets in path and cycle graphs, Unpublished manuscript, 1994. (Annotated scanned copy)
Aimei Yu and Xuezheng Lv, The MerrifieldSimmons indices and Hosoya indices of trees with k pendant vertices, J. Math. Chem., Vol. 41 (2007), pp. 3343. 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.
Index entries for "core" sequences
Index to divisibility sequences
Index entries for related partitioncounting sequences
Index entries for linear recurrences with constant coefficients, signature (1,1).
Index entries for twoway infinite sequences
Index entries for sequences related to Benford's law


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  (1sqrt(5))^n)/(2^n*sqrt(5)).
Alternatively, F(n) = ((1/2+sqrt(5)/2)^n  (1/2sqrt(5)/2)^n)/sqrt(5).
F(n) = F(n1) + F(n2) = (1)^n F(n).
F(n) = round(phi^n/sqrt(5)).
F(n+1) = Sum_{j=0..floor(n/2)} binomial(nj, j).
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m.  Michael Somos, Jan 03 2017
E.g.f.: (2/sqrt(5))*exp(x/2)*sinh(sqrt(5)*x/2).  Len Smiley, 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
From Kurmang. Aziz. Rashid, Feb 21 2004: (Start)
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(n1). [For a proof see Comments section.]
Conjecture 2: for n >= 0, (F(n+2)*F(n+3))  (F(n+1)*F(n+4)) + (1)^n = 0.
[Two more conjectures removed by Peter Luschny, Nov 17 2017 ]
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(n3) + F(n6). (End)
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 2Phi <= c < 2*(2Phi) we have F(n) = floor(Phi*a(n1)+c) for n > 2.  Gerald McGarvey, Jul 21 2004
2*F(n)  9*F(n+1) = 4*A000032(n) + A000032(n+1).  Creighton Dement, Aug 13 2004
For x > Phi, Sum_{n>=0} F(n)/x^n = x/(x^2  x  1)  Gerald McGarvey, Oct 27 2004
F(n+1) = exponent of the nth term in the series f(x, 1) determined by the equation f(x, y) = xy + f(xy, x).  Jonathan Sondow, Dec 19 2004
a(n1) = Sum_{k=0..n} (1)^k*binomial(nceiling(k/2), floor(k/2)).  Benoit Cloitre, May 05 2005
F(n+1) = Sum_{k=0..n} binomial((n+k)/2, (nk)/2)(1+(1)^(nk))/2.  Paul Barry, Aug 28 2005
Fibonacci(n) = Product_{j=1..ceiling(n/2)1} (1 + 4(cos(j*Pi/n))^2). [Bicknell and Hoggatt, pp. 4748.]  Emeric Deutsch, Oct 15 2006
F(n) = 2^(n1)*Sum_{k=0..floor((n1)/2)} binomial(n,2*k+1)*5^k.  Hieronymus Fischer, Feb 07 2006
a(n) = (b(n+1) + b(n1))/n where {b(n)} is the sequence A001629.  Sergio Falcon, Nov 22 2006
F(n*m) = Sum_{k = 0..m} binomial(m,k)*F(n1)^k*F(n)^(mk)*F(mk). The generating function of F(n*m) (n fixed, m = 0,1,2,...) is G(x) = F(n)*x / ((1  F(n1)*x)^2  F(n)*x*(1  F(n1)*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(n) = Lucas numbers. Then:
For a >= b and odd b, F(a+b) + F(ab) = L(a)*F(b).
For a >= b and even b, F(a+b) + F(ab) = F(a)*L(b).
For a >= b and odd b, F(a+b)  F(ab) = F(a)*L(b).
For a >= b and even b, F(a+b)  F(ab) = L(a)*F(b).
F(n+m) + (1)^m*F(nm) = F(n)*L(m);
F(n+m)  (1)^m*F(nm) = L(n)*F(m);
F(n+m+k) + (1)^k*F(n+mk) + (1)^m*(F(nm+k) + (1)^k*F(nmk)) = F(n)*L(m)*L(k);
F(n+m+k)  (1)^k*F(n+mk) + (1)^m*(F(nm+k)  (1)^k*F(nmk)) = L(n)*L(m)*F(k);
F(n+m+k) + (1)^k*F(n+mk)  (1)^m*(F(nm+k) + (1)^k*F(nmk)) = L(n)*F(m)*L(k);
F(n+m+k)  (1)^k*F(n+mk)  (1)^m*(F(nm+k)  (1)^k*F(nmk)) = 5*F(n)*F(m)*F(k). (End)
A corollary to Kristof 2007 is 2*F(a+b) = F(a)*L(b) + L(a)*F(b).  Graeme McRae, Apr 24 2014
For n > m, the sum of the 2m consecutive Fibonacci numbers F(nm1) thru F(n+m2) is F(n)*L(m) if m is odd, and L(n)*F(m) if m is even (see the McRae link).  Graeme McRae, Apr 24 2014.
F(n) = b(n) + (p1)*Sum_{k=2..n1} floor(b(k)/p)*F(nk+1) where b(k) is the digital sum analog of the Fibonacci recurrence, defined by b(k) = ds_p(b(k1)) + ds_p(b(k2)), b(0)=0, b(1)=1, ds_p=digital sum base p. Example for base p=10: F(n) = A010077(n) + 9*Sum_{k=2..n1} A059995(A010077(k))*F(nk+1).  Hieronymus Fischer, Jul 01 2007
F(n) = b(n)+p*Sum_{k=2..n1} floor(b(k)/p)*F(nk+1) where b(k) is the digital product analog of the Fonacci recurrence, defined by b(k) = dp_p(b(k1)) + dp_p(b(k2)), b(0)=0, b(1)=1, dp_p=digital product base p. Example for base p=10: F(n) = A074867(n) + 10*Sum_{k=2..n1} A059995(A074867(k))*F(nk+1).  Hieronymus Fischer, 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,...] = 0.6180339....  Gary W. Adamson, 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, 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, Mar 16 2008
a(2^n) = Product_{i=0..n2} B(i) where B(i) is A001566. Example 3*7*47 = F(16).  Kenneth J Ramsey, Apr 23 2008
F(n) = (1/(n1)!) * (n^(n1)  (C(n2,0) + 4*C(n2,1) + 3*C(n2,2))*n^(n2) + (10*C(n3,0) + 49*C(n3,1) + 95*C(n3,2) + 83*C(n3,3) + 27*C(n3,4))*n^(n3)  (90*C(n4,0) + 740*C(n4,1) + 2415*C(n4,2) + 4110*C(n4,3) + 3890*C(n4,4) + 1950*C(n4,5) + 405*C(n4,6))*n^(n4) + ... ).  André F. Labossière, Nov 24 2004
a(n+1) = Sum_{k=0..n} A109466(n,k)*(1)^(nk). Philippe Deléham, Oct 26 2008
a(n) = Sum_{l_1=0..n+1} Sum_{l_2=0..n}...Sum_{l_i=0..ni}... 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..n1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise.  Thomas Wieder, Feb 25 2009
a(n+1) = 2^n sqrt(Product_{k=1..n} cos(k Pi/(n+1))^2+1/4)) (Kasteleyn's formula specialized).  SarahMarie 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(n1).  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[ji+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
Lim_{k>infinity} F(k+n)/F(k) = (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(n1)) + 2^(phi*F(n2)))), where phi is the golden ratio.  Vladimir Shevelev, Jun 24 2010, Jun 27 2010
For n >= 1, a(n+1) = ceiling(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(n2) + a(n3), n > 2.  Gary Detlefs, Sep 08 2010
a(2^n) = Product_{i=0..n1} A000032(2^i).  Vladimir Shevelev, Nov 28 2010
a(n)^2  a(n1)^2 = a(n+1)*a(n2), 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
(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).  Artur Jasinski, Nov 17 2011
F(n) = 1 + Sum_{x=1..n2} F(x).  Joseph P. Shoulak, Feb 05 2012
F(n) = 4*F(n2)  2*F(n3)  F(n6).  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/(1xx^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=3sqrt(5); (continued fraction, 3rd kind, 3step).
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=3sqrt(5); (continued fraction, 3rd kind, 3step).
(End)
From Hieronymus Fischer, Nov 30 2012: (Start)
F(n) = 1 + Sum_{j_1=1..n2} 1 + Sum_{j_1=1..n2} Sum_{j_2=1..j_12} 1 + Sum_{j_1=1..n2} Sum_{j_2=1..j_12} Sum_{j_3=1..j_22} 1 + ... + Sum_{j_1=1..n2} Sum_{j_2=1..j_12} Sum_{j_3=1..j_22} ... Sum_{j_k=1..j_(k1)2} 1, where k = floor((n1)/2).
Example: F(6) = 1 + Sum_{j=1..4} 1 + Sum_{j=1..4} Sum_{k=1..(j2)} 1 + 0 = 1 + (1 + 1 + 1 + 1) + (1 + (1 + 1)) = 8.
F(n) = Sum_{j=0..k} S(j+1,n2j), where k = floor((n1)/2) and the S(j,n) are the nth jsimplex sums: S(1,n) = 1 is the 1simplex sum, S(2,n) = Sum_{k=1..n} S(1,k) = 1+1+...+1 = n is the 2simplex sum, S(3,n) = Sum_{k=1..n} S(2,k) = 1+2+3+...+n is the 3simplex sum (= triangular numbers = A000217), S(4,n) = Sum_{k=1..n} S(3,k) = 1+3+6+...+n(n+1)/2 is the 4simplex sum (= tetrahedral numbers = A000292) and so on.
Since S(j,n) = binomial(n2+j,j1), the formula above equals the wellknown binomial formula, essentially. (End)
G.f. A(x) = x / (1  x / (1  x / (1 + x))).  Michael Somos, Jan 04 2013
Sum_{n >= 1} (1)^(n1)/(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)^(k1)/(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).  Bill 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.: x11/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
Let b(n) = b(n1) + b(n2), with b(0) = 0, b(1) = phi. Then, for n >= 2, F(n)= floor(b(n1)) if n is even, F(n) = ceil(b(n1)), if n is odd, with convergence.  Richard R. Forberg, Jan 19 2014
a(n) = Sum_{t1*g(1)+t2*g(2)+...+tn*g(n)=n} multinomial(t1+t2 +...+tn,t1,t2,...,tn), where g(k)=2*k1.  Mircea Merca, Feb 27 2014
F(n) = round(sqrt(F(n1)^2 + F(n)^2 + F(n+1)^2)/2), for n > 0. This rule appears to apply to any sequence of the form a(n) = a(n1) + a(n2), for any two values of a(0) and a(1), if n is sufficiently large.  Richard R. Forberg, Jul 27 2014
F(n) = round(2/(1/F(n) + 1/F(n+1) + 1/F(n+2)), for n > 0. This rule also appears to apply to any sequence of the form a(n) = a(n1) + a(n2), for any two values of a(0) and a(1), if n is sufficiently large.  Richard R. Forberg, Aug 03 2014
F(n) = round(1/(Sum_{j>=n+2} 1/F(j))).  Richard R. Forberg, Aug 14 2014
a(n) = hypergeometric([n/2+1/2, n/2+1], [n+1], 4) for n >= 2.  Peter Luschny, Sep 19 2014
F(n) = (L(n+1)^2  L(n1)^2)/(5*L(n)), where L(n) is A000032(n), with a similar inverse relationship.  Richard R. Forberg, Nov 17 2014
Consider the graph G[1vertex;1loop,2loop] in comment above. Construct the power matrix array T(n,j) = [A^*j]*[S^*(j1)] where A=(1,1,0,...) and S=(0,1,0,...)(A063524). [* is convolution operation] Define S^*0=I with I=(1,0,...). Then T(n,j) counts nwalks containing (j) loops and a(n1) = Sum_{j=1...n} T(n,j).  David Neil McGrath, Nov 21 2014
Define F(n) to be F(n) for n odd and F(n) for n even. Then for all n and k, F(n) = F(k)*F(nk+3)  F(k1)*F(nk+2)  F(k2)*F(nk) + (1)^k*F(n2k+2).  Charlie Marion, Dec 04 2014
F(n+k)^2  L(k)*F(n)*F(n+k) + (1)^k*F(n)^2 = (1)^n*F(k)^2, if L(k) = A000032(k).  Alexander Samokrutov, Jul 20 2015
F(2*n) = F(n+1)^2  F(n1)^2, similar to Koshy (D) and Forberg 2011, but different.  Hermann StammWilbrandt, Aug 12 2015
F(n+1) = ceiling( (1/phi)*Sum_{k=0..n} F(k) ).  Tom Edgar, Sep 10 2015
a(n) = (L(n3) + L(n+3))/10 where L(n)=A000032(n).  J. M. Bergot, Nov 25 2015
From Bob Selcoe, Mar 27 2016 (Start):
F(n) = (F(2n+k+1)  F(n+1)*F(n+k+1))/F(n+k), k >= 0.
Thus when k=0: F(n) = sqrt(F(2n+1)  F(n+1)^2).
F(n) = cbrt(F(3n)  F(n+1)^3 + F(n1)^3).
F(n+2k) = binomial transform of any subsequence starting with F(n). Example F(6)=8: 1*8 = F(6)=8; 1*8 + 1*13 = F(8)=21; 1*8 + 2*13 + 1*21 = F(10)=55; 1*8 + 3*13 + 3*21 + 1*34 = F(12)=144, etc. This formula applies to Fibonaccitype sequences with any two seed values for a(0) and a(1) (e.g., Lucas sequence A000032: a(0)=2, a(1)=1).
(End)
F(n) = L(k)*F(nk) + (1)^(k+1)*F(n2k) for all k>=0, where L(k) = A000032(k).  Anton Zakharov, Aug 02 2016
From Ilya Gutkovskiy, Aug 03 2016: (Start)
a(n) = F_n(1), where F_n(x) are the Fibonacci polynomials.
Inverse binomial transform of A001906.
Number of zeros in substitution system {0 > 11, 1 > 1010} at step n from initial string "1" (1 > 1010 > 101011101011 > ...) multiplied by 1/A000079(n). (End)
For n>=2, a(n) = 2^(n^2+n)  (4^n2^n1)*floor(2^(n^2+n)/(4^n2^n1))  2^n*floor(2^(n^2)  (2^n11/2^n)*floor(2^(n^2+n)/(4^n2^n1))).  Benoit Cloitre, Apr 17 2017
For n > 0, a(n) = b(n+1) where b(n) = Sum_{k=1..n} b(nk)*A000931(k1), b(0) = 1.  J. Conrad, Apr 19 2017
f(n+1) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n2j,k)*binomial(j,k).  Tony Foster III, Sep 04 2017
F(n) = Sum_{k=0..floor((n1)/2)} ( (nk1)! / ((n2k1)! * k!) ).  Zhandos Mambetaliyev, Nov 08 2017


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)
Partially ordered partitions of (n1) into parts 1,2,3 where only the order of the adjacent 1's and 2's are unimportant. E.g., a(8)=21. These are (331),(313),(133),(322),(232),(223),(3211),(2311),(1321),(2131),(1132),(2113),(31111),(13111),(11311),(11131),(11113),(2221),(22111),(211111),(1111111).  David Neil McGrath, Jul 25 2015
Consider the partitions of 7 with summands initially listed in nonincreasing order. Keep the 1's frozen in position,(indicated by "[]") and then allow the other summands to otherwise vary their order: 7; 6,[1]; 5,2; 2,5; 4,3; 3,4; 5,[1,1], 4,2,[1]; 2,4,[1]; 3,3,[1]; 3,3,2; 3,2,3; 2,3,3; 4,[1,1,1]; 3,2,[1,1]; 2,3,[1,1]; 2,2,2,[1]; 3,[1,1,1,1]; 2,2,[1,1,1]; 2,[1,1,1,1,1]; [1,1,1,1,1,1,1]. There are 21 = a(7+1) arrangements in all.  Gregory L. Simay, Jun 14 2016


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
# The following Maple command isFib(n) yields true or false depending on whether n is a Fibonacci number or not.
with(combinat): isFib := proc(n) local a: a := proc(n) local j: for j while fibonacci(j) <= n do fibonacci(j) end do: fibonacci(j1) end proc: evalb(a(n) = n) end proc: # Emeric Deutsch, Nov 11 2014


MATHEMATICA

Table[Fibonacci[k], {k, 0, 50}] (* Mohammad K. Azarian, Jul 11 2015 *)
Table[2^n Sqrt @ Product[(Cos[Pi k/(n + 1)]^2 + 1/4), {k, n}] // FullSimplify, {n, 15}]; (* Kasteleyn's formula specialized, SarahMarie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009 *)
LinearRecurrence[{1, 1}, {0, 1}, 40] (* Harvey P. Dale, Aug 03 2014 *)
Fibonacci[Range[0, 20]] (* Eric W. Weisstein, Sep 22 2017 *)
CoefficientList[Series[(x/(1 + x + x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 22 2017 *)


PROG

(Axiom) [fibonacci(n) for n in 0..50]
(MAGMA) [Fibonacci(n): n in [0..38]];
(MAGMA) [0, 1] cat [n: n in [1..50000000]  IsSquare(5*n^24) or IsSquare(5*n^2+4)]; // Vincenzo Librandi, Nov 19 2014
(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*phi1) \\ 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]
.
(Python) # As bfile:
from gmpy2 import fib
for n in xrange(100): print str(n)+" "+str(fib(n)) # Bruno Berselli, Dec 06 2016
(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 38th number of the sequence.
print a.list(39) ## This returns a list of the first 39 numbers.
(Sage) # Alternatively:
a = BinaryRecurrenceSequence(1, 1); print [a(n) for n in (0..19)]
# Closed form integer formula with F(1) = 0 from Paul Hankin (use only for fun).
F = lambda n: (4<<(n1)*(n+2))//((4<<2*(n1))(2<<(n1))1)&((2<<(n1))1)
print [F(n) for n in (0..19)] # Peter Luschny, Aug 28 2016
(Sage) [i for i in fibonacci_sequence(0, 40)] # Bruno Berselli, Jun 26 2014
(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 }
(Julia)
function fib(n)
F = BigInt[1 1; 1 0]
Fn = F^n
Fn[2, 1]
end
println([fib(n) for n in 0:38]) # Peter Luschny, Feb 23 2017
(GAP)
Fib:=[0, 1];; for n in [3..10^3] do Fib[n]:=Fib[n1]+Fib[n2]; od; Fib; # Muniru A Asiru, Sep 03 2017
(Scheme)
;; The following definition uses macro definec for the memoization (caching) of the results. See http://oeis.org/wiki/Memoization#Scheme
(definec (A000045 n) (if (< n 2) n (+ (A000045 ( n 1)) (A000045 ( n 2))))) ;; Antti Karttunen, Oct 06 2017


CROSSREFS

Cf. A039834 (signed Fibonacci numbers), A001690 (complement), A000213, A000288, A000322, A000383, A060455, A030186, 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, A000957, A057078, A007317, A091867, A104597, A249548, A262342, A001060, A022095, A072649.
First row of arrays A103323, A234357. Second row of arrays A099390, A048887, and A092921 (kgeneralized Fibonacci numbers).
a(n) = A094718(4, n). a(n) = A101220(0, j, n).
a(n) = A090888(0, n+1) = A118654(0, n+1) = A118654(1, n1) = A109754(0, n) = A109754(1, n1), for n > 0.
FibonacciPascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074.
Boustrophedon transforms: A000738, A000744.
Powers: A103323, A105317, A254719.
Numbers of prime factors: A022307 and A038575.
Cf. A163733.
Sequence in context: A152163 A039834 A236191 * A020695 A212804 A132916
Adjacent sequences: A000042 A000043 A000044 * A000046 A000047 A000048


KEYWORD

nonn,core,nice,easy,hear


AUTHOR

N. J. A. Sloane, 1964


STATUS

approved



