A000045 - OEIS

%I M0692 N0256 #2230 Nov 20 2024 15:18:14

%S 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,

%T 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,

%U 1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155

%N Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.

%C 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 one-beat and two-beat 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

%C 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 Gopala-Hemachandra numbers H(n) = H(n-1) + H(n-2), 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

%C Susantha Goonatilake writes: "[T]his sequence was well known in South Asia and used in the metrical sciences. Its development is attributed in part to Pingala (200 BC), later being associated with Virahanka (circa 700 AD), Gopala (circa 1135), and Hemachandra (circa 1150)—all of whom lived and worked prior to Fibonacci." (Toward a Global Science: Mining Civilizational Knowledge, p. 126) - _Russ Cox_, Sep 08 2021

%C Also sometimes called Hemachandra numbers.

%C Also sometimes called Lamé's sequence.

%C For a photograph of "Fibonacci"'s 1202 book, see the Leonardo of Pisa link below.

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

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

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

%C 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 F(n) = number of compositions of n+1 with no part equal to 1. [Cayley, Grimaldi]

%C 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 For Fibonacci search see Knuth, Vol. 3; Horowitz and Sahni; etc.

%C F(n) is the diagonal sum of the entries in Pascal's triangle at 45 degrees slope. - _Amarnath Murthy_, Dec 29 2001 (i.e., row sums of A030528, _R. J. Mathar_, Oct 28 2021)

%C 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 F(n+1) = number of (3412,132)-, (3412,213)- and (3412,321)-avoiding involutions in S_n.

%C This is also the Horadam sequence (0,1,1,1). - _Ross La Haye_, Aug 18 2003

%C 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 Number of meaningful differential operations of the k-th order on the space R^3. - _Branko Malesevic_, Mar 02 2004

%C 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 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 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 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 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 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 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 For any nonzero number k, the continued fraction [4,4,...,4,k], which is n 4's and a single k, equals (F(3n) + k*F(3n+3))/(F(3n-3) + k*F(3n)). - _Greg Dresden_, Aug 07 2019

%C 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 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 Lengths of successive words (starting with a) under the substitution: {a -> ab, b -> a}. - _Jeroen F.J. Laros_, Jan 22 2005

%C 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 F(n+2) = Sum_{k=0..n} binomial(floor((n+k)/2),k), row sums of A046854. - _Paul Barry_, Mar 11 2003

%C Number of order ideals of the "zig-zag" poset. See vol. 1, ch. 3, prob. 23 of Stanley. - _Mitch Harris_, Dec 27 2005

%C 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 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 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 Number of Kekulé structures in polyphenanthrenes. See the paper by Lukovits and Janezic for details. - _Parthasarathy Nambi_, Aug 22 2006

%C 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 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 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

%C 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 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 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 This is a_1(n) in the Doroslovacki reference.

%C Let phi = A001622 then phi^n = (1/phi)*a(n) + a(n+1). - _Gary W. Adamson_, Dec 15 2007

%C 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 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 Equals row sums of triangle A144152. - _Gary W. Adamson_, Sep 12 2008

%C Except for the initial term, the numerator of the convergents to the recursion x = 1/(x+1). - _Cino Hilliard_, Sep 15 2008

%C 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 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 Fp == 5^((p-1)/2) mod p, p = prime [Schroeder, p. 90]. - _Gary W. Adamson_ & _Alexander R. Povolotsky_, Feb 21 2009

%C A000032(n)^2 - 5*F(n)^2 = 4*(-1)^n. - _Gary W. Adamson_, Mar 11 2009

%C 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_, Jul 04 2009

%C (F(n),F(n+4)) satisfies the Diophantine equation: X^2 + Y^2 - 7XY = 9*(-1)^n. - _Mohamed Bouhamida_, Sep 06 2009

%C (F(n),F(n+2)) satisfies the Diophantine equation: X^2 + Y^2 - 3XY = (-1)^n. - _Mohamed Bouhamida_, Sep 08 2009

%C a(n+2) = A083662(A131577(n)). - _Reinhard Zumkeller_, Sep 26 2009

%C 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 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 (F(n-1) + F(n+1))^2 - 5*F(n-2)*F(n+2) = 9*(-1)^n. - _Mohamed Bouhamida_, Mar 31 2010

%C 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 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 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 As n->oo, (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 From _Hieronymus Fischer_, Oct 20 2010: (Start)

%C 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 For all numbers 1 <= k < F(n), the inequality |k*phi-round(k*phi)| > |F(n)*phi-round(F(n)*phi)| holds.

%C F(n)*phi - round(F(n)*phi) = -((-phi)^(-n)), for n > 1.

%C Fract(1/2 + F(n)*phi) = 1/2 -(-phi)^(-n), for n > 1.

%C Fract(F(n)*phi) = (1/2)*(1 + (-1)^n) - (-phi)^(-n), n > 1.

%C Inverse: n = -log_phi |1/2 - fract(1/2 + F(n)*phi)|.

%C (End)

%C F(A001177(n)*k) mod n = 0, for any integer k. - _Gary Detlefs_, Nov 27 2010

%C F(n+k)^2 - F(n)^2 = F(k)*F(2n+k), for even k. - _Gary Detlefs_, Dec 04 2010

%C F(n+k)^2 + F(n)^2 = F(k)*F(2n+k), for odd k. - _Gary Detlefs_, Dec 04 2010

%C F(n) = round(phi*F(n-1)) for n > 1. - _Joseph P. Shoulak_, Jan 13 2012

%C For n > 0: a(n) = length of n-th row in Wythoff array A003603. - _Reinhard Zumkeller_, Jan 26 2012

%C From _Bridget Tenner_, Feb 22 2012: (Start)

%C The number of free permutations of [n].

%C The number of permutations of [n] for which s_k in supp(w) implies s_{k+-1} not in supp(w).

%C The number of permutations of [n] in which every decomposition into length(w) reflections is actually composed of simple reflections. (End)

%C The sequence F(n+1)^(1/n) is increasing. The sequence F(n+2)^(1/n) is decreasing. - _Thomas Ordowski_, Apr 19 2012

%C 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 From _Ravi Kumar Davala_, Jan 30 2014: (Start)

%C Proof of Ratushnyak's first conjecture: For n > 1, F(n+2)^2 - F(n)*F(n+1) + (-1)^n = 2*F(n+1)^2.

%C Consider: F(n+2)^2 - F(n)*F(n+1) - 2*F(n+1)^2

%C          = F(n+2)^2 - F(n+1)^2 - F(n+1)^2 - F(n)*F(n+1)

%C          = (F(n+2) + F(n+1))*(F(n+2) - F(n+1)) - F(n+1)*(F(n+1) + F(n))

%C          = F(n+3)*F(n) - F(n+1)*F(n+2) = -(-1)^n.

%C Proof of second conjecture: L(n) stands for Lucas number sequence from A000032.

%C Consider the fact that

%C     L(2n+1)^2 = L(4n+2) - 2

%C    (F(2n) + F(2n+2))^2 = F(4n+1) + F(4n+3) - 2

%C    (F(2n) + F(2n+2))^2 = (Sum_{k = 2..2n} F(2k)) + F(4n+3).

%C (End)

%C 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 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 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 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 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 [see the Hopkins/Tangboonduangjit reference for a proof, see also the Checa reference for alternative proofs and statistics]

%C Central terms of triangles in A162741 and A208245, n > 0. - _Reinhard Zumkeller_, Jul 28 2013

%C 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 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 A010056(a(n)) = 1. - _Reinhard Zumkeller_, Oct 10 2013

%C 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 ( 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 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 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 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 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 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

%C a(4)=3 and a(6)=8 are the only Fibonacci numbers that are of the form prime+1. - _Emmanuel Vantieghem_, Oct 02 2014

%C a(1)=1=a(2), a(3)=2 are the only Fibonacci numbers that are of the form prime-1. - _Emmanuel Vantieghem_, Jun 07 2015

%C 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

%C 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

%C a(n-1) counts closed walks on the graph G(1-vertex;l-loop,2-loop). - _David Neil McGrath_, Nov 26 2014

%C From _Tom Copeland_, Nov 02 2014: (Start)

%C Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x) = [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).

%C 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)].

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

%C BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)].

%C Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^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).

%C 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,1-t]], and that for A104597, Pinv[Cinv(x),t+1].

%C (End)

%C F(n+1) equals the number of binary words of length n avoiding runs of zeros of odd lengths. - _Milan Janjic_, Jan 28 2015

%C From _Russell Jay Hendel_, Apr 12 2015: (Start)

%C We prove Conjecture 1 of Rashid listed in the Formula section.

%C We use the following notation: F(n)=A000045(n), the Fibonacci numbers, and L(n) = A000032(n), the Lucas numbers. The fundamental Fibonacci-Lucas recursion asserts that G(n) = G(n-1) + G(n-2), with "L" or "F" replacing "G".

%C 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(m-1) + 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(m-k) = (-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).

%C We must also prove (E), L(n+2)*F(n-1) = 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(n-1) + F(n+3)*F(n-1) = F(2n+1) + 2*(-1)^n. But by (C) with k=1, we have F(n+1)*F(n-1) = F(n)^2 + (-1)^n. Applying (C) again with k=2 and m=n+1, we have F(n+3)*F(n-1) = F(n+1) + (-1)^n. Adding these two applications of (C) together and using (D) we have F(n+1)*F(n-1) + F(n+3)*F(n-1) = F(n)^2 + F(n+1)^2 + 2*(-1)^n = F(2n+1) + 2(-1)^n, completing the proof of (E).

%C We now prove Conjecture 1. By (A) and the Fibonacci-Lucas 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(n-1) = F(2n+1) + 2*(-1)^n. Dividing both sides by F(n-1), we have (F(2n+1) + 2*(-1)^n)/F(n-1) = L(n+2) = sqrt(F(2n+1) + F(2n+2) + F(2n+3) + F(2n+4) + 2(-1)^n), as required.

%C (End)

%C In Fibonacci's Liber Abaci the rabbit problem appears in the translation of L. E. Sigler on pp. 404-405, and a remark [27] on p. 637. - _Wolfdieter Lang_, Apr 17 2015

%C a(n) counts partially ordered partitions of (n-1) 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

%C F(n) divides F(n*k). Proved by Marjorie Bicknell and Verner E Hoggatt Jr. - _Juhani Heino_, Aug 24 2015

%C F(n) is the number of UDU-equivalence classes of ballot paths of length n. Two ballot paths of length n with steps U = (1,1), D = (1,-1) are UDU-equivalent whenever the positions of UDU are the same in both paths. - _Kostas Manes_, Aug 25 2015

%C 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

%C For n >= 4, F(n) is the number of up-down words on alphabet {1,2,3} of length n-2. - _Ran Pan_, Nov 23 2015

%C F(n+2) is the number of terms in p(n), where p(n)/q(n) is the n-th 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

%C F(n+1) (for n >= 1) is the permanent of an n X n matrix M with M(i,j)=1 if |i-j| <= 1 and 0 otherwise. - _Dmitry Efimov_, Jan 08 2016

