|
%I M3538 N1434 #312 Dec 20 2023 10:44:43
%S 0,1,4,17,72,305,1292,5473,23184,98209,416020,1762289,7465176,
%T 31622993,133957148,567451585,2403763488,10182505537,43133785636,
%U 182717648081,774004377960,3278735159921,13888945017644,58834515230497,249227005939632,1055742538989025
%N Denominators of continued fraction convergents to sqrt(5).
%C a(2*n+1) with b(2*n+1) := A001077(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation b^2 - 5*a^2 = -1, a(2*n) with b(2*n) := A001077(2*n), n >= 1, give all (positive integer) solutions to Pell equation b^2 - 5*a^2 = +1 (cf. Emerson reference).
%C Bisection: a(2*n+1) = T(2*n+1, sqrt(5))/sqrt(5) = A007805(n), n >= 0 and a(2*n) = 4*S(n-1,18), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. S(-1,x)=0. See A053120, resp. A049310. S(n,18)=A049660(n+1). - _Wolfdieter Lang_, Jan 10 2003
%C Apart from initial terms, this is the Pisot sequence E(4,17), a(n) = floor(a(n-1)^2/a(n-2) + 1/2).
%C This is also the Horadam sequence (0,1,1,4), having the recurrence relation a(n) = s*a(n-1) + r*a(n-2); for n > 1, where a(0) = 0, a(1) = 1, s = 4, r = 1. a(n) / a(n-1) converges to 5^1/2 + 2 as n approaches infinity. 5^(1/2) + 2 can also be written as (2 * Phi) + 1 and Phi^2 + Phi. - _Ross La Haye_, Aug 18 2003
%C Numerators of continued fraction [4, 4, 4, ...], where the convergents to [4, 4, 4, ...] = (4/1, 17/4, 72/17, ...). Let X = the 2 X 2 matrix [0, 1; 1, 4]; then X^n = [a(n-1), a(n); a(n), a(n+1)]; e.g., X^3 = [4, 17; 17, 72]. Let C = the limit of a(n)/a(n-1) = 2 + sqrt(5) = 4.236067977...; then C^n = a(n+1) + (1/C)*a(n), where (1/C) = 0.236067977... . Example: C^3 = 76.01315556..., = 72 + 17*(0.2360679...). - _Gary W. Adamson_, Dec 15 2007, corrected by _Greg Dresden_, Sep 16 2019, corrected by _Alex Mark_, Jul 21 2020
%C Sqrt(5) = 4/2 + 4/17 + 4/(17*305) + 4/(305*5473) + 4/(5473*98209) + ... . - _Gary W. Adamson_, Dec 15 2007
%C a(p) == 20^((p-1)/2)) mod p, for odd primes p. - _Gary W. Adamson_, Feb 22 2009
%C A001076 == One half of even Fibonacci numbers. - _Vladimir Joseph Stephan Orlovsky_, Oct 25 2009
%C a(n) = A167808(3*n). - _Reinhard Zumkeller_, Nov 12 2009
%C For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 4's along the main diagonal and 1's along the superdiagonal and the subdiagonal. - _John M. Campbell_, Jul 08 2011
%C Moreover, a(n) is the second binomial transform of (0,1,0,5,0,25,...) (see also A033887). This fact can be proved similarly like the proof of _Paul Barry_'s remark in A033887 by using the following scaling identity for delta-Fibonacci numbers: y^n b(n;x/y) = Sum_{k=0..n} binomial(n,k) (y-1)^(n-k) b(k;x) and the fact that b(n;2) = (1-(-1)^n) 5^floor(n/2). - _Roman Witula_, Jul 12 2012
%C Binomial transform of 0, 1, 2, 8, 24, 80, 256, ... (A063727 with offset 1). - _R. J. Mathar_, Feb 05 2014
%C For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,...,4} avoiding runs of zeros of odd lengths. - _Milan Janjic_, Jan 28 2015
%C With offset 1 is the INVERT transform of A006190: (1, 3, 10, 33, 109, 360, ...). - _Gary W. Adamson_, Jul 24 2015
%C a(n) = A000045(3*n)/2 = (A000045(n)*A047946(n))/2, so a(n) is either divisible by A000045(n)/2 or by A047946(n)/2. When n > 3, A000045(n) > 2 and A047946(n) > 2. Therefore a(3) = 17 is the only prime number in this sequence. - _Bobby Jacobs_, Sep 17 2017
%C From _Rogério Serôdio_, Mar 30 2018: (Start)
%C This is a divisibility sequence (i.e., if n|m then a(n)|a(m)).
%C gcd(a(n),a(n+k)) = a(gcd(n, k)) for all positive integers n and k. (End)
%C The initial 0 of this sequence is in contradiction with the fact that 0 is no valid denominator and according to all standard references, the first convergent of a continued fraction is p(0)/q(0) = b(0)/1 where b(0) is the first term of the continued fraction, given by the integer part of the number. One may artificially define q(-1) = 0 to have a recurrent relation q(n) = b(n)*q(n-1) + q(n-2), n >= 1, but then its index should be -1. - _M. F. Hasler_, Nov 01 2019
%C Number of 4-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 17 2020
%C From _Michael A. Allen_, Feb 15 2023: (Start)
%C Also called the 4-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence.
%C a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are 4 kinds of squares available. (End)
%C a(n) is the smallest nonnegative integer that is the sum of n, but no fewer, Fibonacci numbers including negative-index Fibonacci numbers (A039834), with that sum being a(n) = Sum_{i=0..n-1} A000045(3*i+1). a(n) is also the smallest nonnegative integer that is the sum of n, but no fewer, terms each of which is either a Fibonacci number or the negative of a Fibonacci number. (See A027941 for negatives disallowed.) - _Mike Speciner_, Oct 08 2023
%C From _Enrique Navarrete_, Dec 16 2023: (Start)
%C a(n) is the number of compositions of n when there are P(k) sorts of parts k, with k,n > = 1, where P(k) = A006190(k) is the k-th 3-metallonacci number (see example below).
%C In general, the number of compositions with k-metallonacci number of parts is counted by the (k+1)-st metallonacci sequence (note k=1 and k=2 are the Fibonacci and the Pell numbers, respectively). (End).
%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 23.
%D S. Koshkin, Non-classical linear divisibility sequences ..., Fib. Q., 57 (No. 1, 2019), 68-80. See Table 1.
%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 V. Thébault, Les Récréations Mathématiques. Gauthier-Villars, Paris, 1952, p. 282.
%H G. C. Greubel, <a href="/A001076/b001076.txt">Table of n, a(n) for n = 0..1000</a> (terms 0..200 from T. D. Noe)
%H Michael A. Allen and Kenneth Edwards, <a href="https://www.fq.math.ca/Papers1/60-5/allen.pdf">Fence tiling derived identities involving the metallonacci numbers squared or cubed</a>, Fib. Q. 60:5 (2022) 5-17.
%H Paraskevas K. Alvanos and Konstantinos A. Draziotis, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Draziotis/draz2.html">Integer Solutions of the Equation y^2 = Ax^4 + B</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.4.
%H Elwyn Berlekamp and Richard K. Guy, <a href="https://arxiv.org/abs/2002.03705">Fibonacci Plays Billiards (2003)</a>, arXiv:2002.03705 [math.HO], 2020. See p. 5.
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 8.
%H D. W. Boyd, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa34/aa3444.pdf">Some integer sequences related to the Pisot sequences</a>, Acta Arithmetica, 34 (1979), 295-305.
%H D. W. Boyd, <a href="https://www.researchgate.net/profile/David_Boyd7/publication/262181133_Linear_recurrence_relations_for_some_generalized_Pisot_sequences_-_annotated_with_corrections_and_additions/links/00b7d536d49781037f000000.pdf">Linear recurrence relations for some generalized Pisot sequences</a>, Advances in Number Theory ( Kingston ON, 1991) 333-340, Oxford Sci. Publ., Oxford Univ. Press, New York, 1993.
%H Latham Boyle and Paul J. Steinhardt, <a href="https://arxiv.org/abs/1608.08220">Self-Similar One-Dimensional Quasilattices</a>, arXiv preprint arXiv:1608.08220 [math-ph], 2016.
%H E. I. Emerson, <a href="http://www.fq.math.ca/Scanned/7-3/emerson.pdf">Recurrent Sequences in the Equation DQ^2=R^2+N</a>, Fib. Quart., 7 (1969), pp. 231-242, Thm. 1, p. 233.
%H M. C. Firengiz and A. Dil, <a href="http://www.nntdm.net/papers/nntdm-20/NNTDM-20-4-21-32.pdf">Generalized Euler-Seidel method for second order recurrence relations</a>, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
%H Yixing Fu, E. J. König, J. H. Wilson, Yang-Zhi Chou, and J. H. Pixley, <a href="https://arxiv.org/abs/1809.04604">Magic-angle semimetals</a>, arXiv:1809.04604 [cond-mat.str-el], 2018.
%H Juan B. Gil and Aaron Worley, <a href="https://arxiv.org/abs/1901.02619">Generalized metallic means</a>, arXiv:1901.02619 [math.NT], 2019.
%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=398">Encyclopedia of Combinatorial Structures 398</a>
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H C. Pita, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Pita/pita12.html">On s-Fibonomials</a>, J. Int. Seq. 14 (2011) # 11.3.7.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%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 Shaoxiong (Steven) Yuan, <a href="https://arxiv.org/abs/1907.12459">Generalized Identities of Certain Continued Fractions</a>, arXiv:1907.12459 [math.NT], 2019.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,1).
%F a(n) = 4*a(n-1) + a(n-2), n > 1. a(0)=0, a(1)=1.
%F G.f.: x/(1 - 4*x - x^2).
%F a(n) = ((2+sqrt(5))^n - (2-sqrt(5))^n)/(2*sqrt(5)).
%F a(n) = A014445(n)/2 = F(3n)/2.
%F a(n) = ((-i)^(n-1))*S(n-1, 4*i), with i^2 = -1 and S(n, x) := U(n, x/2) Chebyshev's polynomials of the second kind. See A049310. S(-1, x) = 0.
%F a(n) = Sum_{i=0..n} Sum_{j=0..n} Fibonacci(i+j)*n!/(i!j!(n-i-j)!)/2. - _Paul Barry_, Feb 06 2004
%F E.g.f.: exp(2*x)*sinh(sqrt(5)*x)/sqrt(5). - _Vladeta Jovovic_, Sep 01 2004
%F a(n) = F(1) + F(4) + F(7) + ... + F(3n-2), for n > 0.
%F Conjecture: 2a(n+1) = a(n+2) - A001077(n+1). - _Creighton Dement_, Nov 28 2004
%F a(n) = Sum_{k=0..n} Sum_{j=0..n} C(n, j)*C(j, k)*F(j)/2. - _Paul Barry_, Feb 14 2005
%F a(n) = A048876(n) - A048875(n). - _Creighton Dement_, Mar 19 2005
%F Let M = {{0, 1}, {1, 4}}, v[1] = {0, 1}, v[n] = M.v[n - 1]; then a(n) = v[n][[1]]. - _Roger L. Bagula_, May 29 2005
%F a(n) = F(n, 4), the n-th Fibonacci polynomial evaluated at x=4. - _T. D. Noe_, Jan 19 2006
%F [A015448(n), a(n)] = [1,4; 1,3]^n * [1,0]. - _Gary W. Adamson_, Mar 21 2008
%F a(n) = (Sum_{k=0..n} Fibonacci(3*k-2)) + 1. - _Gary Detlefs_, Dec 26 2010
%F a(n) = (3*(-1)^n*F(n) + 5*F(n)^3)/2, n >= 0. See the general D. Jennings formula given in a comment on triangle A111125, where also the reference is given. Here the second (k=1) row [3,1] applies. - _Wolfdieter Lang_, Sep 01 2012
%F Sum_{k>=1} (-1)^(k-1)/(a(k)*a(k+1)) = (Sum_{k>=1} (-1)^(k-1)/(F_k*F_(k+1)))^3 = phi^(-3), where F_n is the n-th Fibonacci numbers (A000045) and phi is golden ratio (A001622). - _Vladimir Shevelev_, Feb 23 2013
%F G.f.: Q(0)*x/(2-4*x), where Q(k) = 1 + 1/(1 - x*(5*k-4)/(x*(5*k+1) - 2/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Oct 11 2013
%F a(-n) = -(-1)^n * a(n). - _Michael Somos_, Feb 23 2014
%F The o.g.f. A(x) = x/(1 - 4*x - x^2) satisfies A(x) + A(-x) + 8*A(x)*A(-x) = 0 or equivalently (1 + 8*A(x))*(1 + 8*A(-x)) = 1. The o.g.f. for A049660 equals -A(sqrt(x))*A(-sqrt(x)). - _Peter Bala_, Apr 02 2015
%F From _Rogério Serôdio_, Mar 30 2018: (Start)
%F Some properties:
%F (1) a(n)*a(n+1) = 4*Sum_{k=1..n} a(k)^2;
%F (2) a(n)^2 + a(n+1)^2 = a(2*n+1);
%F (3) a(n)^2 - a(n-2)^2 = 4*a(n-1)*(a(n) + a(n-2));
%F (4) a(m*(p+1)) = a(m*p)*a(m+1) + a(m*p-1)*a(m);
%F (5) a(n-k)*a(n+k) = a(n)^2 + (-1)^(n+k+1)*a(k)^2;
%F (6) a(n-1)*a(n+1) = a(n)^2 + (-1)^n (particular case of (5)!);
%F (7) a(2*n) = 2*a(n)*(2*a(n) + a(n-1));
%F (8) 3*Sum_{k=2..n+1} a(k)*a(k-1) is equal to a(n+1)^2 if n odd, and is equal to a(n+1)^2 - 1 if n is even;
%F (9) a(n) - a(n-2*k+1) = alpha(k)*a(n-2*k+1) + a(n-4*k+2), where alpha(k) = (2+sqrt(5))^(2*k-1) + (2-sqrt(5))^(2*k-1);
%F (10) 31|Sum_{k=n..n+9} a(k), for all positive n. (End)
%F O.g.f.: x*exp(Sum_{n >= 1} Lucas(3*n)*x^n/n) = x + 4*x^2 + 17*x^3 + .... - _Peter Bala_, Oct 11 2019
%F a(n) = Sum_{k=0..floor(n/2)} 4^(n-2*k-1)*C(n-k-1,n-2*k-1). - _Vladimir Kruchinin_, Oct 02 2022
%F a(n) = i^(n-1)*S(n-1, -4*i), with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. - _Gary Detlefs_ and _Wolfdieter Lang_, Mar 06 2023
%e 1 2 9 38 161 (A001077)
%e -,-,-,--,---, ...
%e 0 1 4 17 72 (A001076)
%e G.f. = x + 4*x^2 + 17*x^3 + 72*x^4 + 305*x^5 + 1292*x^6 + 5473*x^7 + 23184*x^8 + ...
%e From _Enrique Navarrete_, Dec 16 2023: (Start)
%e From the comment on compositions with 3-metallonacci sorts of parts, A006190(k), there are A006190(1)=1 type of 1, A006190(2)=3 types of 2, A006190(3)=10 types of 3, A006190(4)=33 types of 4, A006190(5)=109 types of 5 and A006190(6)=360 types of 6. The following table gives the number of compositions of n=6:
%e Composition, number of such compositions, number of compositions of this type:
%e 6, 1, 360;
%e 5+1, 2, 218;
%e 4+2, 2, 198;
%e 3+3, 1, 100;
%e 4+1+1, 3, 99;
%e 3+2+1, 6, 180;
%e 2+2+2, 1, 27;
%e 3+1+1+1, 4, 40;
%e 2+2+1+1, 6, 54;
%e 2+1+1+1+1, 5, 15;
%e 1+1+1+1+1+1, 1, 1;
%e for a total of a(6)=1292 compositions of n=6. (End)
%p A001076:=-1/(-1+4*z+z**2); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t Join[{0}, Denominator[Convergents[Sqrt[5], 30]]] (* _Harvey P. Dale_, Dec 10 2011 *)
%t a[ n_] := Fibonacci[3*n] / 2; (* _Michael Somos_, Feb 23 2014 *)
%t a[ n_] := ((2 + Sqrt[5])^n - (2 - Sqrt[5])^n) /(2 Sqrt[5]) // Simplify; (* _Michael Somos_, Feb 23 2014 *)
%t LinearRecurrence[{4, 1}, {0, 1}, 26] (* _Jean-François Alcover_, Sep 23 2017 *)
%t a[ n_] := Fibonacci[n, 4]; (* _Michael Somos_, Nov 02 2021 *)
%o (MuPAD) numlib::fibonacci(3*n)/2 $ n = 0..30; // _Zerinvary Lajos_, May 09 2008
%o (Sage) [lucas_number1(n,4,-1) for n in range(23)] # _Zerinvary Lajos_, Apr 23 2009
%o (Sage) [fibonacci(3*n)/2 for n in range(23)] # _Zerinvary Lajos_, May 15 2009
%o (PARI) {a(n) = fibonacci(3*n) / 2}; /* _Michael Somos_, Aug 11 2009 */
%o (PARI) {a(n) = imag( (2 + quadgen(20))^n )}; /* _Michael Somos_, Feb 23 2014 */
%o (PARI) {a(n) = polchebyshev(n-1, 2, 2*I)/I^(n-1)}; /* _Michael Somos_, Nov 02 2021 */
%o (Magma) I:=[0,1]; [n le 2 select I[n] else 4*Self(n-1) + Self(n-2): n in [1..30]]; // _G. C. Greubel_, Jan 24 2018
%o (GAP) a:=[0,1];; for n in [3..30] do a[n]:=4*a[n-1]+a[n-2]; od; a; # _Muniru A Asiru_, Mar 31 2018
%o (Maxima) a(n):=sum(4^(n-1-2*k)*binomial(n-k-1,n-2*k-1),k,0,floor((n)/2));/* _Vladimir Kruchinin_, Oct 02 2022 */
%Y Row n=4 of A073133, A172236 and A352361.
%Y Cf. A000045, A001077, A015448, A175183 (Pisano periods).
%Y Cf. A049660, A007805.
%Y Partial sums of A033887. First differences of A049652. Bisection of A059973.
%Y Third column of array A028412.
%K nonn,easy,cofr,nice
%O 0,3
%A _N. J. A. Sloane_
|
