### ----------------------------------------------------
### -- OEIS
### -- Licenses: Artistic-2.0
### -- Authors: Tobias Boege
### -- File: t/data/A000045.txt
### ----------------------------------------------------
### -- Chunk 5 of 6
 Feb 25 2009
%F A000045 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 (smbelcas(AT)toroidalsnark.net), Jul 04 2009
%F A000045 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 A000045 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 A000045 Lim_{k->infinity} F(k+n)/F(k) = (L(n) + F(n)*sqrt(5))/2 with the Lucas numbers L(n)= A000032(n). - _Johannes W. Meijer_, May 27 2010
%F A000045 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 A000045 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 A000045 a(n) = 2*a(n-2) + a(n-3), n > 2. - _Gary Detlefs_, Sep 08 2010
%F A000045 a(2^n) = Product_{i=0..n-1} A000032(2^i). - _Vladimir Shevelev_, Nov 28 2010
%F A000045 a(n)^2 - a(n-1)^2 = a(n+1)*a(n-2), see A121646.
%F A000045 a(n) = sqrt((-1)^k*(a(n+k)^2 - a(k)*a(2n+k))), for any k. - _Gary Detlefs_, Dec 03 2010
%F A000045 F(2*n) = F(n+2)^2 - F(n+1)^2 - 2*F(n)^2. - _Richard R. Forberg_, Jun 04 2011
%F A000045 (-1)^(n+1) = F(n)^2 + F(n)*F(1+n) - F(1+n)^2.
%F A000045   F(n) = -F(n+2)(-2 + (F(n+1))^4 + 2*(F(n+1)^3*F(n+2)) - (F(n+1)*F(n+2))^2 2*F(n+1)(F(n+2))^3 + (F(n+2))^4)- F(n+1). - _Artur Jasinski_, Nov 17 2011
%F A000045 F(n) = 1 + Sum_{x=1..n-2} F(x). - _Joseph P. Shoulak_, Feb 05 2012
%F A000045 F(n) = 4*F(n-2) - 2*F(n-3) - F(n-6). - _Gary Detlefs_, Apr 01 2012
%F A000045 F(n) = round(phi^(n+1)/(phi+2)). - _Thomas Ordowski_, Apr 20 2012
%F A000045 From _Sergei N. Gladkovskii_, Jun 03 2012: (Start)
%F A000045 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 A000045 Let E(x) be the e.g.f., i.e.,
%F A000045 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 A000045 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 A000045 (End)
%F A000045 From _Hieronymus Fischer_, Nov 30 2012: (Start)
%F A000045 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 A000045 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 A000045 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 A000045 Since S(j,n) = binomial(n-2+j,j-1), the formula above equals the well-known binomial formula, essentially. (End)
%F A000045 G.f. A(x) = x / (1 - x / (1 - x / (1 + x))). - _Michael Somos_, Jan 04 2013
%F A000045 Sum_{n >= 1} (-1)^(n-1)/(a(n)*a(n+1)) = 1/phi (phi=golden ratio). - _Vladimir Shevelev_, Feb 22 2013
%F A000045 From _Vladimir Shevelev_, Feb 24 2013: (Start)
%F A000045 (1) Expression a(n+1) via a(n): a(n+1) = (a(n) + sqrt(5*(a(n))^2 + 4*(-1)^n))/2;
%F A000045 (2) Sum_{k=1...n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);
%F A000045 (3) a(n)/a(n+1) = 1/phi + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)
%F A000045 F(n+1) = F(n)/2 + sqrt((-1)^n + 5*F(n)^2/4), n >= 0. F(n+1) = U_n(i/2)/i^n, (U:= Chebyshef 2nd kind). - _Bill Gosper_, Mar 04 2013
%F A000045 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 A000045 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 A000045 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 A000045 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 A000045 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 A000045 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) = ceil(b(n-1)), if n is odd, with convergence. - _Richard R. Forberg_, Jan 19 2014
%F A000045 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 A000045 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 A000045 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 A000045 F(n) = round(1/(Sum_{j>=n+2} 1/F(j))). - _Richard R. Forberg_, Aug 14 2014
%F A000045 a(n) = hypergeometric([-n/2+1/2, -n/2+1], [-n+1], -4) for n >= 2. - _Peter Luschny_, Sep 19 2014
%F A000045 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 A000045 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 A000045 Define F(-n) to be F(n) for n odd and -F(n) for n even. Then for all n and k, F(n) = 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 A000045 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 A000045 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 A000045 F(n+1) = ceiling( (1/phi)*Sum_{k=0..n} F(k) ). - _Tom Edgar_, Sep 10 2015
%F A000045 a(n) = (L(n-3) + L(n+3))/10 where L(n)=A000032(n). - _J. M. Bergot_, Nov 25 2015
%F A000045 From _Bob Selcoe_, Mar 27 2016 (Start):
%F A000045 F(n) = (F(2n+k+1) - F(n+1)*F(n+k+1))/F(n+k), k >= 0.
%F A000045 Thus when k=0: F(n) = sqrt(F(2n+1) - F(n+1)^2).
%F A000045 F(n) = cbrt(F(3n) - F(n+1)^3 + F(n-1)^3).
%F A000045 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 A000045 (End)
%F A000045 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 A000045 From _Ilya Gutkovskiy_, Aug 03 2016: (Start)
%F A000045 a(n) = F_n(1), where F_n(x) are the Fibonacci polynomials.
%F A000045 Inverse binomial transform of A001906.
%F A000045 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 A000045 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 A000045 For n > 0, a(n) = b(n+1) where b(n) = Sum_{k=1..n} b(n-k)*A000931(k-1), b(0) = 1. - _J. Conrad_, Apr 19 2017
%F A000045 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 A000045 F(n) = Sum_{k=0..floor((n-1)/2)} ( (n-k-1)! / ((n-2k-1)! * k!) ). - _Zhandos Mambetaliyev_, Nov 08 2017
%F A000045 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 A000045 From _Isaac Saffold_, Jul 19 2018: (Start)
%F A000045 Let [a/p] denote the Legendre symbol. Then, for an odd prime p:
%F A000045   F(p+n) == [5/p]*F([5/p]+n) (mod p), if [5/p] = 1 or -1.
%F A000045   F(p+n) == 3*F(n) (mod p), if [5/p] = 0 (i.e. p = 5).
%F A000045   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 A000045 a(n) = A094718(4, n). a(n) = A101220(0, j, n).
%F A000045 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 A000045 a(n) = (L(n-3) + L(n-2) + L(n-1) + L(n))/5 with L(n)=A000032(n). - _Art Baker_, Jan 04 2019
%e A000045 For x = 0,1,2,3,4, x=1/(x+1) = 1, 1/2, 2/3, 3/5, 5/8. These fractions have numerators 1,1,2,3,5, which are the 2nd to 6th entries in the sequence. - _Cino Hilliard_, Sep 15 2008
%e A000045 From _Joerg Arndt_, May 21 2013: (Start)
%e A000045 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 A000045 01:  [ 2 1 2 1 1 ]
%e A000045 02:  [ 2 1 3 1 ]
%e A000045 03:  [ 2 1 4 ]
%e A000045 04:  [ 3 1 2 1 ]
%e A000045 05:  [ 3 1 3 ]
%e A000045 06:  [ 3 2 2 ]
%e A000045 07:  [ 4 1 2 ]
%e A000045 08:  [ 4 2 1 ]
%e A000045 09:  [ 4 3 ]
%e A000045 10:  [ 5 1 1 ]
%e A000045 11:  [ 5 2 ]
%e A000045 12:  [ 6 1 ]
%e A000045 13:  [ 7 ]
%e A000045 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 A000045 01:  [ 1 2 1 2 ]
%e A000045 02:  [ 1 3 1 1 ]
%e A000045 03:  [ 1 3 2 ]
%e A000045 04:  [ 1 4 1 ]
%e A000045 05:  [ 1 5 ]
%e A000045 06:  [ 2 2 1 1 ]
%e A000045 07:  [ 2 3 1 ]
%e A000045 08:  [ 2 4 ]
%e A000045 09:  [ 3 2 1 ]
%e A000045 10:  [ 3 3 ]
%e A000045 11:  [ 4 2 ]
%e A000045 12:  [ 5 1 ]
%e A000045 13:  [ 6 ]
%e A000045 (End)
%e A000045 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 A000045 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 A000045 := proc(n) combinat[fibonacci](n); end;
%p A000045 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 A000045 spec := [B, {B=Sequence(Set(Z, card>1))}, unlabeled ]: seq(combstruct[count](spec, size=n), n=1..39); # _Zerinvary Lajos_, Apr 04 2008
%p A000045 # The following Maple command isFib(n) yields true or false depending on whether n is a Fibonacci number or not.
%p A000045 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 A000045 Table[Fibonacci[k], {k, 0, 50}] (* _Mohammad K. Azarian_, Jul 11 2015 *)
%t A000045 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 (smbelcas(AT)toroidalsnark.net), Jul 04 2009 *)
%t A000045 LinearRecurrence[{1, 1}, {0, 1}, 40] (* _Harvey P. Dale_, Aug 03 2014 *)
%t A000045 Fibonacci[Range[0, 20]] (* _Eric W. Weisstein_, Sep 22 2017 *)
%t A000045 CoefficientList[Series[-(x/(-1 + x + x^2)), {x, 0, 20}], x] (* _Eric W. Weisstein_, Sep 22 2017 *)
%o A000045 (Axiom) [fibonacci(n) for n in 0..50]
%o A000045 (MAGMA) [Fibonacci(n): n in [0..38]];
%o A000045 (MAGMA) [0,1] cat [n: n in [1..50000000] | IsSquare(5*n^2-4) or IsSquare(5*n^2+4)]; // _Vincenzo Librandi_, Nov 19 2014
%o A000045 (Maxima) makelist(fib(n),n,0,100); /* _Martin Ettl_, Oct 21 2012 */
%o A000045 (PARI) a(n) = fibonacci(n)
%o A000045 (PARI) a(n) = imag(quadgen(5)^n)
%o A000045 (PARI) a(n)=my(phi=quadgen(5));(phi^n-(-1/phi)^n)/(2*phi-1) \\ _Charles R Greathouse IV_, Jun 17 2012
%o A000045 (PARI) a(n)=polcoeff(sum(m=0, n, x^m*prod(k=1, m, k+x +x*O(x^n))/prod(k=1, m, 1+k*x +x*O(x^n))), n) \\ _Paul D. Hanna_, Oct 26 2013
%o A000045 (Python) # _Jaap Spies_, Jan 05 2007 (Change leading dots to blanks.)
%o A000045 def fib():
%o A000045 ... """ Generates the Fibonacci numbers, starting with 0 """
%o A000045 ... x, y = 0, 1
%o A000045 ... while 1:
%o A000045 ....... yield x
%o A000045 ....... x, y = y, x+y
%o A000045 .
%o A000045 f = fib()
%o A000045 a = [f.next() for i in range(100)]
%o A000045 .
%o A000045 def A000045(n):
%o A000045 ... """ Returns Fibonacci number with index n, offset 0,4 """
%o A000045 ... return a[n]
%o A000045 ................
%o A000045 def A000045_list(N):
%o A000045 ... """ Returns a list of the first n Fibonacci numbers """
%o A000045 ... return a[:N]
%o A000045 .
%o A000045 (Python) # As b-file:
%o A000045 from gmpy2 import fib
%o A000045 for n in xrange(100): print str(n)+" "+str(fib(n)) # _Bruno Berselli_, Dec 06 2016
%o A000045 (Sage) ## Demonstration program from Jaap Spies:
%o A000045 a = sloane.A000045; ## choose sequence
%o A000045 print a ## This returns the name of the sequence.
%o A000045 print a(38) ## This returns the 38th number of the sequence.
%o A000045 print a.list(39) ## This returns a list of the first 39 numbers.
%o A000045 (Sage) # Alternatively:
%o A000045 a = BinaryRecurrenceSequence(1,1); print [a(n) for n in (0..19)]
%o A000045 # Closed form integer formula with F(1) = 0 from Paul Hankin (use only for fun).
%o A000045 F = lambda n: (4<<(n-1)*(n+2))//((4<<2*(n-1))-(2<<(n-1))-1)&((2<<(n-1))-1)
%o A000045 print [F(n) for n in (0..19)] # _Peter Luschny_, Aug 28 2016
%o A000045 (Sage) [i for i in fibonacci_sequence(0, 40)] # _Bruno Berselli_, Jun 