%C 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

%C (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*n-1) - (F(2*n-7) - F(2*n-13))/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*n-1) - 2*(F(2*n-7) + F(2*n-18)). - _J. M. Bergot_, Apr 06 2016

%C From _Clark Kimberling_, Jun 13 2016: (Start)

%C 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*.

%C Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2, x}, g(3) = {3, 2x, x+1, x^2}, etc.

%C Let T(r) be the tree obtained by substituting r for x.

%C 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)

%C 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

%C Limit of the matrix power M^k shown in A163733, Sep 14 2016, as k->infinity results in a single column vector equal to the Fibonacci sequence. - _Gary W. Adamson_, Sep 19 2016

%C F(n) and Lucas numbers L(n), being related by the formulas F(n) = (F(n-1) + L(n-1))/2 and L(n) = 2 F(n+1) - F(n), are a typical pair of "autosequences" (see the link to OEIS Wiki). - _Jean-François Alcover_, Jun 10 2017

%C Also the number of independent vertex sets and vertex covers in the (n-2)-path graph. - _Eric W. Weisstein_, Sep 22 2017

%C Shifted numbers of {UD, DU, FD, DF}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - _Sergey Kirgizov_, Apr 08 2018

%C For n > 0, F(n) = the number of Markov equivalence classes with skeleton the path on n nodes. See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - _Liam Solus_, Aug 23 2018

%C For n >= 2, also: number of terms in A032858 (every other base-3 digit is strictly smaller than its neighbors) with n-2 digits in base 3. - _M. F. Hasler_, Oct 05 2018

%C F(n+1) is the number of fixed points of the Foata transformation on S_n. - _Kevin Long_, Oct 17 2018

%C F(n+2) is the dimension of the Hecke algebra of type A_n with independent parameters (0,1,0,1,...) or (1,0,1,0,...). See Corollary 1.5 in the link "Hecke algebras with independent parameters". - _Jia Huang_, Jan 20 2019

%C The sequence is the second INVERT transform of (1, -1, 2, -3, 5, -8, 13, ...) and is the first sequence in an infinite set of successive INVERT transforms generated from (1, 0, 1, 0, 1, ...). Refer to the array shown in A073133. - _Gary W. Adamson_, Jul 16 2019

%C From _Kai Wang_, Dec 16 2019: (Start)

%C F(n*k)/F(k) = Sum_{i=0..n-1; j=0..n-1; i+2*j=n-1} (-1)^(j*(k-1))*L(k)^i*((i+j)!/(i!*j!)).

%C F((2*m+1)*k)/F(k) = Sum_{i=0..m-1} (-1)^(i*k)*L((2*m-2*i)*k) + (-1)^(m*k).

%C F(2*m*k)/F(k) = Sum_{i=0..m-1} (-1)^(i*k)*L((2*m-2*i-1)*k).

%C F(m+s)*F(n+r) - F(m+r)*F(n+s) = (-1)^(n+s)*F(m-n)*F(r-s).

%C F(m+r)*F(n+s) + F(m+s)*F(n+r) = (2*L(m+n+r+s) - (-1)^(n+s)*L(m-n)*L(r-s))/5.

%C L(m+r)*L(n+s) - 5*F(m+s)*F(n+r) = (-1)^(n+s)*L(m-n)*L(r-s).

%C L(m+r)*L(n+s) + 5*F(m+s)*F(n+r) = 2*L(m+n+r+s) + (-1)^(n+s)*5*F(m-n)*F(r-s).

%C L(m+r)*L(n+s) - L(m+s)*L(n+r) = (-1)^(n+s)*5*F(m-n)*F(r-s). (End)

%C F(n+1) is the number of permutations in S_n whose principal order ideals in the weak order are Boolean lattices. - _Bridget Tenner_, Jan 16 2020

%C F(n+1) is the number of permutations w in S_n that form Boolean intervals [s, w] in the weak order for every simple reflection s in the support of w. - _Bridget Tenner_, Jan 16 2020

%C F(n+1) is the number of subsets of {1,2,.,.,n} in which all differences between successive elements of subsets are odd. For example, for n = 6, F(7) = 13 and the 13 subsets are {6}, {1,6}, {3,6}, {5,6}, {2,3,6}, {2,5,6}, {4,5,6}, {1,2,3,6}, {1,2,5,6}, {1,4,5,6}, {3,4,5,6}, {2,3,4,5,6}, {1,2,3,4,5,6}. For even differences between elements see Comment in A016116. - _Enrique Navarrete_, Jul 01 2020

%C F(n) is the number of subsets of {1,2,...,n} in which the smallest element of the subset equals the size of the subset (this type of subset is sometimes called extraordinary). For example, F(6) = 8 and the subsets are {1}, {2,3}, {2,4}, {2,5}, {3,4,5}, {2,6}, {3,4,6}, {3,5,6}. It is easy to see that these subsets follow the Fibonacci recursion F(n) = F(n-1) + F(n-2) since we get F(n) such subsets by keeping all F(n-1) subsets from the previous stage (in the example, the F(5)=5 subsets that don't include 6), and by adding one to all elements and appending an additional element n to each subset in F(n-2) subsets (in the example, by applying this to the F(4)=3 subsets {1}, {2,3}, {2,4} we obtain {2,6}, {3,4,6}, {3,5,6}). - _Enrique Navarrete_, Sep 28 2020

%C Named "série de Fibonacci" by Lucas (1877) after the Italian mathematician Fibonacci (Leonardo Bonacci, c. 1170 - c. 1240/50). In 1876 he named the sequence "série de Lamé" after the French mathematician Gabriel Lamé (1795 - 1870). - _Amiram Eldar_, Apr 16 2021

%C F(n) is the number of edge coverings of the path with n edges. - _M. Farrokhi D. G._, Sep 30 2021

%C LCM(F(m), F(n)) is a Fibonacci number if and only if either F(m) divides F(n) or F(n) divides F(m). - _M. Farrokhi D. G._, Sep 30 2021

%C Every nonunit positive rational number has at most one representation as the quotient of two Fibonacci numbers. - _M. Farrokhi D. G._, Sep 30 2021

%C The infinite sum F(n)/10^(n-1) for all natural numbers n is equal to 100/89. More generally, the sum of F(n)/(k^(n-1)) for all natural numbers n is equal to k^2/(k^2-k-1). _Jonatan Djurachkovitch_, Dec 31 2023

%C For n >= 1, number of compositions (c(1),c(2),...,c(k)) of n where c(1), c(3), c(5), ... are 1. To obtain such compositions K(n) of length n increase all parts c(2) by one in all of K(n-1) and prepend two parts 1 in all of K(n-2). - _Joerg Arndt_, Jan 05 2024

%D 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.

%D 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.

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

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

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

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

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 24 (Ex. 18), 489, 541.

%D 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 B. A. Davey and H. A. Priestley, Introduction to Lattices and Order (2nd edition), CUP, 2002. (See Exercise 1.15.)

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

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

%D 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.

%D H. Halberstam and K. F. Roth, Sequences, Oxford, 1966; see Appendix.

%D S. Happersett, "Mathematical meditations", Journal of Mathematics and the Arts, 1 (2007), 29 - 33.

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

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

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

%D M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 63.

%D C. Kicey and K. Klimko, Some geometry of Pascal's triangle, Pi Mu Epsilon Journal, 13(4):229-245 (2011).

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

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

%D Leonardo of Pisa [Leonardo Pisano], Liber Abaci [The Book of Calculation], 1202.

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

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

%D 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.

%D 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.

%D G. Mantel, Resten van wederkeerige Reeksen, Nieuw Archief v. Wiskunde, 2nd series, I (1894), 172-184.

%D C. N. Menhinick, The Fibonacci Resonance and other new Golden Ratio discoveries, Onperson, (2015), pages 200-206.

%D 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 253-258.

%D 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 0973-4562 Volume 11, Number 6 (2016) pp 4623-4627.

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

%D 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.

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

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

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

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

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

%D Manfred R. Schroeder, "Number Theory in Science and Communication", 5th ed., Springer-Verlag, 2009

%D L. E. Sigler, Fibonacci's Liber Abaci, Springer, 2003, pp. 404-405 and [26] on p. 627.

%D Simson, [No first name given], An explanation of an obscure passage in Albert Girard's Commentary ..., Phil. Trans. Royal Soc., 10 (1753), 430-433.

%D Parmanand Singh, The so-called fibonacci numbers in ancient and medieval India, Historia Mathematica, vol. 12 (1985), 229-244.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

%D N. N. Vorob'ev, Chisla fibonachchi [Russian], Moscow, 1951. English translation, Fibonacci Numbers, Blaisdell, New York and London, 1961.

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

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

%D D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 53.

%D R. Witula, D. Slota, delta-Fibonacci Numbers, Appl. Anal. Discrete Math., 3 (2009), 310-329.

%H N. J. A. Sloane, <a href="/A000045/b000045.txt">The first 2000 Fibonacci numbers: Table of n, F(n) for n = 0..2000</a>

%H Marco Abrate, Stefano Barbero, Umberto Cerruti, Nadir Murru, <a href="http://dx.doi.org/10.1016/j.disc.2014.06.026">Colored compositions, Invert operator and elegant compositions with the "black tie"</a>, Discrete Math. 335 (2014), 1--7. MR3248794.

%H Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, Mark Shattuck, <a href="https://www.emis.de/journals/JIS/VOL22/Shattuck/shattuck13.html">Some New Restricted n-Color Composition Functions</a>, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.

%H Matt Anderson, Jeffrey Frazier and Kris Popendorf, <a href="http://library.thinkquest.org/27890/theSeries.html">The Fibonacci series: the section index</a> [broken link]

%H P. G. Anderson, <a href="http://www.cs.rit.edu/~pga/Fibo/fact_sheet.html">Fibonacci Facts</a>

%H George E. Andrews, <a href="https://www.fq.math.ca/Papers1/42-1/quartgranville01_2004.pdf">Fibonacci numbers and the Rogers-Ramanujan identities</a>, Fibonacci Quart. 42 (2004), no. 1, 3-19. MR2060558(2005b:11161).

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>

%H Andrei Asinowski, Cyril Banderier, Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).

%H Shaun V. Ault and Charles Kicey, <a href="http://dx.doi.org/10.1016/j.disc.2014.05.020">Counting paths in corridors using circular Pascal arrays</a>, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.

%H Mohammad K. Azarian, <a href="http://www.m-hikari.com/ijcms/ijcms-2012/37-40-2012/azarianIJCMS37-40-2012.pdf">Fibonacci Identities as Binomial Sums</a>, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 1871-1876.

%H Mohammad K. Azarian, <a href="http://www.m-hikari.com/ijcms/ijcms-2012/41-44-2012/azarianIJCMS41-44-2012.pdf">Fibonacci Identities as Binomial Sums II</a>, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 42, 2012, pp. 2053-2059.

%H Mohammad K. Azarian, <a href="http://www.m-hikari.com/ijcms/ijcms-2012/45-48-2012/azarianIJCMS45-48-2012.pdf">Identities Involving Lucas or Fibonacci and Lucas Numbers as Binomial Sums</a>, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 45, 2012, pp. 2221-2227.

