### ----------------------------------------------------
### -- OEIS
### -- Licenses: Artistic-2.0
### -- Authors: Tobias Boege
### -- File: t/data/Fibonacci-Search-all.txt
### ----------------------------------------------------
### -- Chunk 1 of 15
# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: seq:1,1,2,3,5,8,13,21
Showing 1-10 of 92

%I A000045 M0692 N0256
%S A000045 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,
%T A000045 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
%U A000045 1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155
%N A000045 Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
%C A000045 Also sometimes called Lamé's sequence.
%C A000045 F(n+2) = number of binary sequences of length n that have no consecutive 0's.
%C A000045 F(n+2) = number of subsets of {1,2,...,n} that contain no consecutive integers.
%C A000045 F(n+1) = number of tilings of a 2 X n rectangle by 2 X 1 dominoes.
%C A000045 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
%C A000045 F(n) = number of compositions of n+1 with no part equal to 1. [Cayley, Grimaldi]
%C A000045 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).
%C A000045 For Fibonacci search see Knuth, Vol. 3; Horowitz and Sahni; etc.
%C A000045 F(n) is the diagonal sum of the entries in Pascal's triangle at 45 degrees slope. - _Amarnath Murthy_, Dec 29 2001
%C A000045 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
%C A000045 F(n+1) = number of (3412,132)-, (3412,213)- and (3412,321)-avoiding involutions in S_n.
%C A000045 This is also the Horadam sequence (0,1,1,1). - _Ross La Haye_, Aug 18 2003
%C A000045 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
%C A000045 Number of meaningful differential operations of the k-th order on the space R^3. - _Branko Malesevic_, Mar 02 2004
%C A000045 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.
%C A000045 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
%C A000045 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
%C A000045 The number of sequences (s(0),s(1),...,s(n)) such that 0<s(i)<5, |s(i)-s(i-1)|=1 and s(0)=1 is F(n+1); e.g., F(5+1) = 8 corresponds to 121212, 121232, 121234, 123212, 123232, 123234, 123432, 123434. - _Clark Kimberling_, Jun 22 2004 [corrected by Neven Juric, Jan 09 2009]
%C A000045 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
%C A000045 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
%C A000045 For n>0, the continued fraction for F(2n-1)*Phi = [F(2n);L(2n-1),L(2n-1),L(2n-1),...] and the continued fraction for F(2n)*Phi=[F(2n+1)-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]
%C A000045 F(n+1) (for n >= 1) = 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
%C A000045 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
%C A000045 Lengths of successive words (starting with a) under the substitution: {a -> ab, b -> a}. - _Jeroen F.J. Laros_, Jan 22 2005
%C A000045 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 Brown-Duncan, 1970. - _N. J. A. Sloane_, Feb 12 2017)
%C A000045 a(n) = Sum_{k=0..n} abs(A108299(n, k)). - _Reinhard Zumkeller_, Jun 01 2005
%C A000045 a(n) = A001222(A000304(n)).
%C A000045 F(n+2) = Sum_{k=0..n} binomial(floor((n+k)/2),k), row sums of A046854. - _Paul Barry_, Mar 11 2003
%C A000045 Number of order ideals of the "zig-zag" poset. See vol. 1, ch. 3, prob. 23 of Stanley. - _Mitch Harris_, Dec 27 2005
%C A000045 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
%C A000045 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
%C A000045 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
%C A000045 Number of Kekulé structures in polyphenanthrenes. See the paper by Lukovits and Janezic for details. - _Parthasarathy Nambi_, Aug 22 2006
%C A000045 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
%C A000045 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
%C A000045 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
%C A000045 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_phi|5*F(n)*F(n+1)|) = n (where sign(x) = sign of x). - _Hieronymus Fischer_, May 02 2007
%C A000045 F(n+2) = The number of Khalimsky-continuous functions with a two-point codomain. - Shiva Samieinia (shiva(AT)math.su.se), Oct 04 2007
%C A000045 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
%C A000045 This is a_1(n) in the Doroslovacki reference.
%C A000045 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
%C A000045 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
%C A000045 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
%C A000045 Equals row sums of triangle A144152. - _Gary W. Adamson_, Sep 12 2008
%C A000045 Except for the initial term, the numerator of the convergents to the recursion x = 1/(x+1). - _Cino Hilliard_, Sep 15 2008
%C A000045 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
%C A000045 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
%C A000045 Fp == 5^((p-1)/2) mod p, p = prime [Schroeder, p. 90]. - _Gary W. Adamson_ & _Alexander R. Povolotsky_, Feb 21 2009
%C A000045 (Ln)^2 - 5*(Fn)^2 = 4*(-1)^n. Example: 11^2 - 5*5 = -4. - _Gary W. Adamson_, Mar 11 2009
%C A000045 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
%C A000045 (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
%C A000045 (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
%C A000045 a(n+2) = A083662(A131577(n)). - _Reinhard Zumkeller_, Sep 26 2009
%C A000045 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
%C A000045 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
%C A000045 (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
%C A000045 From the Pinter and Ziegler reference's abstract: authors "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
%C A000045 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
%C A000045 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
%C A000045 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 = 0.99992197.... - _Gary W. Adamson_, Jul 16 2010
%C A000045 From _Hieronymus Fischer_, Oct 20 2010: (Start)
%C A000045 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.
%C A000045 For all numbers 1 <= k < F(n), the inequality |k*phi-round(k*phi)| > |F(n)*phi-round(F(n)*phi)| holds.
%C A000045 F(n)*phi - round(F(n)*phi) = -((-phi)^(-n)), for n > 1.
%C A000045 Fract(1/2 + F(n)*phi) = 1/2 -(-phi)^(-n), for n > 1.
%C A000045 Fract(F(n)*phi) = (1/2)*(1 + (-1)^n) - (-phi)^(-n), n > 1.
%C A000045 Inverse: n = -log_phi |1/2 - fract(1/2 + F(n)*phi)|.
%C A000045 (End)
%C A000045 F(A001177(n)*k) mod n = 0, for any integer k. - _Gary Detlefs_, Nov 27 2010
%C A000045 F(n+k)^2 - F(n)^2 = F(k)*F(2n+k), for even k. - _Gary Detlefs_, Dec 04 2010
%C A000045 F(n+k)^2 + F(n)^2 = F(k)*F(2n+k), for odd k. - _Gary Detlefs_, Dec 04 2010
%C A000045 F(n) = round(phi* F(n-1)) for n > 1. - _Joseph P. Shoulak_, Jan 13 2012
%C A000045 For n > 0: a(n) = length of n-th row in Wythoff array A003603. - _Reinhard Zumkeller_, Jan 26 2012
%C A000045 From _Bridget Tenner_, Feb 22 2012: (Start)
%C A000045 The number of free permutations of [n].
%C A000045 The number of permutations of [n] for which s_k in supp(w) implies s_{k+-1} not in supp(w).
%C A000045 The number of permutations of [n] in which every decomposition into length(w) reflections is actually composed of simple reflections. (End)
%C A000045 The sequence F(n+1)^(1/n) is increasing. The sequence F(n+2)^(1/n) is decreasing. - _Thomas Ordowski_, Apr 19 2012
%C A000045 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
%C A000045 From _Ravi Kumar Davala_, Jan 30 2014: (Start)
%C A000045 Proof of Ratushnyak's first conjecture: For n > 1, F(n+2)^2 - F(n)*F(n+1) + (-1)^n = 2F(n+1)^2.
%C A000045 Consider: F(n+2)^2 - F(n)*F(n+1) - 2F(n+1)^2
%C A000045          = F(n+2)^2 - F(n+1)^2 - F(n+1)^2 - F(n)*F(n+1)
%C A000045          = (F(n+2) + F(n+1))*(F(n+2) - F(n+1)) - F(n+1)*(F(n+1) + F(n))
%C A000045          = F(n+3)*F(n) - F(n+1)*F(n+2) = -(-1)^n.
%C A000045 Proof of second conjecture: L(n) stands for Lucas number sequence from A000032.
%C A000045 Consider the fact that
%C A000045     L(2n+1)^2 = L(4n+2) - 2
%C A000045    (F(2n) + F(2n+2))^2 = F(4n+1) + F(4n+3) - 2
%C A000045    (F(2n) + F(2n+2))^2 = (Sum_{k = 2..2n} F(2k)) + F(4n+3).
%C A000045 (End)
%C A000045 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
%C A000045 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 the papers of Witula et al.). - _Roman Witula_, Jul 24 2012
%C A000045 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
%C A000045 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
%C A000045 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
%C A000045 Central terms of triangles in A162741 and A208245, n > 0. - _Reinhard Zumkeller_, Jul 28 2013
%C A000045 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
%C A000045 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. - _Wolfdieter Lang_, Oct 01 2013
%C A000045 A010056(a(n)) = 1. - _Reinhard Zumkeller_, Oct 10 2013
%C A000045 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(n-k) ). - _Charlie Marion_, Dec 20 2013
%C A000045 ( 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
%C A000045 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
%C A000045 Range of row n of the circular Pascal array of order 5. - _Shaun V. Ault_, May 30 2014 [orig. Kicey-Klimko 2011, and observations by Glen Whitehead; more general work found in Ault-Kicey 2014]
%C A000045 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
%C A000045 The expression round(1/(F(k+1)/F(n) + F(k)/F(n+1))), for n > 0, yields a Fibonacci sequence with k-1 leading zeros (with rounding 0.5 to 0). - _Richard R. Forberg_, Aug 04 2014
%C A000045 Conjecture: For n > 0, F(n) is the number of all admissible residue classes for