%H Ovidiu Bagdasar, Eve Hedderwick, Ioan-Lucian Popa, <a href="https://doi.org/10.1016/j.endm.2018.05.011">On the ratios and geometric boundaries of complex Horadam sequences</a>, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 63-70.

%H S. Barbero, U. Cerruti, N. Murru, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barbero/barbero5.html">Transforming Recurrent Sequences by Using the Binomial and Invert Operators</a>, J. Int. Seq. 13 (2010) # 10.7.7, example 17.

%H J.-L. Baril, <a href="https://doi.org/10.37236/665">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.

%H Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.

%H Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="http://math.colgate.edu/~integers/t46/t46.Abstract.html">Motzkin paths with a restricted first return decomposition</a>, Integers (2019) Vol. 19, A46.

%H Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry1/barry95r.html">Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences </a>, J. Int. Seq. 13 (2010) #10.7.2.

%H Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.

%H Paul Barry, <a href="https://arxiv.org/abs/1910.00875">Generalized Catalan recurrences, Riordan arrays, elliptic curves, and orthogonal polynomials</a>, arXiv:1910.00875 [math.CO], 2019.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.01126">Riordan arrays, the A-matrix, and Somos 4 sequences</a>, arXiv:1912.01126 [math.CO], 2019.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.11845">Chebyshev moments and Riordan involutions</a>, arXiv:1912.11845 [math.CO], 2019.

%H Paul Barry, <a href="https://arxiv.org/abs/2001.08799">Characterizations of the Borel triangle and Borel polynomials</a>, arXiv:2001.08799 [math.CO], 2020.

%H Paul Barry, Aoife Hennessy and Nikolaos Pantelidis, <a href="https://doi.org/10.1007/s10801-020-00953-4">Algebraic properties of Riordan subgroups</a>, J Algebr Comb 53, 1015-1036 (2021).

%H A. T. Benjamin, A. K. Eustis, M. A. Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Shattuck/shattuck20.html">Compression Theorems for Periodic Tilings and Consequences</a>, JIS 12 (2009) 09.6.3.

%H E. R. Berlekamp, <a href="/A257113/a257113.pdf">A contribution to mathematical psychometrics</a>, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]

%H Kh. Bibak and M. H. Shirdareh Haghighi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Bibak/bibak4.html">Some Trigonometric Identities Involving Fibonacci and Lucas Numbers</a>, JIS 12 (2009) 09.8.4

%H Marjorie Bicknell and Verner E Hoggatt Jr, <a href="http://www.fq.math.ca/Books/Primer/bicknell6.pdf">To Prove: F(n) Divides F(nk)</a>, A Primer for the Fibonacci Numbers: IX (1973)

%H J. Bodeen, S. Butler, T. Kim, X. Sun, S. Wang, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p7">Tiling a strip with triangles</a>, El. J. Combinat. 21 (1) (2014) P1.7.

%H H. Bottomley and N. J. A. Sloane, <a href="/A000045/a000045.html">Illustration of initial terms: the Fibonacci tree</a>.

%H William Boyles, <a href="/A000045/a000045_3.txt">Table of n, a(n) for n = 0..9983</a>

%H Brantacan, <a href="http://www.branta.connectfree.co.uk/fibonacci.htm">Fibonacci Numbers</a> [broken link]

%H Jhon J. Bravo, Jose L. Herrera, and José L. Ramírez, <a href="https://www.emis.de/journals/JIS/VOL23/Bravo/bravo4.html">Combinatorial Interpretation of Generalized Pell Numbers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.2.1.

%H J. Britton & B. V. Eeckhout, <a href="http://ccins.camosun.bc.ca/~jbritton/fibonacci/jbfibapplet.htm">Fibonacci Interactive</a> [broken link]

%H S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.019">On the equivalence problem for succession rules</a>, Discr. Math., 298 (2005), 142-154.

%H J. Brown and R. Duncan, <a href="http://www.fq.math.ca/Scanned/8-5/brown.pdf">Modulo one uniform distribution of the sequence of logarithms of certain recursive sequences</a>, Fibonacci Quarterly 8 (1970) 482-486.

%H Steve Butler, Jason Ekstrand, and Steven Osborne, <a href="https://doi.org/10.1007/978-3-030-37853-0_5">Counting Tilings by Taking Walks in a Graph</a>, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 155.

%H N. D. Cahill, J. R. D'Errico, and J. P. Spence, <a href="https://www.fq.math.ca/Scanned/41-1/cahill.pdf">Complex factorizations of the Fibonacci and Lucas numbers</a>, Fib. Quart. 41 (2003) 13.

%H N. D. Cahill and D. A. Narayan, <a href="http://www.fq.math.ca/Papers1/42-3/quartcahill03_2004.pdf">Fibonacci and Lucas Numbers as Tridiagonal Matrix Determinants</a>, Fibonacci Quarterly, 42(3):216-221, 2004.

%H C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php/FibonacciNumber.html">Fibonacci number</a>

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Dario Carrasquel, <a href="https://dariocarrasquel.com/2016/08/26/5-ways-to-solve-fibonacci-in-scala-tail-recursion-memoization-the-pisano-period-more/">"5 ways to solve Fibonacci in Scala - Tail Recursion, Memoization, The Pisano Period & More"</a>, August 26, 2016.

%H Paula M. M. C. Catarino, and Anabela Borges, <a href="http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1005">On Leonardo numbers</a>, Acta Mathematica Universitatis Comenianae (2019), 1-12.

%H Daniel F. Checa, <a href="/A000045/a000045_3.pdf">Arndt Compositions: Connections with Fibonacci Numbers, Statistics, and Generalizations</a>, 2023.

%H Hongwei Chen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Chen/chen78.html">Evaluations of Some Variant Euler Sums</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.3.

%H Fan R. K. Chung, Persi Diaconis, and Ron Graham, <a href="https://statweb.stanford.edu/~cgates/PERSI/papers/sequential_sampling_10.pdf">Permanental generating functions and sequential importance sampling</a>, Stanford University (2018).

%H J. H. Conway and N. J. A. Sloane, <a href="/A019586/a019586.pdf">Notes on the Para-Fibonacci and related sequences</a>

%H J. H. Conway, Allan Wechsler, Marc LeBrun, Dan Hoey, N. J. A. Sloane, <a href="/A269725/a269725.txt">On Kimberling Sums and Para-Fibonacci Sequences</a>, Correspondence and Postings to Math-Fun Mailing List, Nov 1996 to Jan 1997.

%H H. S. M. Coxeter, <a href="/A000201/a000201.pdf">The Golden Section, Phyllotaxis and Wythoff's Game</a>, Scripta Math. 19 (1953), 135-143. [Annotated scanned copy]

%H E. S. Croot, <a href="http://people.math.gatech.edu/~ecroot/recurrence_notes2.pdf">Notes on Linear Recurrence Sequences</a>

%H Paul Cubre, <a href="http://wakespace.lib.wfu.edu/bitstream/handle/10339/37313/Cubre_wfu_0248M_10299.pdf">The Z-densities of the Fibonacci sequence</a>, M. A. Thesis, Wake Forest University, May 2012.

%H Henrique F. da Cruz, Ilda Inácio, Rogério Serôdio, <a href="https://doi.org/10.26493/1855-3974.1477.1c7">Convertible subspaces that arise from different numberings of the vertices of a graph</a>, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 473-486.

%H C. Dement, <a href="http://mathforum.org/discuss/sci.math/t/622432">Posting to Math Forum</a> [broken link].

%H B. Demirturk and R. Keskin, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Demirturk/demirturk3.html">Integer Solutions of Some Diophantine Equations via Fibonacci and Lucas Numbers</a>, JIS 12 (2009) 09.8.7.

%H Ömür Deveci, Zafer Adıgüzel, and Taha Doğan, <a href="https://doi.org/10.7546/nntdm.2020.26.1.179-190">On the Generalized Fibonacci-circulant-Hurwitz numbers</a>, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 1, 179-190.

%H Persi Diaconis, <a href="http://statweb.stanford.edu/~cgates/PERSI/papers/probabilizing-fibonacci.pdf">Probabilizing Fibonacci Numbers</a>, 2017.

%H R. M. Dickau, <a href="https://www.robertdickau.com/fibboard.html">Fibonacci numbers</a>

%H Robert Dougherty-Bliss, <a href="https://arxiv.org/abs/2206.14852">The Meta-C-finite Ansatz</a>, arXiv preprint arXiv:2206.14852, 2022

%H R. Doroslovacki, <a href="http://www.emis.de/journals/MV/9434/mv943407.ps">Binary sequences without 011...110 (k-1 1's) for fixed k</a>, Mat. Vesnik 46 (1994), no. 3-4, 93-98.

%H A.-S. Elsenhans and J. Jahnel, <a href="http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf">The Fibonacci sequence modulo p^2 - an investigation by computer for p < 10^14</a>.

%H Nathaniel D. Emerson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.html">A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.

%H David Eppstein, <a href="https://arxiv.org/abs/1804.07396">Making Change in 2048</a>, arXiv:1804.07396 [cs.DM], 2018.

%H Gennady Eremin, <a href="https://arxiv.org/abs/2108.10676">Walking in the OEIS: From Motzkin numbers to Fibonacci numbers. The "shadows" of Motzkin numbers</a>, arXiv:2108.10676 [math.CO], 2021.

%H Reinhardt Euler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Euler/euler1.html">The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.

%H G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Ward/ward2.html">Integer Sequences and Periodic Points</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3.

%H G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255. <a href="http://www.ams.org/mathscinet-getitem?mr=1990179">MR1990179</a>

%H Philipp Fahr and Claus Michael Ringel, <a href="http://www.mathematik.uni-bielefeld.de/~ringel/opus/fr-zwei.pdf">Categorification of the Fibonacci Numbers Using Representations of Quivers</a>

%H Sergio Falcon, <a href="http://ijism.org/administrator/components/com_jresearch/files/publications/IJISM_816_FINAL.pdf">Generating Function of Some k-Fibonacci and k-Lucas Sequences</a>, International Journal of Innovation in Science and Mathematics (2019) Vol. 7, Issue 2, 2347-9051.

%H Sergio Falcón, <a href="http://doi.org/10.26713/cma.v10i3.1221">Binomial Transform of the Generalized k-Fibonacci Numbers</a>, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.

%H Bakir Farhi, <a href="https://www.emis.de/journals/JIS/VOL22/Farhi/farhi19.html">Summation of Certain Infinite Lucas-Related Series</a>, J. Int. Seq., Vol. 22 (2019), Article 19.1.6.

%H John Farrier, <a href="http://uploads.neatorama.com/wp-content/uploads/2010/09/1nT6a-500x296.jpg">Fibonacci Pigeons</a> [From Sarah Spolaor, Sep 30 2010]

%H Massimiliano Fasi and Gian Maria Negri Porzio, <a href="http://eprints.maths.manchester.ac.uk/2709/">Determinants of Normalized Bohemian Upper Hessemberg Matrices</a>, University of Manchester (England, 2019).

%H Helaman and Claire Ferguson, <a href="http://www.ams.org/notices/201007/rtx100700840p.pdf">Celebrating Mathematics in Stone and Bronze</a>, Notices of the American Mathematical Society, 57 (2010), 840-850. See page 844.

%H Emmanuel Ferrand, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Ferrand/ferrand8.html">Deformations of the Taylor Formula</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.

%H Rigoberto Flórez, Robinson A. Higuita, and Antara Mukherjee, <a href="https://arxiv.org/abs/1804.02481">The Geometry of some Fibonacci Identities in the Hosoya Triangle</a>, arXiv:1804.02481 [math.NT], 2018.

%H D. Foata and G.-N. Han, <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub71.html">Nombres de Fibonacci et polynomes orthogonaux</a>, Leonardo Fibonacci: il tempo, le opere, l'eredità scientifica (1994), 179-208.

%H Robert Frontczak, Taras Goy, <a href="https://doi.org/10.15330/cmp.12.1.34-45">Mersenne-Horadam identities using generating functions</a>, Carpathian Math. Publ. (2020) Vol. 12, No. 1, 34-45.

%H I. Galkin, <a href="http://ulcar.uml.edu/~iag/CS/Fibonacci.html">"Fibonacci Numbers Spelled Out"</a>

%H Dale Gerdemann, <a href="http://www.youtube.com/watch?v=YpTSfkqS7zg">Video of Fibonacci tree</a>

%H Dale Gerdemann, <a href="http://bit.ly/lw7pP2">Video of Fibonacci tree(s)</a> (another version)

%H Dale Gerdemann, <a href="http://www.youtube.com/watch?v=AvRdzZMcUrI">Golden Ratio Base Contains Zeckendorf and Negative Indexed Bunder Forms</a>

%H C. J. Glasby, S. P. Glasby, F. Pleijel, <a href="http://dx.doi.org/10.1098/rspb.2008.0418">Worms by number</a>, Proc. Roy. Soc. B, Proc. Biol. Sci. 275 (1647) (2008) 2071-2076.

%H L. Goldsmith, <a href="https://web.archive.org/web/20050120014638/http://people.bath.ac.uk/ma2lag/fibonaccinumbers.html">The Fibonacci Numbers</a> [Wayback Machine link from _Felix Fröhlich_, Sep 06 2019]

%H Taras Goy and Mark Shattuck, <a href="https://www.pvamu.edu/aam/wp-content/uploads/sites/182/2019/12/05-R1320_AAM_Shattuck_MS_082819_Published_121119.pdf">Fibonacci and Lucas identities from Toeplitz-Hessenberg matrices</a>, Applications and Applied Mathematics: An International Journal, 14:2 (2019), 699-715.

%H Taras Goy and Mark Shattuck, <a href="https://arxiv.org/abs/2003.10660">Determinant Identities for Toeplitz-Hessenberg Matrices with Tribonacci Number Entries</a>, arXiv:2003.10660 [math.CO], 2020.

%H Hank Green, <a href="https://www.youtube.com/watch?v=wTlw7fNcO-0">The Fibonacci Sequence: Nature's Code</a> (2012).

%H M. Griffiths, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Griffiths/griffiths16.html">A Restricted Random Walk defined via a Fibonacci Process</a>, Journal of Integer Sequences, Vol. 14 (2011), #11.5.4.

%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.

%H R. K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]

%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.

%H Paul Hankin, <a href="https://blog.paulhankin.net/fibonacci/">An integer formula for Fibonacci numbers</a>, blog post, April 2015.

%H S. Happersett, <a href="http://dx.doi.org/10.1080/17513470701210626">Mathematical meditations</a>, Journal of Mathematics and the Arts, 1(1) (2007), 29-33.

%H Brady Haran and Colm Mulcahy, <a href="https://www.youtube.com/watch?v=4izjrtR8Ozg">Little Fibs</a>, Numberphile video (2016).

%H Tian-Xiao He, Peter J.-S. Shiue, Zihan Nie, and Minghao Chen, <a href="https://doi.org/10.3934/era.2020057">Recursive sequences and Girard-Waring identities with applications in sequence transformation</a>, Electronic Research Archive (2020) Vol. 28, No. 2, 1049-1062.

%H J. Hermes, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002255200">Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden</a>, Math. Ann., 45 (1894), 371-380.

%H A. P. Hillman and G. L. Alexanderson, Algebra Through Problem Solving, Chapter 2 pp. 11-16, <a href="http://education.lanl.gov/RESOURCES/ATPS/CHPTR02/P011.HTM">The Fibonacci and Lucas Numbers</a> [broken link]

%H A. M. Hinz, S. Klavžar, and U. Milutinović, and C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 12. <a href="http://tohbook.info">Book's website</a>

%H Andreas M. Hinz and Paul K. Stockmeyer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Hinz/hinz5.html">Precious Metal Sequences and Sierpinski-Type Graphs</a>, J. Integer Seq., Vol 25 (2022), Article 22.4.8.

%H V. E. Hoggatt and C. T. Long, <a href="http://www.fq.math.ca/Scanned/12-2/hoggatt1.pdf">Divisibility Properties of Generalized Fibonacci Polynomials</a>, Fibonacci Quarterly, 12:113-120, 1974.

%H Brian Hopkins, Aram Tangboonduangjit, <a href="https://www.fq.math.ca/Papers1/60-5/hopkins.pdf">Verifying and generalizing Arndt's compositions</a>, The Fibonacci Quarterly, December 2022.

%H Q.-H. Hou, Z.-W. Sun and H.-M. Wen, <a href="http://arxiv.org/abs/1208.3903">On monotonicity of some combinatorial sequences</a>, arXiv:1208.3903 [math.CO], 2012-2014.

%H J. Huang, <a href="https://arxiv.org/abs/1405.1636">Hecke algebras with independent parameters</a>, arXiv:1405.1636 [math.RT], 2014; Journal of Algebraic Combinatorics 43 (2016) 521-551.

%H C. W. Huegy and D. B. West, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00239-4">A Fibonacci tiling of the plane</a>, Discrete Math., 249 (2002), 111-116.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=9">Encyclopedia of Combinatorial Structures 9</a>

%H Milan Janjić, <a href="https://arxiv.org/abs/1905.04465">On Restricted Ternary Words and Insets</a>, arXiv:1905.04465 [math.CO], 2019.

%H Tina Hill Janzen, <a href="http://www.youtube.com/watch?v=2nAycC7sGVI">Fibonacci sequence / Golden scale</a> [broken link]

%H James P. Jones, <a href="http://www.fq.math.ca/Scanned/13-1/jones.pdf">Diophantine representation of the Fibonacci numbers</a>, Fibonacci Quarterly 13:1 (1975), pp. 84-88.

%H R. Jovanovic, <a href="https://web.archive.org/web/20141220015443/http://milan.milanovic.org/math/english/function/function.html">Fibonacci Function Calculator</a> [Wayback Machine link from _Felix Fröhlich_, Sep 06 2019]

%H R. Jovanovic, <a href="https://web.archive.org/web/20140410020348/http://milan.milanovic.org/math/english/pdf/Fibonacci.pdf">The relations between the Fibonacci and the Lucas numbers</a> [Wayback Machine link from _Felix Fröhlich_, Sep 06 2019]

%H R. Jovanovic, <a href="https://web.archive.org/web/20080921114314/http://milan.milanovic.org/math/Math.php?akcija=SviFibo">First 70 Fibonacci numbers</a> [Wayback Machine link from _Felix Fröhlich_, Sep 06 2019]

%H Ivana Jovović and Branko Malešević, <a href="http://nntdm.net/volume-23-2017/number-1/28-38/">Some Enumerations of Non-trivial Composition of the Differential Operations and the Directional Derivative</a>, Notes on Number Theory and Discrete Mathematics 23, no. 1 (2017), 28-38. See Remark 2.9.

%H S. Kak, <a href="http://arXiv.org/abs/physics/0411195">The Golden Mean and the Physics of Aesthetics</a>, arXiv:physics/0411195 [physics.hist-ph], 2004.

%H P. W. Kasteleyn, <a href="https://doi.org/10.1016/0031-8914(61)90063-5">The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice</a>, Physica, 27 (1961), 1209-1225.

%H Manuel Kauers, Doron Zeilberger, <a href="https://arxiv.org/abs/2006.10205">Counting Standard Young Tableaux With Restricted Runs</a>, arXiv:2006.10205 [math.CO], 2020.

%H Louis H. Kauffman and Pedro Lopes, <a href="http://arXiv.org/abs/0710.3765">Graded forests and rational knots</a>, arXiv:0710.3765 [math.GT], 2007-2009.

%H Blair Kelly, <a href="http://mersennus.net/fibonacci//">Fibonacci and Lucas factorizations</a>

%H R. Keskin, Z. Yosma, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Keskin/keskin3.html">On Fibonacci and Lucas Numbers of the form c*x^2</a>, J. Int. Seq. 14 (2011) # 11.9.3.

%H C. Kimberling, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Kimberling/kimberling24.html">Matrix Transformations of Integer Sequences</a>, J. Integer Seqs., Vol. 6, 2003.

%H C. Kimberling, <a href="http://www.fq.math.ca/Scanned/17-1/kimberling1.pdf">Strong divisibility sequences and some conjectures</a>, Fib. Quart., 17 (1979), 13-17.

%H Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449, 2018.

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/">Fibonacci numbers and the golden section</a>

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html">Mathematics of the Fibonacci Series</a>

%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html">Fibonacci numbers with tables of F(0)-F(500).</a>

%H A. Krowne, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/FibonacciNumber.html">Fibonacci sequence</a> [broken link]

%H K. Kuhapatanakul, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Kuhapatanakul/kuha4.html">On the Sums of Reciprocal Generalized Fibonacci Numbers</a>, J. Int. Seq. 16 (2013) #13.7.1

%H Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, Fausto Jarquín-Zárate, <a href="https://arxiv.org/abs/1904.13002">The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d))</a>, arXiv:1904.13002 [math.NT], 2019.

%H D. H. Lehmer, <a href="/A002487/a002487_1.pdf">On Stern's Diatomic Series</a>, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]

%H Hendrik Lenstra, <a href="http://math.berkeley.edu/~hwl/papers/fibo.pdf">Profinite Fibonacci Numbers</a>

%H Leonardo of Pisa [Leonardo Pisano], <a href="/A000045/a000045.jpg">Illustration of initial terms</a>, from Liber Abaci [The Book of Calculation], 1202 (photo by David Singmaster).

%H M. A. Lerma, <a href="http://www.math.northwestern.edu/~mlerma/problem_solving/results/recurrences.pdf">Recurrence Relations</a>

%H F. Luca, V. J. M. Huguet, F. Nicolae, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Mejia/luca31.html">On the Euler Function of Fibonacci Numbers</a>, JIS 12 (2009) 09.6.6.

%H Édouard Lucas, <a href="https://gdz.sub.uni-goettingen.de/id/PPN598948236_0002?tify={%22pages%22:[76],%22view%22:%22info%22}">Note sur le triangle arithmétique de Pascal et sur la série de Lamé</a>, Nouvelle correspondance mathématique, Vol. 2 (1876), pp. 70-75.

%H Édouard Lucas, <a href="http://visualiseur.bnf.fr/Visualiseur?Destination=Gallica&amp;O=NUMM-99634">Recherches sur plusieurs ouvrages de Léonard de Pise et sur diverses questions d'arithmétique supérieure</a>, Bulletino di bibliografia e di storia delle scienze matematiche e fisiche, Vol. 10 (1877), pp. 129-193, 239-293; <a href="http://edouardlucas.free.fr/pdf/oeuvres/Leonard_de_Pise.pdf">alternative link</a>.

%H Édouard Lucas, <a href="http://www.mathstat.dal.ca/FQ/Books/Complete/simply-periodic.pdf">The Theory of Simply Periodic Numerical Functions</a>, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.

%H David Macdonald, <a href="https://www.youtube.com/watch?v=IGJeGOw8TzQ">Music From the Fibonacci Sequence</a>, Youtube video, Jun 17 2018

%H B. Malesevic, <a href="http://arxiv.org/abs/0704.0750">Some combinatorial aspects of differential operation composition on the space R^n </a> arXiv:0704.0750 [math.DG], 2007.

%H B C Manjunath, <a href="https://www.soundslice.com/slices/8klcc/">Fibonacci Tala</a>, recorded musical performance and synchronized player (2018).

%H John Mason, <a href="/A000045/a000045_1.jpg">Italian postage stamp celebrating 850 years since birth of Fibonacci</a>

%H Peter McCalla, Asamoah Nkwanta, <a href="https://arxiv.org/abs/1901.07092">Catalan and Motzkin Integral Representations</a>, arXiv:1901.07092 [math.NT], 2019.

%H Charles P. McKeague, <a href="http://www.youtube.com/watch?v=_NmSEEhtc1U">Fibonacci numbers from MathTV</a>

%H Graeme McRae, <a href="http://oeis.org/wiki/User:Graeme_McRae/Sum_of_2m_Consecutive_Fibonacci_Numbers">Sum of 2m consecutive Fibonacci numbers</a>

%H R. S. Melham, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Melham/melham3.html">Finite Reciprocal Sums Involving Summands that are Balanced Products of Generalized Fibonacci Numbers</a>, J. Int. Seq. 17 (2014) # 14.6.5.

%H R. S. Melahm, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Melham/melham8.html">Reciprocal Series of Squares of Fibonacci Related Sequences with Subscripts in Arithmetic Progression</a>, J. Int. Seq. 18 (2015) 15.8.7.

%H D. Merlini, R. Sprugnoli and M. C. Verri, <a href="https://doi.org/10.1016/S0304-3975(98)00204-7">Strip tiling and regular grammars</a>, Theoret. Computer Sci. 242, 1-2 (2000) 109-124.

%H D. Merrill, <a href="http://pw1.netcom.com/~merrills/fibphi.html">The Fib-Phi Link Page</a> [broken link]

%H Ângela Mestre, José Agapito, <a href="https://www.emis.de/journals/JIS/VOL22/Agapito/mestre8.html">A Family of Riordan Group Automorphisms</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.

%H Jean-Christophe Michel, <a href="http://framy.free.fr/fibonacci%20dans%20mandelbrot.htm">Le nombre d'or dans l'ensemble de Mandelbrot</a> (in French, 'The golden number in the Mandelbrot set')

%H A. Milicevic and N. Trinajstic, <a href="https://www.cmm.ki.si/~FAMNIT-knjiga/wwwANG/web-pages/405_469_tcm18-67839%255B1%255D.pdf">Combinatorial Enumeration in Chemistry</a>, Chem. Modell., Vol. 4, (2006), pp. 405-469.

%H Kerry Mitchell, <a href="http://kerrymitchellart.com/articles/Spirolateral-Type_Images_from_Integer_Sequences.pdf">Spirolateral-Type Images from Integer Sequences</a>, 2013.

%H H. Mishima, Factorizations of Fibonacci numbers <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha108.htm">n=1..100</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha109.htm">n=101..200</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha110.htm">n=201..300</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha111.htm">n=301..400</a>, <a href="http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha112.htm">n=401..480</a>

%H P. Moree, <a href="http://arXiv.org/abs/math.CO/0311205">Convoluted convolved Fibonacci numbers</a>, arXiv:math/0311205 [math.CO], 2003.

%H R. Mullen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Mullen/mullen2.html">On Determining Paint by Numbers Puzzles with Nonunique Solutions</a>, JIS 12 (2009) 09.6.5.

%H Augustine O. Munagi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Munagi/munagi10.html">Integer Compositions and Higher-Order Conjugation</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.

%H Mariana Nagy, Simon R. Cowell, and Valeriu Beiu, <a href="https://doi.org/10.1109/ICCCC.2018.8390443">Are 3D Fibonacci spirals for real?: From science to arts and back to science</a>, 2018 7th International Conference on Computers Communications and Control (ICCCC), IEEE, 2018.

%H Mariana Nagy, Simon R. Cowell, Valeriu Beiu, <a href="https://arxiv.org/abs/1902.05944">Survey of Cubic Fibonacci Identities - When Cuboids Carry Weight</a>, arXiv:1902.05944 [math.HO], 2019.

%H László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Nemeth/nemeth6.html">The trinomial transform triangle</a>, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also <a href="https://arxiv.org/abs/1807.07109">arXiv:1807.07109</a> [math.NT], 2018.

%H Newton Institute, <a href="http://www.newton.cam.ac.uk/wmy2kposters/january">Posters in the London Underground</a>

%H Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.4.

%H OEIS Wiki, <a href="https://oeis.org/wiki/Autosequence">Autosequence</a>

%H J. J. O'Connor and E. F. Robertson, Mac Tutor History of Mathematics, <a href="http://www-history.mcs.st-andrews.ac.uk/Biographies/Hemchandra.html">Archarya Hemachandra</a>

%H Ahmet Öteleş, Zekeriya Y. Karata, Diyar O. Mustafa Zangana, <a href="https://www.emis.de/journals/JIS/VOL21/Oteles/ote5.html">Jacobsthal Numbers and Associated Hessenberg Matrices</a>, J. Int. Seq., Vol. 21 (2018), Article 18.2.5.

%H Arzu Özkoç, <a href="http://link.springer.com/article/10.1186/s13662-015-0486-7/fulltext.html">Some algebraic identities on quadra Fibona-Pell integer sequence</a>, Advances in Difference Equations, 2015, 2015:148.

%H Ram Krishna Pandey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Pandey/pandey7.html">On Some Magnified Fibonacci Numbers Modulo a Lucas Number</a>, Journal of Integer Sequences, Vol. 16 (2013), #13.1.7.

%H J. Patterson, <a href="http://www.bath.ac.uk/~ma1jmp/link.html">The Fibonacci Sequence</a>. [broken link]

%H Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/MAA/07-Sequence%20Pictures/mathgames_12_08_03.html">Sequence Pictures</a>, Math Games column, Dec 08 2003.

%H Ed Pegg, Jr., <a href="/A000043/a000043_2.pdf">Sequence Pictures</a>, Math Games column, Dec 08 2003 [Cached copy, with permission (pdf only)]

%H T. K. Petersen and B. E. Tenner, <a href="http://arxiv.org/abs/1202.4765">The depth of a permutation</a>, arXiv:1202.4765v1 [math.CO], 2012-2014.

%H Ivars Peterson, <a href="http://www.sciencenews.org/articles/20060603/mathtrek.asp">Fibonacci's Missing Flowers</a>.

%H Akos Pinter and Volker Ziegler, <a href="http://arxiv.org/abs/1005.3624">On Arithmetic Progressions in Recurrences - A new characterization of the Fibonacci sequence</a>, arXiv:1005.3624 [math.NT], 2010.

%H Simon Plouffe, Project Gutenberg, <a href="http://ibiblio.org/pub/docs/books/gutenberg/etext01/fbncc10.txt">The First 1001 Fibonacci Numbers</a> [broken link]

%H Project Nayuki, <a href="http://www.nayuki.io/page/fast-fibonacci-algorithms">Fast Fibonacci algorithms</a> (fast doubling is faster than matrix multiplication).

%H Phakhinkon Phunphayap, Prapanpong Pongsriiam, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Pongsriiam/pong12.html">Explicit Formulas for the p-adic Valuations of Fibonomial Coefficients</a>, J. Int. Seq. 21 (2018), #18.3.1.

%H S. Rabinowitz, <a href="http://www.mathpropress.com/stan/bibliography/algorithmicFib.pdf">Algorithmic Manipulation of Fibonacci Identities</a> (1996).

%H A. Radhakrishnan, L. Solus, and C. Uhler, <a href="https://doi.org/10.1016/j.dam.2018.03.015">Counting Markov equivalence classes for DAG models on trees</a>, Discrete Applied Mathematics 244 (2018): 170-185.

%H Arulalan Rajan, R. Vittal Rao, Ashok Rao and H. S. Jamadagni, <a href="http://arxiv.org/abs/1205.5398">Fibonacci Sequence, Recurrence Relations, Discrete Probability Distributions and Linear Convolution</a>, arXiv preprint arXiv:1205.5398 [math.PR], 2012. - From _N. J. A. Sloane_, Oct 23 2012

%H Aayush Rajasekaran, <a href="https://uwspace.uwaterloo.ca/bitstream/handle/10012/13202/Rajasekaran_Aaayush.pdf?sequence=3">Using Automata Theory to Solve Problems in Additive Number Theory</a>, MS thesis, University of Waterloo, 2018.

%H José L. Ramirez, Mark Shattuck, <a href="https://doi.org/10.1515/puma-2015-0034">Generalized Jacobsthal numbers and restricted k-ary words</a>, Pure Mathematics and Applications (2019) Vol. 28, Issue 1, 91-108.

%H Marc Renault, <a href="http://webspace.ship.edu/msrenault/fibonacci/FibThesis.pdf">The Fibonacci sequence under various moduli</a>, MSc Thesis, Wake Forest U, 1996.

%H N. Renton, <a href="http://www.users.bigpond.net.au/renton/903.htm">The fibonacci Series</a>

%H B. Rittaud, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Rittaud2/rittaud11.pdf">On the Average Growth of Random Fibonacci Sequences</a>, Journal of Integer Sequences, 10 (2007), Article 07.2.4.

%H Rosetta Code, <a href="http://rosettacode.org/wiki/Fibonacci_sequence">A collection of codes to compute fibonacci numbers with different computer languages</a>

%H E. S. Rowland, <a href="https://ericrowland.github.io/investigations/fibonacci.html">Fibonacci Sequence Calculator up to n=1474</a>

%H Michelle Rudolph-Lilith, <a href="http://arxiv.org/abs/1508.07894">On the Product Representation of Number Sequences, with Application to the Fibonacci Family</a>, arXiv preprint arXiv:1508.07894 [math.NT], 2015.

%H Shiva Samieinia, <a href="http://www.math.su.se/reports/2007/6/">Digital straight line segments and curves</a>. Licentiate Thesis. Stockholm University, Department of Mathematics, Report 2007:6.

%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Tsikouras/tsikouras67.html">On the Dominance Partial Ordering of Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.

%H D. Schweizer, <a href="http://math.holycross.edu/~davids/fibonacci/fibonacci.html">First 500 Fibonacci Numbers in blocks of 100.</a> [broken link]

%H Mark A. Shattuck, <a href="http://www.emis.de/journals/INTEGERS/papers/j5/j5.Abstract.html">Tiling proofs of some formulas for the Pell numbers of odd index</a>, Integers, 9 (2009), 53-64.

%H Mark A. Shattuck and Carl G. Wagner, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Shattuck/shattuck56.html">Periodicity and Parity Theorems for a Statistic on r-Mino Arrangements</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.6.

%H S. Silvia, <a href="http://arttech.about.com/library/weekly/aa060900a_fibonacci_sequence.htm">Fibonacci sequence</a> [broken link]

%H Parmanand Singh, <a href="http://dx.doi.org/10.1016/0315-0860(85)90021-7">The so-called Fibonacci numbers in ancient and medieval India</a>, Historia Mathematica, Volume 12 (3), 1985, 229-244.

%H Yüksel Soykan, <a href="https://doi.org/10.13140/RG.2.2.19903.87207">On Hyperbolic Numbers With Generalized Fibonacci Numbers Components</a>, Zonguldak Bülent Ecevit University (Turkey, 2019).

%H Yüksel Soykan, <a href="https://doi.org/10.9734/jamcs/2020/v35i130241">Generalized Fibonacci Numbers: Sum Formulas</a>, Journal of Advances in Mathematics and Computer Science (2020) Vol. 35, No. 1, 89-104.

%H Yüksel Soykan, <a href="https://doi.org/10.9734/AJARR/2020/v9i130212">Closed Formulas for the Sums of Squares of Generalized Fibonacci Numbers</a>, Asian Journal of Advanced Research and Reports (2020) Vol. 9, No. 1, 23-39, Article no. AJARR.55441.

%H Yüksel Soykan, <a href="https://doi.org/10.9734/ACRI/2020/v20i230177">Closed Formulas for the Sums of Cubes of Generalized Fibonacci Numbers: Closed Formulas of Sum_{k=0..n} W_k^3 and Sum_{k=1..n} W_(-k)^3</a>, Archives of Current Research International (2020) Vol. 20, Issue 2, 58-69.

%H Yüksel Soykan, <a href="https://doi.org/10.34198/ejms.4220.297331">A Study on Generalized Fibonacci Numbers: Sum Formulas Sum_{k=0..n} k * x^k * W_k^3 and Sum_{k=1..n} k * x^k W_-k^3 for the Cubes of Terms</a>, Earthline Journal of Mathematical Sciences (2020) Vol. 4, No. 2, 297-331.

%H Jaap Spies, <a href="http://www.jaapspies.nl/oeis/a000045.sage">Sage program for computing A000045</a>

%H Michael Z. Spivey and Laura L. Steil, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html">The k-Binomial Transforms and the Hankel Transform</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

%H Robin James Spivey, <a href="https://doi.org/10.7546/nntdm.2019.25.3.170-184">Close encounters of the golden and silver ratios</a>, Notes on Number Theory and Discrete Mathematics (2019) Vol. 25, No. 3, 170-184.

%H Z.-H. Sun, <a href="http://202.195.112.2/xsjl/szh/ConFn.pdf">Congruences For Fibonacci Numbers</a>

%H Asep K. Supriatna, Ema Carnia, Meksianis Z. Ndii, <a href="https://doi.org/10.1016/j.heliyon.2019.e01130">Fibonacci numbers: A population dynamics perspective</a>, Heliyon (2019) Vol. 5, Issue 1, e01130.

%H Roberto Tauraso, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Tauraso/tauraso3.html">A New Domino Tiling Sequence</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.3.

%H B. E. Tenner, <a href="https://arxiv.org/abs/2001.05011">Interval structures in the Bruhat and weak orders</a>, arXiv:2001.05011 [math.CO], 2020.

%H Thesaurus.Maths.org, <a href="http://thesaurus.maths.org/dictionary/map/word/3788">Fibonacci sequence</a> [broken link]

%H K. Tognetti, <a href="/A000045/a000045.pdf">Letter to N. J. A. Sloane (with attachments), May 25 1994</a>

%H K. Tognetti, <a href="/A000045/a000045_2.pdf">The Search for the Golden Sequence</a>, Draft Manuscript, May 25 1994.

%H K. Tognetti, <a href="http://www.austms.org.au/Modules/Fib">Fibonacci-His Rabbits and His Numbers and Kepler</a>

%H Herman Tulleken, <a href="https://www.researchgate.net/publication/333296614_Polyominoes">Polyominoes 2.2: How they fit together</a>, (2019).

%H Van Ravenstein, Tony. <a href="https://doi.org/10.1017/S1446788700031062">The three gap theorem (Steinhaus conjecture)</a>, Journal of the Australian Mathematical Society (Series A) 45.03 (1988): 360-370.

%H Tony van Ravenstein, <a href="/A000045/a000045_1.pdf">The three gap theorem (Steinhaus conjecture)</a>, Journal of the Australian Mathematical Society (Series A) 45.03 (1988): 360-370. [Annotated scanned copy]

%H C. Vila, <a href="http://www.boingboing.net/2010/03/22/dreamlike-animation.html">Nature by numbers</a> (animation).

%H Christobal Vila, <a href="http://wimp.com/naturenumbers/">Nature Numbers</a> (Video related to Fibonacci numbers)

%H N. N. Vorob'ev, <a href="http://eom.springer.de/F/f040020.htm">Fibonacci numbers</a>, Springer's Encyclopaedia of Mathematics.

%H A. Y. Z. Wang, P. Wen, <a href="https://doi.org/10.1186/s13660-015-0595-6">On the partial finite sums of the reciprocals of the Fibonacci numbers</a>, Journal of Inequalities and Applications, 2015.

%H Kai Wang, <a href="https://www.researchgate.net/publication/337943524_Fibonacci_Numbers_And_Trigonometric_Functions_Outline">Fibonacci Numbers And Trigonometric Functions Outline</a>, (2019).

%H Carl G. Wagner, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Wagner/wagner3.html">Partition Statistics and q-Bell Numbers (q = -1)</a>, J. Integer Seqs., Vol. 7, 2004.

%H Robert Walker, <a href="http://www.youtube.com/watch?v=Wx4ZfuMl-FI&amp;NR=1">Inharmonic "Golden Rhythmicon" - Fibonacci Sequence in Pairs Approaching Golden Ratio - With Bounce</a>

%H Kai Wang, <a href="https://www.researchgate.net/publication/339487198_On_k-Fibonacci_Sequences_And_Infinite_Series_List_of_Results_and_Examples">On k-Fibonacci Sequences And Infinite Series List of Results and Examples</a>, 2020.

%H L. C. Washington, <a href="https://www.fq.math.ca/Scanned/19-2/washington.pdf">Benford's Law for Fibonacci and Lucas numbers</a>, Fib. Quarterly, 19-2 1981, pp. 175-177.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciNumber.html">Fibonacci Number</a>, <a href="http://mathworld.wolfram.com/Double-FreeSet.html">Double-Free Set</a>, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>, <a href="http://mathworld.wolfram.com/ResistorNetwork.html">Resistor Network</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HosoyaIndex.html">Hosoya Index</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>

%H Wikipedia, <a href="http://www.wikipedia.org/wiki/Fibonacci_number">Fibonacci number</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cassini_and_Catalan_identities">Cassini and Catalan identities</a>

%H Willem's Fibonacci site, <a href="http://home.zonnet.nl/LeonardEuler/fiboe.htm">Fibonacci</a>

%H Mike Winkler, <a href="http://arxiv.org/abs/1412.0519">On the structure and the behaviour of Collatz 3n + 1 sequences - Finite subsequences and the role of the Fibonacci sequence</a>, arXiv:1412.0519 [math.GM], 2014.

%H Roman Witula, Damian Slota and Edyta Hetmaniok, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_41_from255to263.pdf">Bridges between different known integer sequences</a>, Annales Mathematicae et Informaticae, 41 (2013) pp. 255-263.

%H R. Yanco, <a href="/A007380/a007380.pdf">Letter and Email to N. J. A. Sloane, 1994</a>

%H R. Yanco and A. Bagchi, <a href="/A007380/a007380_1.pdf">K-th order maximal independent sets in path and cycle graphs</a>, Unpublished manuscript, 1994. (Annotated scanned copy)

%H Donovan Young, <a href="https://www.emis.de/journals/JIS/VOL21/Young/young2.html">The Number of Domino Matchings in the Game of Memory</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.1.

%H Donovan Young, <a href="https://arxiv.org/abs/1905.13165">Generating Functions for Domino Matchings in the 2 * k Game of Memory</a>, arXiv:1905.13165 [math.CO], 2019. Also in <a href="https://www.emis.de/journals/JIS/VOL22/Young/young13.html">J. Int. Seq.</a>, Vol. 22 (2019), Article 19.8.7.

%H Aimei Yu and Xuezheng Lv, <a href="http://dx.doi.org/10.1007/s10910-006-9088-7">The Merrifield-Simmons indices and Hosoya indices of trees with k pendant vertices</a>, J. Math. Chem., Vol. 41 (2007), pp. 33-43. See page 35.

%H Tianping Zhang and Yuankui Ma, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Zhang/zhang56.html">On Generalized Fibonacci Polynomials and Bernoulli Numbers</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.3.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1).

%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>

%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>

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

%F G.f.: Sum_{n>=0} x^n * Product_{k=1..n} (k + x)/(1 + k*x). - _Paul D. Hanna_, Oct 26 2013

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

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

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

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

%F F(n+1) = Sum_{j=0..floor(n/2)} binomial(n-j, j).

%F 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

%F E.g.f.: (2/sqrt(5))*exp(x/2)*sinh(sqrt(5)*x/2). - _Len Smiley_, Nov 30 2001

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

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

%F 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

%F 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

%F From _Kurmang. Aziz. Rashid_, Feb 21 2004: (Start)

%F 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). [For a proof see Comments section.]

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

%F [Two more conjectures removed by _Peter Luschny_, Nov 17 2017]

%F Theorem 1: for n >= 0, (F(n+3)^ 2 - F(n+1)^ 2)/F(n+2) = (F(n+3)+ F(n+1)).

%F Theorem 2: for n >= 0, F(n+10) = 11*F(n+5) + F(n).

%F Theorem 3: for n >= 6, F(n) = 4*F(n-3) + F(n-6). (End)

%F 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

%F 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

%F 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

%F For x > phi, Sum_{n>=0} F(n)/x^n = x/(x^2 - x - 1). - _Gerald McGarvey_, Oct 27 2004

%F 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

%F a(n-1) = Sum_{k=0..n} (-1)^k*binomial(n-ceiling(k/2), floor(k/2)). - _Benoit Cloitre_, May 05 2005

%F a(n) = Sum_{k=0..n} abs(A108299(n, k)). - _Reinhard Zumkeller_, Jun 01 2005

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

%F F(n+1) = Sum_{k=0..n} binomial((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2. - _Paul Barry_, Aug 28 2005

%F Fibonacci(n) = Product_{j=1..ceiling(n/2)-1} (1 + 4(cos(j*Pi/n))^2). [Bicknell and Hoggatt, pp. 47-48.] - _Emeric Deutsch_, Oct 15 2006

%F F(n) = 2^-(n-1)*Sum_{k=0..floor((n-1)/2)} binomial(n,2*k+1)*5^k. - _Hieronymus Fischer_, Feb 07 2006

%F a(n) = (b(n+1) + b(n-1))/n where {b(n)} is the sequence A001629. - _Sergio Falcon_, Nov 22 2006

%F 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

%F From _Miklos Kristof_, Mar 19 2007: (Start)

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

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

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

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

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

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

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

%F   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   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   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   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)

%F A corollary to Kristof 2007 is 2*F(a+b) = F(a)*L(b) + L(a)*F(b). - _Graeme McRae_, Apr 24 2014

%F For n > m, the sum of the 2m consecutive Fibonacci numbers F(n-m-1) thru F(n+m-2) 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 F(n) = b(n) + (p-1)*Sum_{k=2..n-1} floor(b(k)/p)*F(n-k+1) where b(k) is the digital sum analog of the Fibonacci recurrence, defined by b(k) = ds_p(b(k-1)) + ds_p(b(k-2)), b(0)=0, b(1)=1, ds_p=digital sum base p. Example for base p=10: F(n) = A010077(n) + 9*Sum_{k=2..n-1} A059995(A010077(k))*F(n-k+1). - _Hieronymus Fischer_, Jul 01 2007

%F F(n) = b(n)+p*Sum_{k=2..n-1} floor(b(k)/p)*F(n-k+1) where b(k) is the digital product analog of the Fonacci recurrence, defined by b(k) = dp_p(b(k-1)) + dp_p(b(k-2)), b(0)=0, b(1)=1, dp_p=digital product base p. Example for base p=10: F(n) = A074867(n) + 10*Sum_{k=2..n-1} A059995(A074867(k))*F(n-k+1). - _Hieronymus Fischer_, Jul 01 2007

%F 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 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

%F a(2^n) = Product_{i=0..n-2} B(i) where B(i) is A001566. Example 3*7*47 = F(16). - _Kenneth J Ramsey_, Apr 23 2008

%F a(n+1) = Sum_{k=0..n} A109466(n,k)*(-1)^(n-k). -_Philippe Deléham_, Oct 26 2008

%F a(n) = Sum_{l_1=0..n+1} Sum_{l_2=0..n}...Sum_{l_i=0..n-i}... Sum_{l_n=0..1} delta(l_1,l_2,...,l_i,...,l_n), where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i + l_(i+1) >= 2 for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. - _Thomas Wieder_, Feb 25 2009

%F a(n+1) = 2^n sqrt(Product_{k=1..n} cos(k Pi/(n+1))^2+1/4) (Kasteleyn's formula specialized). - _Sarah-Marie Belcastro_, Jul 04 2009

%F 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

%F 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

%F Limit_{k->oo} 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

%F For n >= 1, F(n) = round(log_2(2^(phi*F(n-1)) + 2^(phi*F(n-2)))), where phi is the golden ratio. - _Vladimir Shevelev_, Jun 24 2010, Jun 27 2010

%F 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

%F a(n) = 2*a(n-2) + a(n-3), n > 2. - _Gary Detlefs_, Sep 08 2010

%F a(2^n) = Product_{i=0..n-1} A000032(2^i). - _Vladimir Shevelev_, Nov 28 2010

%F a(n)^2 - a(n-1)^2 = a(n+1)*a(n-2), see A121646.

%F a(n) = sqrt((-1)^k*(a(n+k)^2 - a(k)*a(2n+k))), for any k. - _Gary Detlefs_, Dec 03 2010

%F F(2*n) = F(n+2)^2 - F(n+1)^2 - 2*F(n)^2. - _Richard R. Forberg_, Jun 04 2011

%F From _Artur Jasinski_, Nov 17 2011: (Start)

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

%F F(n) = F(n+2) - 1 + (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 F(n) = 1 + Sum_{x=1..n-2} F(x). - _Joseph P. Shoulak_, Feb 05 2012

%F F(n) = 4*F(n-2) - 2*F(n-3) - F(n-6). - _Gary Detlefs_, Apr 01 2012

%F F(n) = round(phi^(n+1)/(phi+2)). - _Thomas Ordowski_, Apr 20 2012

%F From _Sergei N. Gladkovskii_, Jun 03 2012: (Start)

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

%F Let E(x) be the e.g.f., i.e.,

%F 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

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

%F (End)

%F From _Hieronymus Fischer_, Nov 30 2012: (Start)

%F F(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).

%F Example: F(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.

%F F(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.

%F Since S(j,n) = binomial(n-2+j,j-1), the formula above equals the well-known binomial formula, essentially. (End)

%F G.f.: A(x) = x / (1 - x / (1 - x / (1 + x))). - _Michael Somos_, Jan 04 2013

%F Sum_{n >= 1} (-1)^(n-1)/(a(n)*a(n+1)) = 1/phi (phi=golden ratio). - _Vladimir Shevelev_, Feb 22 2013

%F From _Raul Prisacariu_, Oct 29 2023: (Start)

%F For odd k, Sum_{n >= 1} a(k)^2*(-1)^(n-1)/(a(k*n)*a(k*n+k)) = phi^(-k).

%F For even  k, Sum_{n >= 1} a(k)^2/(a(k*n)*a(k*n+k)) = phi^(-k). (End)

%F From _Vladimir Shevelev_, Feb 24 2013: (Start)

%F (1) Expression a(n+1) via a(n): a(n+1) = (a(n) + sqrt(5*(a(n))^2 + 4*(-1)^n))/2;

%F (2) Sum_{k=1..n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);

%F (3) a(n)/a(n+1) = 1/phi + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)

%F 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:= Chebyshev polynomial of the 2nd kind, i=sqrt(-1)). - _Bill Gosper_, Mar 04 2013

%F 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

%F 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

%F 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

%F 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

%F 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

%F Let b(n) = b(n-1) + b(n-2), with b(0) = 0, b(1) = phi. Then, for n >= 2, F(n) = floor(b(n-1)) if n is even, F(n) = ceiling(b(n-1)), if n is odd, with convergence. - _Richard R. Forberg_, Jan 19 2014

%F a(n) = Sum_{t1*g(1)+t2*g(2)+...+tn*g(n)=n} multinomial(t1+t2+...+tn,t1,t2,...,tn), where g(k)=2*k-1. - _Mircea Merca_, Feb 27 2014

%F F(n) = round(sqrt(F(n-1)^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(n-1) + a(n-2), for any two values of a(0) and a(1), if n is sufficiently large. - _Richard R. Forberg_, Jul 27 2014

%F 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(n-1) + a(n-2), for any two values of a(0) and a(1), if n is sufficiently large. - _Richard R. Forberg_, Aug 03 2014

%F F(n) = round(1/(Sum_{j>=n+2} 1/F(j))). - _Richard R. Forberg_, Aug 14 2014

%F a(n) = hypergeometric([-n/2+1/2, -n/2+1], [-n+1], -4) for n >= 2. - _Peter Luschny_, Sep 19 2014

%F Limit_{n -> oo} (log F(n+1)/log F(n))^n = e. - _Thomas Ordowski_, Oct 06 2014

%F F(n) = (L(n+1)^2 - L(n-1)^2)/(5*L(n)), where L(n) is A000032(n), with a similar inverse relationship. - _Richard R. Forberg_, Nov 17 2014

%F Consider the graph G[1-vertex;1-loop,2-loop] in comment above. Construct the power matrix array T(n,j) = [A^*j]*[S^*(j-1)] 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 n-walks containing (j) loops and a(n-1) = Sum_{j=1..n} T(n,j). - _David Neil McGrath_, Nov 21 2014

%F 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(n-k+3) - F(k-1)*F(n-k+2) - F(k-2)*F(n-k) + (-1)^k*F(n-2k+2). - _Charlie Marion_, Dec 04 2014

%F 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 F(2*n) = F(n+1)^2 - F(n-1)^2, similar to Koshy (D) and Forberg 2011, but different. - _Hermann Stamm-Wilbrandt_, Aug 12 2015

%F F(n+1) = ceiling( (1/phi)*Sum_{k=0..n} F(k) ). - _Tom Edgar_, Sep 10 2015

%F a(n) = (L(n-3) + L(n+3))/10 where L(n)=A000032(n). - _J. M. Bergot_, Nov 25 2015

%F From _Bob Selcoe_, Mar 27 2016: (Start)

%F F(n) = (F(2n+k+1) - F(n+1)*F(n+k+1))/F(n+k), k >= 0.

%F Thus when k=0: F(n) = sqrt(F(2n+1) - F(n+1)^2).

%F F(n) = (F(3n) - F(n+1)^3 + F(n-1)^3)^(1/3).

%F 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 Fibonacci-type sequences with any two seed values for a(0) and a(1) (e.g., Lucas sequence A000032: a(0)=2, a(1)=1).

%F (End)

%F F(n) = L(k)*F(n-k) + (-1)^(k+1)*F(n-2k) for all k >= 0, where L(k) = A000032(k). - _Anton Zakharov_, Aug 02 2016

%F From _Ilya Gutkovskiy_, Aug 03 2016: (Start)

%F a(n) = F_n(1), where F_n(x) are the Fibonacci polynomials.

%F Inverse binomial transform of A001906.

%F 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)

%F For n >= 2, a(n) = 2^(n^2+n) - (4^n-2^n-1)*floor(2^(n^2+n)/(4^n-2^n-1)) - 2^n*floor(2^(n^2) - (2^n-1-1/2^n)*floor(2^(n^2+n)/(4^n-2^n-1))). - _Benoit Cloitre_, Apr 17 2017

%F f(n+1) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2j,k)*binomial(j,k). - _Tony Foster III_, Sep 04 2017

%F F(n) = Sum_{k=0..floor((n-1)/2)} ( (n-k-1)! / ((n-2k-1)! * k!) ). - _Zhandos Mambetaliyev_, Nov 08 2017

%F For x even, F(n) = (F(n+x) + F(n-x))/L(x). For x odd, F(n) = (F(n+x) - F(n-x))/L(x) where n >= x in both cases. Therefore F(n) = F(2*n)/L(n) for n >= 0. - _David James Sycamore_, May 04 2018

%F From _Isaac Saffold_, Jul 19 2018: (Start)

%F Let [a/p] denote the Legendre symbol. Then, for an odd prime p:

%F   F(p+n) == [5/p]*F([5/p]+n) (mod p), if [5/p] = 1 or -1.

%F   F(p+n) == 3*F(n) (mod p), if [5/p] = 0 (i.e., p = 5).

%F   This is true for negative-indexed terms as well, if this sequence is extended by the negafibonacci numbers (i.e., F(-n) = A039834(n)). (End)

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

%F a(n) = A090888(0, n+1) = A118654(0, n+1) = A118654(1, n-1) = A109754(0, n) = A109754(1, n-1), for n > 0.

%F a(n) = (L(n-3) + L(n-2) + L(n-1) + L(n))/5 with L(n)=A000032(n). - _Art Baker_, Jan 04 2019

%F F(n) = F(k-1)*F(abs(n-k-2)) + F(k-1)*F(n-k-1) + F(k)*F(abs(n-k-2)) + 2*F(k)*F(n-k-1), for n > k > 0. - _Joseph M. Shunia_, Aug 12 2019

%F F(n) = F(n-k+2)*F(k-1) + F(n-k+1)*F(k-2) for all k such that 2 <= k <= n. - _Michael Tulskikh_, Oct 09 2019

%F F(n)^2 - F(n+k)*F(n-k) = (-1)^(n+k) * F(k)^2 for 2 <= k <= n [Catalan's identity]. - _Hermann Stamm-Wilbrandt_, May 07 2021

%F Sum_{n>=1} 1/a(n) = A079586 is the reciprocal Fibonacci constant. - _Gennady Eremin_, Aug 06 2021

%F a(n) = Product_{d|n} b(d) = Product_{k=1..n} b(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} b(n/gcd(n,k))^(1/phi(n/gcd(n,k))) where b(n) = A061446(n) = primitive part of a(n), phi(n) = A000010(n). - _Richard L. Ollerton_, Nov 08 2021

%F a(n) = 2*i^(1-n)*sin(n*arccos(i/2))/sqrt(5), i=sqrt(-1). - _Bill Gosper_, May 05 2022

%F a(n) = i^(n-1)*sin(n*c)/sin(c) = i^(n-1)*sin(c*n)*csc(c), where c = Pi/2 + i*arccsch(2). - _Peter Luschny_, May 23 2022

%F F(2n) = Sum_{k=1..n} (k/5)*binomial(2n, n+k), where (k/5) is the Legendre or Jacobi Symbol; F(2n+1)= Sum_{k=1..n} (-(k+2)/5)*binomial(2n+1, n+k), where (-(k+2)/5) is the Legendre or Jacobi Symbol. For example, F(10) = 1*binomial(10,6) - 1*binomial(10,7) - 1*binomial(10,8) + 1*binomial(10,9) + 0*binomial(10,10), F(11) = 1*binomial(11,6) - 1*binomial(11,7) + 0*binomial(11,8) - 1*binomial(11,9) + 1*binomial(11,10) + 1*binomial(11,11). - _Yike Li_, Aug 21 2022

%F For n > 0, 1/F(n) = Sum_{k>=1} F(n*k)/(F(n+2)^(k+1)). - _Diego Rattaggi_, Oct 26 2022

%F From _Andrea Pinos_, Dec 02 2022: (Start)

%F For n == 0 (mod 4): F(n) = F((n+2)/2)*( F(n/2) + F((n/2)-2) ) + 1;

%F For n == 1 (mod 4): F(n) = F((n-1)/2)*( F((n-1)/2) + F(2+(n-1)/2) ) + 1;

%F For n == 2 (mod 4): F(n) = F((n-2)/2)*( F(n/2) + F((n/2)+2) ) + 1;

%F For n == 3 (mod 4): F(n) = F((n-1)/2)*( F((n-1)/2) + F(2+(n-1)/2) ) - 1. (End)

%e 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 terms of the sequence. - _Cino Hilliard_, Sep 15 2008

%e From _Joerg Arndt_, May 21 2013: (Start)

%e 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:

%e 01:  [ 2 1 2 1 1 ]

%e 02:  [ 2 1 3 1 ]

%e 03:  [ 2 1 4 ]

%e 04:  [ 3 1 2 1 ]

%e 05:  [ 3 1 3 ]

%e 06:  [ 3 2 2 ]

%e 07:  [ 4 1 2 ]

%e 08:  [ 4 2 1 ]

%e 09:  [ 4 3 ]

%e 10:  [ 5 1 1 ]

%e 11:  [ 5 2 ]

%e 12:  [ 6 1 ]

%e 13:  [ 7 ]

%e 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:

%e 01:  [ 1 2 1 2 ]

%e 02:  [ 1 3 1 1 ]

%e 03:  [ 1 3 2 ]

%e 04:  [ 1 4 1 ]

%e 05:  [ 1 5 ]

%e 06:  [ 2 2 1 1 ]

%e 07:  [ 2 3 1 ]

%e 08:  [ 2 4 ]

%e 09:  [ 3 2 1 ]

%e 10:  [ 3 3 ]

%e 11:  [ 4 2 ]

%e 12:  [ 5 1 ]

%e 13:  [ 6 ]

%e (End)

%e Partially ordered partitions of (n-1) 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

%e 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

%p A000045 := proc(n) combinat[fibonacci](n); end;

%p 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

%p spec := [B, {B=Sequence(Set(Z, card>1))}, unlabeled ]: seq(combstruct[count](spec, size=n), n=1..39); # _Zerinvary Lajos_, Apr 04 2008

%p # The following Maple command isFib(n) yields true or false depending on whether n is a Fibonacci number or not.

%p with(combinat): isFib := proc(n) local a: a := proc(n) local j: for j while fibonacci(j) <= n do fibonacci(j) end do: fibonacci(j-1) end proc: evalb(a(n) = n) end proc: # _Emeric Deutsch_, Nov 11 2014

%t Table[Fibonacci[k], {k, 0, 50}] (* _Mohammad K. Azarian_, Jul 11 2015 *)

%t Table[2^n Sqrt @ Product[(Cos[Pi k/(n + 1)]^2 + 1/4), {k, n}] // FullSimplify, {n, 15}]; (* Kasteleyn's formula specialized, _Sarah-Marie Belcastro_, Jul 04 2009 *)

%t LinearRecurrence[{1, 1}, {0, 1}, 40] (* _Harvey P. Dale_, Aug 03 2014 *)

%t Fibonacci[Range[0, 20]] (* _Eric W. Weisstein_, Sep 22 2017 *)

%t CoefficientList[Series[-(x/(-1 + x + x^2)), {x, 0, 20}], x] (* _Eric W. Weisstein_, Sep 22 2017 *)

%o (Axiom) [fibonacci(n) for n in 0..50]

%o (Magma) [Fibonacci(n): n in [0..38]];

%o (Maxima) makelist(fib(n),n,0,100); /* _Martin Ettl_, Oct 21 2012 */

%o (PARI) a(n) = fibonacci(n)

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

%o (PARI) a(n)=my(phi=quadgen(5));(phi^n-(-1/phi)^n)/(2*phi-1) \\ _Charles R Greathouse IV_, Jun 17 2012

%o (Python) # From _Jaap Spies_, Jan 05 2007, updated by _Peter Luschny_, Feb 21 2023:

%o from itertools import islice

%o def fib_gen():

%o     x, y = 0, 1

%o     while True:

%o         yield x

%o         x, y = y, x + y

%o fib_list = lambda n: list(islice(fib_gen(), n))

%o (Python)

%o def A000045(n, F=[0,1]):

%o     F.extend(sum(F[-2:])for _ in range(n-len(F)+1)); return F[n] # _M. F. Hasler_, Feb 17 2023

%o (Sage) # Demonstration program from _Jaap Spies_:

%o a = sloane.A000045; # choose sequence

%o print(a)            # This returns the name of the sequence.

%o print(a(38))        # This returns the 38th term of the sequence.

%o print(a.list(39))   # This returns a list of the first 39 terms.

%o (Sage)

%o a = BinaryRecurrenceSequence(1,1); print([a(n) for n in range(20)])

%o # Closed form integer formula with F(1) = 0 from Paul Hankin (see link).

%o F = lambda n: (4<<(n-1)*(n+2))//((4<<2*(n-1))-(2<<(n-1))-1)&((2<<(n-1))-1)

%o print([F(n) for n in range(20)]) # _Peter Luschny_, Aug 28 2016

%o (Sage) print(list(fibonacci_sequence(0, 40))) # _Bruno Berselli_, Jun 26 2014

%o (Haskell)

%o -- Based on code from http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

%o -- which also has other versions.

%o fib :: Int -> Integer

%o fib n = fibs !! n

%o     where

%o         fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

%o {- Example of use: map fib [0..38] _Gerald McGarvey_, Sep 29 2009 -}

%o (Julia)

%o function fib(n)

%o    F = BigInt[1 1; 1 0]

%o    Fn = F^n

%o    Fn[2, 1]

%o end

%o println([fib(n) for n in 0:38]) # _Peter Luschny_, Feb 23 2017

%o (Julia) # faster

%o function fibrec(n::Int)

%o     n == 0 && return (BigInt(0), BigInt(1))

%o     a, b = fibrec(div(n, 2))

%o     c = a * (b * 2 - a)

%o     d = a * a + b * b

%o     iseven(n) ? (c, d) : (d, c + d)

%o end

%o fibonacci(n::Int) = fibrec(n)[1]

%o println([fibonacci(n) for n in 0:40]) # _Peter Luschny_, Apr 03 2022

%o (GAP)

%o Fib:=[0,1];; for n in [3..10^3] do Fib[n]:=Fib[n-1]+Fib[n-2]; od; Fib; # _Muniru A Asiru_, Sep 03 2017

%o (Scala) def fibonacci(n: BigInt): BigInt = {

%o   val zero = BigInt(0)

%o   def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {

%o     case `zero` => a

%o     case _ => fibTail(n - 1, b, a + b)

%o   }

%o   fibTail(n, 0, 1)

%o } // Based on "Case 3: Tail Recursion" from Carrasquel (2016) link

%o (0 to 49).map(fibonacci(_)) // _Alonso del Arte_, Apr 13 2019

%Y Cf. A001622 (phi), A039834 (signed Fibonacci numbers), A001519 (F(2n-1)), A001906 (F(2n)), A001690 (complement), A000213, A000288, A000322, A000383, A060455, A030186, A020695, A020701, A060280 (inv. Eul. Trans), 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, A163733, A073133, A166861 (Euler Transform), A337009 (Multiset Transf.).

%Y First row of arrays A103323, A172236, A234357. Second row of arrays A099390, A048887, and A092921 (k-generalized Fibonacci numbers).

%Y Cf. A001175 (Pisano periods), A001177 (Entry points), A001176 (number of zeros in a fundamental period).

%Y Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

%Y Fibonacci-Cayley triangle: A327992.

%Y Boustrophedon transforms: A000738, A000744.

%Y Powers: A103323, A105317, A254719.

%Y Numbers of prime factors: A022307 and A038575.

%Y Cf. A061446 (primitive part of Fibonacci numbers), A000010 (comments on product formulas).

%K nonn,core,nice,easy,hear,changed

%O 0,4

%A _N. J. A. Sloane_, 1964