%I M2741 N1101 #715 Sep 24 2024 18:18:58

%S 0,1,3,8,21,55,144,377,987,2584,6765,17711,46368,121393,317811,832040,

%T 2178309,5702887,14930352,39088169,102334155,267914296,701408733,

%U 1836311903,4807526976,12586269025,32951280099,86267571272,225851433717,591286729879,1548008755920

%N F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).

%C Apart from initial term, same as A088305.

%C Second column of array A102310 and of A028412.

%C Numbers k such that 5*k^2 + 4 is a square. - _Gregory V. Richardson_, Oct 13 2002

%C Apart from initial terms, also Pisot sequences E(3,8), P(3,8), T(3,8). See A008776 for definitions of Pisot sequences.

%C Binomial transform of A000045. - _Paul Barry_, Apr 11 2003

%C Number of walks of length 2n+1 in the path graph P_4 from one end to the other one. Example: a(2)=3 because in the path ABCD we have ABABCD, ABCBCD and ABCDCD. - _Emeric Deutsch_, Apr 02 2004

%C Simplest example of a second-order recurrence with the sixth term a square.

%C Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 3. - _Lekraj Beedassy_, Jun 11 2004

%C a(n) (for n > 0) is the smallest positive integer that cannot be created by summing at most n values chosen among the previous terms (with repeats allowed). - _Andrew Weimholt_, Jul 20 2004

%C All nonnegative integer solutions of Pell equation b(n)^2 - 5*a(n)^2 = +4 together with b(n) = A005248(n), n >= 0. - _Wolfdieter Lang_, Aug 31 2004

%C a(n+1) is a Chebyshev transform of 3^n (A000244), where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)). - _Paul Barry_, Oct 25 2004

%C a(n) is the number of distinct products of matrices A, B, C, in (A+B+C)^n where commutator [A,B] = 0 but C does not commute with A or B. - _Paul D. Hanna_ and _Max Alekseyev_, Feb 01 2006

%C Number of binary words with exactly k-1 strictly increasing runs. Example: a(3)=F(6)=8 because we have 0|0,1|0,1|1,0|01,01|0,1|01,01|1 and 01|01. Column sums of A119900. - _Emeric Deutsch_, Jul 23 2006

%C See Table 1 on page 411 of Lukovits and Janezic paper. - _Parthasarathy Nambi_, Aug 22 2006

%C Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5) a(n) + sqrt(5 a(n)^2 + 4))/2) = n. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007

%C [1,3,8,21,55,144,...] is the Hankel transform of [1,1,4,17,75,339,1558,...](see A026378). - _Philippe Deléham_, Apr 13 2007

%C The Diophantine equation a(n) = m has a solution (for m >= 1) if and only if floor(arcsinh(sqrt(5)*m/2)/log(phi)) <> floor(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130259(m) = A130260(m). - _Hieronymus Fischer_, May 25 2007

%C a(n+1) = AB^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 1=`1`, 3=`10`, 8=`100`, 21=`1000`, ..., in Wythoff code.

%C Equals row sums of triangles A140069, A140736 and A140737. - _Gary W. Adamson_, May 25 2008

%C a(n) is also the number of idempotent order-preserving partial transformations (of an n-element chain) of width n (width(alpha) = max(Im(alpha))). Equivalently, it is the number of idempotent order-preserving full transformations (of an n-element chain). - _Abdullahi Umar_, Sep 08 2008

%C a(n) is the number of ways that a string of 0,1 and 2 of size (n-1) can be arranged with no 12-pairs. - _Udita Katugampola_, Sep 24 2008

%C Starting with offset 1 = row sums of triangle A175011. - _Gary W. Adamson_, Apr 03 2010

%C As a fraction: 1/71 = 0.01408450... or 1/9701 = 0.0001030821.... - _Mark Dols_, May 18 2010

%C Sum of the products of the elements in the compositions of n (example for n=3: the compositions are 1+1+1, 1+2, 2+1, and 3; a(3) = 1*1*1 + 1*2 + 2*1 + 3 = 8). - Dylon Hamilton, Jun 20 2010, _Geoffrey Critzer_, _Joerg Arndt_, Dec 06 2010

%C a(n) relates to regular polygons with even numbers of edges such that Product_{k=1..(n-2)/2} (1 + 4*cos^2 k*Pi/n) = even-indexed Fibonacci numbers with a(n) relating to the 2*n-gons. The constants as products = roots to even-indexed rows of triangle A152063. For example: a(5) = 55 satisfies the product formula relating to the 10-gon. - _Gary W. Adamson_, Aug 15 2010

%C Alternatively, product of roots to x^4 - 12x^3 + 51x^2 - 90x + 55, (10th row of triangle A152063) = (4.618...)*(3.618...)*(2.381...)*(1.381...) = 55. - _Gary W. Adamson_, Aug 15 2010

%C a(n) is the number of generalized compositions of n when there are i different types of i, (i=1,2,...). - _Milan Janjic_, Aug 26 2010

%C Starting with "1" = row sums of triangle A180339, and eigensequence of triangle A137710. - _Gary W. Adamson_, Aug 28 2010

%C a(2) = 3 is the only prime.

%C Number of nonisomorphic graded posets with 0 and uniform hasse graph of rank n > 0, with exactly 2 elements of each rank level above 0. (Uniform used in the sense of Retakh, Serconek, and Wilson. Graded used in Stanley's sense that every maximal chain has the same length n.) - _David Nacin_, Feb 13 2012

%C Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ... - _R. J. Mathar_, Aug 10 2012

%C Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 1. - _Michel Lagneau_, Feb 01 2014

%C For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,2}. - _Milan Janjic_, Jan 25 2015

%C With a(0) = 0, for n > 1, a(n) is the smallest number not already in the sequence such that a(n)^2 - a(n-1)^2 is a Fibonacci number. - _Derek Orr_, Jun 08 2015

%C Let T be the tree generated by these rules: 0 is in T, and if p is in T, then p + 1 is in T and x*p is in T and y*p is in T. The n-th generation of T consists of A001906(n) polynomials, for n >= 0. - _Clark Kimberling_, Nov 24 2015

%C For n > 0, a(n) = exactly the maximum area of a quadrilateral with sides in order of lengths F(n), F(n), L(n), and L(n) with L(n)=A000032(n). - _J. M. Bergot_, Jan 20 2016

%C a(n) = twice the area of a triangle with vertices at (L(n+1), L(n+2)), (F(n+1), F(n+1)), and (L(n+2), L(n+1)), with L(n)=A000032(n). - _J. M. Bergot_, Apr 20 2016

%C Except for the initial 0, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S - S^2; see A291000. - _Clark Kimberling_, Aug 24 2017

%C a(n+1) is the number of spanning trees of the graph T_n, where T_n is a sequence of n triangles, where adjacent triangles share an edge. - _Kevin Long_, May 07 2018

%C a(n) is the number of ways to partition [n] such that each block is a run of consecutive numbers, and each block has a fixed point, e.g., for n=3, 12|3 with 1 and 3 as fixed points is valid, but 13|2 is not valid as 1 and 3 do not form a run. Consequently, a(n) also counts the spanning trees of the graph given by taking a path with n vertices and adding another vertex adjacent to all of them. - _Kevin Long_, May 11 2018

%C From _Wolfdieter Lang_, May 31 2018: (Start)

%C The preceding comment can be paraphrased as follows. a(n) is the row sum of the array A305309 for n >= 1. The array A305309(n, k) gives the sum of the products of the block lengths of the set partition of [n] := {1, 2, ..., n} with A048996(n, k) blocks of consecutive numbers, corresponding to the compositions obtained from the k-th partition of n in Abramowitz-Stegun order. See the comments and examples at A305309.

%C {a(n)} also gives the infinite sequence of nonnegative numbers k for which k * ||k*phi|| < 1/sqrt(5), where the irrational number phi = A001622 (golden section), and ||x|| is the absolute value of the difference between x and the nearest integer. See, e.g., the Havil reference, pp. 171-172. (End)

%C This Chebyshev sequence a(n) = S(n-1, 3) (see a formula below) is related to the bisection of Fibonacci sequences {F(a,b;n)}_{n>=0} with input F(a,b;0) = a and F(a,b;1) = b, by F(a,b;2*k) = (a+b)*S(k-1, 3) - a*S(k-2, 3) and F(a,b;2*k+1) = b*S(k, 3) + (a-b)*S(k-1, 3), for k >= 0, and S(-2, 3) = -1. Proof via the o.g.f.s GFeven(a,b,t) = (a - t*(2*a-b))/(1 - 3*t + t^2) and GFodd(a,b,t) = (b + t*(a-b))/(1 - 3*t + t^2). The special case a = 0, b = 1 gives back F(2*k) = S(k-1, 3) = a(k). - _Wolfdieter Lang_, Jun 07 2019

%C a(n) is the number of tilings of two n X 1 rectangles joined orthogonally at a common end-square (so to have 2n-1 squares in a right-angle V shape) with only 1 X 1 and 2 X 1 tiles. This is a consequence of F(2n) = F(n+1)*F(n) + F(n)*F(n-1). - _Nathaniel Gregg_, Oct 10 2021

%C These are the denominators of the upper convergents to the golden ratio, tau; they are also the numerators of the lower convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - _Clark Kimberling_, Jan 02 2022

%C For n > 1, a(n) is the smallest Fibonacci number of unit equilateral triangle tiles needed to make an isosceles trapezoid of height F(n) triangles. - _Kiran Ananthpur Bacche_, Sep 01 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 A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 2,5,6,14,33,55.

%D R. J. Douglas, Tournaments that admit exactly one Hamiltonian cycle, Proc. London Math. Soc., 21 (1970), 716-730.

%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

%D A. Gerardin, Reply to Query 4389, L'Intermédiaire des Mathématiciens, 22 (1915), 23.

%D Julian Havil, The Irrationals, Princeton University Press, Princeton and Oxford, 2012, pp. 171-172.

%D Howie, J. M. Combinatorial and probabilistic results in transformation semigroups. Words, languages and combinatorics, II (Kyoto, 1992), 200--206, World Sci. Publ., River Edge, NJ, (1994).

%D Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving full transformations. Semigroup Forum 72 (2006), 51-62.

%D I. Lukovits, A. Graovac, E. Kalman, G. Kaptay, P. Nagy, S. Nikolic, J. Sytchev and N. Trinajstich, "Nanotubes: Number of Kekulé Structures and Aromaticity", J. Chem. Inf. Comput. Sci, vol. 43 (2003), pp. 609-614. See Equation 6 on page 611.

%D T. Mansour, M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.

%D H. Mathieu, Query 3932, L'Intermédiaire des Mathématiciens, 18 (1911), 222. - _N. J. A. Sloane_, Mar 08 2022

%D I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 101.

%D Paulo Ribenboim, Primes in Lucas sequences (Chap 4), in 'My Numbers, My Friends', Springer-Verlag 2000 NY, page 27.

%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 R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.

%H Indranil Ghosh, <a href="/A001906/b001906.txt">Table of n, a(n) for n = 0..2388</a> (terms 0..200 from T. D. Noe)

%H Marco Abrate, Stefano Barbero, Umberto Cerruti, and 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 Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, <a href="https://www.emis.de/journals/INTEGERS/papers/p38/p38.Abstract.html">Polynomial sequences on quadratic curves</a>, Integers, Vol. 15, 2015, #A38.

%H K. Andersen, L. Carbone, and D. Penta, <a href="https://pdfs.semanticscholar.org/8f0c/c3e68d388185129a56ed73b5d21224659300.pdf">Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields</a>, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.01124">A Note on Riordan Arrays with Catalan Halves</a>, arXiv:1912.01124 [math.CO], 2019.

%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

%H Raghavendra Bhat, Cristian Cobeli, and Alexandru Zaharescu, <a href="https://arxiv.org/abs/2309.03922">Filtered rays over iterated absolute differences on layers of integers</a>, arXiv:2309.03922 [math.NT], 2023. See page 16.

%H Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, <a href="https://arxiv.org/abs/2203.13205">Honeycombs in the Pascal triangle and beyond</a>, arXiv:2203.13205 [math.HO], 2022. See p. 5.

%H A. Bremner and N. Tzanakis, <a href="http://arxiv.org/abs/math/0405306">Lucas sequences whose 12th or 9th term is a square</a>, arXiv:math/0405306 [math.NT], 2004.

%H David Broadhurst, <a href="http://arxiv.org/abs/1504.05303">Multiple Landen values and the tribonacci numbers</a>, arXiv:1504.05303 [hep-th], 2015.

%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.

%H Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

%H Marc Chamberland and Christopher French, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Chamberland/chamberland12.html">Generalized Catalan Numbers and Generalized Hankel Transformations</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.1.

%H A. Collins et al., <a href="https://www.fq.math.ca/Papers1/51-2/CollinsDedricksonWang.pdf">Binary words, n-color compositions and bisection of the Fibonacci numbers</a>, Fib. Quarterly, 51 (2013), 130-136.

%H Aleksandar Cvetkovic, Predrag Rajkovic and Milos Ivkovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL5/Ivkovic/ivkovic3.html">Catalan Numbers, the Hankel Transform and Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.3

%H Tomislav Doslic, <a href="http://dx.doi.org/10.1007/s10910-013-0167-2">Planar polycyclic graphs and their Tutte polynomials</a>, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607. See Cor. 3.7(e).

%H S. Falcon, <a href="http://dx.doi.org/10.4236/am.2014.515216">Relationships between Some k-Fibonacci Sequences</a>, Applied Mathematics, 2014, 5, 2226-2234.

%H Sergio Falcon, <a href="http://www.mathnet.or.kr/mathnet/thesis_file/CKMS-28-4-827-832.pdf">Catalan transform of the K-Fibonacci sequence</a>, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832. doi:10.4134/CKMS.2013.28.4.827.

%H S. Falcon, <a href="http://dx.doi.org/10.9734/BJMCS/2014/11783">Iterated Binomial Transforms of the k-Fibonacci Sequence</a>, British Journal of Mathematics & Computer Science, 4 (22): 2014.

%H R. Flórez, R. A. Higuita, and A. Mukherjee, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mukherjee/mukh2.html">Alternating Sums in the Hosoya Polynomial Triangle</a>, Article 14.9.5 Journal of Integer Sequences, Vol. 17 (2014).

%H Achille Frigeri, <a href="https://arxiv.org/abs/1705.08305">A note on Fibonacci number of even index</a>, arXiv:1705.08305 [math.NT], 2017.

%H M. R. Garey, <a href="https://doi.org/10.1016/0095-8956(72)90062-7">On enumerating tournaments that admit exactly one Hamiltonian circuit</a>, J. Combin. Theory, B 13 (1972), 266-269.

%H Dale Gerdemann, <a href="https://www.youtube.com/watch?v=QgFK6MoemEA">Fractal images from (3,-1) recursion</a>, YouTube Video, Oct 30 2014.

%H I. M. Gessel and Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013), 13.4.5.

%H A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding <a href="http://www.fq.math.ca/Scanned/9-3/gougenheim-a.pdf">Part 1</a> <a href="http://www.fq.math.ca/Scanned/9-3/gougenheim-b.pdf">Part 2</a>, Fib. Quart., 9 (1971), 277-295, 298.

%H Y-h. Guo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Guo/guo4.html">Some n-Color Compositions</a>, J. Int. Seq. 15 (2012) 12.1.2, eq (2).

%H Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, <a href="https://doi.org/10.1515/math-2017-0047">Binomials Transformation Formulae of Scaled Fibonacci Numbers</a>, Open Math. 15 (2017), 477-485.

%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/5-5/horadam.pdf">Special Properties of the Sequence W(n){a,b; p,q}</a>, Fib. Quart., Vol. 5, No. 5 (1967), pp. 424-434. Case a=0,b=1; p=3, q=-1.

%H J. M. Howie, <a href="http://dx.doi.org/10.1017/S0013091500026936"> Products of idempotents in certain semigroups of transformations</a>, Proc. Edinburgh Math. Soc. 17 (1971), 223-236.

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

%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Janjic/janjic42.html">Determinants and Recurrence Sequences</a>, Journal of Integer Sequences, 2012, Article 12.3.5.

%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 J. Jina and P. Trojovsky, <a href="http://dx.doi.org/10.12732/ijpam.v88i4.11">On determinants of some tridiagonal matrices connected with Fibonacci numbers</a>, International Journal of Pure and Applied Mathematics 88:4 (2013), 569-575.

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H E. Kilic, Y. T. Ulutas, and N. Omur, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Omur/omur6.html">A Formula for the Generating Functions of Powers of Horadam's Sequence with Two Additional Parameters</a>, J. Int. Seq. 14 (2011) #11.5.6, Table 1, k=t=1.

%H Seong Ju Kim, R. Stees, and L. Taalman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Stees/stees4.html">Sequences of Spiral Knot Determinants</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.1.4.

%H G. Kreweras, <a href="/A000108/a000108_1.pdf">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]

%H Markus Kuba and Alois Panholzer, <a href="http://dx.doi.org/10.1016/j.disc.2012.07.011">Enumeration formulas for pattern restricted Stirling permutations</a>, Discrete Math. 312(21) (2012), 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012

%H Wolfdieter Lang, <a href="http://www.fq.math.ca/Scanned/38-5/lang.pdf">On polynomials related to powers of the generating function of Catalan's numbers</a>, Fib. Quart. 38 (2000) 408-419. Eq. (44) lhs, m=5.

%H Ioana-Claudia Lazăr, <a href="https://arxiv.org/abs/1904.06555">Lucas sequences in t-uniform simplicial complexes</a>, arXiv:1904.06555 [math.GR], 2019.

%H I. Lukovits and D. Janezic, <a href="http://dx.doi.org/10.1021/ci034240k">Enumeration of conjugated circuits in nanotubes</a>, J. Chem. Inf. Comput. Sci., vol. 44 (2004) pp. 410-414.

%H G. Narang and A. K. Agarwal, <a href="https://doi.org/10.1016/j.disc.2007.04.022">Lattice paths and n-color compositions</a>, Discr. Math., 308 (2008), 1732-1740.

%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.

%H Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee, and Jung Hoon Han, <a href="https://arxiv.org/abs/1709.01344">Proposal of a spin-one chain model with competing dimer and trimer interactions</a>, arXiv:1709.01344 [cond-mat.str-el], 2017.

%H J. Pan, <a href="https://cs.uwaterloo.ca/journals/JIS/OL13/Pan/pan8.html">Multiple Binomial Transforms and Families of Integer Sequences</a>, J. Int. Seq. 13 (2010), 10.4.2. Absolute values of F^(-2).

%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 V. Retakh, S. Serconek, and R. Wilson, <a href="http://arxiv.org/abs/1010.6295">Hilbert Series of Algebras Associated to Directed Graphs and Order Homology</a>, arXiv:1010.6295 [math.RA], 2010-2011.

%H John Riordan, <a href="/A001519/a001519.pdf">Letter to N. J. A. Sloane, Nov. 1970</a>

%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.

%H J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373, <a href="http://arxiv.org/abs/0711.1738">arXiv:0711.1738</a>. Mentions this sequence.

%H Luigi Santocanale, <a href="https://arxiv.org/abs/1906.05590">On discrete idempotent paths</a>, arXiv:1906.05590 [math.LO], 2019.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H Michael Somos, <a href="https://grail.eecs.csuohio.edu/~somos/step2.txt">In the Elliptic Realm</a>.

%H Ryan Stees, <a href="https://commons.lib.jmu.edu/honors201019/84">Sequences of Spiral Knot Determinants</a>, Senior Honors Projects, Paper 84, James Madison Univ., May 2016.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

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

%H Roman Witula, <a href="https://doi.org/10.1515/dema-2013-0436">Binomials transformation formulae of scaled Lucas numbers</a>, Demonstratio Math. 46 (2013), 15-27.

%H R. Witula and Damian Slota, <a href="http://dx.doi.org/10.2298/AADM0902310W">delta-Fibonacci numbers</a>, Appl. Anal. Discr. Math 3 (2009) 310-329, <a href="http://www.ams.org/mathscinet-getitem?mr=2555042">MR2555042</a>

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

%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 (3,-1).

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

%F G.f.: x / (1 - 3*x + x^2). - _Simon Plouffe_ in his 1992 dissertation

%F a(n) = 3*a(n-1) - a(n-2) = A000045(2*n).

%F a(n) = -a(-n).

%F a(n) = A060921(n-1, 0), n >= 1.

%F a(n) = sqrt((A005248(n)^2 - 4)/5).

%F a(n) = A007598(n) - A007598(n-2), n > 1.

%F a(n) = (ap^n - am^n)/(ap-am), with ap := (3+sqrt(5))/2, am := (3-sqrt(5))/2.

%F Invert transform of natural numbers: a(n) = Sum_{k=1..n} k*a(n-k), a(0) = 1. - _Vladeta Jovovic_, Apr 27 2001

%F a(n) = S(n-1, 3) with S(n, x) = U(n, x/2) Chebyshev's polynomials of the 2nd kind, see A049310.

%F a(n) = Sum_{k=0..n} binomial(n, k)*F(k). - _Benoit Cloitre_, Sep 03 2002

%F Limit_{n->infinity} a(n)/a(n-1) = 1 + phi = (3 + sqrt(5))/2. This sequence includes all of the elements of A033888 combined with A033890.

%F a(0)=0, a(1)=1, a(2)=3, a(n)*a(n-2) + 1 = a(n-1)^2. - _Benoit Cloitre_, Dec 06 2002

%F a(n) = n + Sum_{k=0..n-1} Sum_{i=0..k} a(i) = n + A054452(n). - _Benoit Cloitre_, Jan 26 2003

%F a(n) = Sum_{k=1..n} binomial(n+k-1, n-k). - _Vladeta Jovovic_, Mar 23 2003

%F E.g.f.: (2/sqrt(5))*exp(3*x/2)*sinh(sqrt(5)*x/2). - _Paul Barry_, Apr 11 2003

%F Second diagonal of array defined by T(i, 1) = T(1, j) = 1, T(i, j) = Max(T(i-1, j) + T(i-1, j-1); T(i-1, j-1) + T(i, j-1)). - _Benoit Cloitre_, Aug 05 2003

%F a(n) = F(n)*L(n) = A000045(n)*A000032(n). - _Lekraj Beedassy_, Nov 17 2003

%F F(2n+2) = 1, 3, 8, ... is the binomial transform of F(n+2). - _Paul Barry_, Apr 24 2004

%F Partial sums of A001519(n). - _Lekraj Beedassy_, Jun 11 2004

%F a(n) = Sum_{i=0..n-1} binomial(2*n-1-i, i)*5^(n-i-1)*(-1)^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004

%F a(n) = Sum_{k=0..n} binomial(n+k, n-k-1) = Sum_{k=0..n} binomial(n+k, 2k+1).

%F a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*3^(n-2*k). - _Paul Barry_, Oct 25 2004

%F a(n) = (n*L(n) - F(n))/5 = Sum_{k=0..n-1} (-1)^n*L(2*n-2*k-1).

%F The i-th term of the sequence is the entry (1, 2) in the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - _Simone Severini_, Oct 15 2005

%F Computation suggests that this sequence is the Hankel transform of A005807. The Hankel transform of {a(n)} is Det[{{a(1), ..., a(n)}, {a(2), ..., a(n+1)}, ..., {a(n), ..., a(2n-1)}}]. - _John W. Layman_, Jul 21 2000

%F a(n+1) = (A005248(n+1) - A001519(n))/2. - _Creighton Dement_, Aug 15 2004

%F a(n+1) = Sum_{i=0..n} Sum_{j=0..n} binomial(n-i, j)*binomial(n-j, i). - _N. J. A. Sloane_, Feb 20 2005

%F a(n) = (2/sqrt(5))*sinh(2*n*psi), where psi:=log(phi) and phi=(1+sqrt(5))/2. - _Hieronymus Fischer_, Apr 24 2007

%F a(n) = ((phi+1)^n - A001519(n))/phi with phi=(1+sqrt(5))/2. - _Reinhard Zumkeller_, Nov 22 2007

%F Row sums of triangle A135871. - _Gary W. Adamson_, Dec 02 2007

%F a(n)^2 = Sum_{k=1..n} a(2*k-1). This is a property of any sequence S(n) such that S(n) = B*S(n-1) - S(n-2) with S(0) = 0 and S(1) = 1 including {0,1,2,3,...} where B = 2. - _Kenneth J Ramsey_, Mar 23 2008

%F a(n) = 1/sqrt(5)*(phi^(2*n+2) - phi^(-2*n-2)), where phi = (1+sqrt(5))/2, the golden ratio. - _Udita Katugampola_ (SIU), Sep 24 2008

%F If p[i] = i 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 If p[i] = Stirling2(i,2) and if A is the 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-1) = det(A). - _Milan Janjic_, May 08 2010

%F a(n) = F(2*n+10) mod F(2*n+5).

%F a(n) = 1 + a(n-1) + Sum_{i=1..n-1} a(i), with a(0)=0. - _Gary W. Adamson_, Feb 19 2011

%F a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 3's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - _John M. Campbell_, Jun 09 2011

%F a(n), n > 1 is equal to the determinant of an (n-x) X (n-1) tridiagonal matrix with 3's in the main diagonal, 1's in the super and subdiagonals, and the rest 0's. - _Gary W. Adamson_, Jun 27 2011

%F a(n) = b such that Integral_{x=0..Pi/2} sin(n*x)/(3/2-cos(x)) dx = c + b*log(3). - _Francesco Daddi_, Aug 01 2011

%F a(n+1) = Sum_{k=0..n} A101950(n,k)*2^k. - _Philippe Deléham_, Feb 10 2012

%F G.f.: A(x) = x/(1-3*x+x^2) = G(0)/sqrt(5); where G(k)= 1 -(a^k)/(1 - b*x/(b*x - 2*(a^k)/G(k+1))), a = (7-3*sqrt(5))/2, b = 3+sqrt(5), if |x|<(3-sqrt(5))/2 = 0.3819660...; (continued fraction 3 kind, 3-step ). - _Sergei N. Gladkovskii_, Jun 25 2012

%F a(n) = 2^n*b(n;1/2) = -b(n;-1), where b(n;d), n=0,1,...,d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also Witula's et al. papers). - _Roman Witula_, Jul 12 2012

%F Product_{n>=1} (1 + 1/a(n)) = 1 + sqrt(5). - _Peter Bala_, Dec 23 2012

%F Product_{n>=2} (1 - 1/a(n)) = (1/6)*(1 + sqrt(5)). - _Peter Bala_, Dec 23 2012

%F G.f.: x/(1-2*x) + x^2/(1-2*x)/(Q(0)-x) where Q(k) = 1 - x/(x*k+1)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Feb 23 2013

%F G.f.: G(0)/2 - 1, where G(k) = 1 + 1/( 1 - x/(x + (1-x)^2/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jul 16 2013

%F G.f.: x*G(0)/(2-3*x), where G(k) = 1 + 1/( 1 - x*(5*k-9)/(x*(5*k-4) - 6/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jul 17 2013

%F Sum_{n>=1} 1/(a(n) + 1/a(n)) = 1. Compare with A001519, A049660 and A049670. - _Peter Bala_, Nov 29 2013

%F a(n) = U(n-1,3/2) where U(n-1,x) is Chebyshev polynomial of the second kind. - _Milan Janjic_, Jan 25 2015

%F The o.g.f. A(x) satisfies A(x) + A(-x) + 6*A(x)*A(-x) = 0. The o.g.f. for A004187 equals -A(sqrt(x))*A(-sqrt(x)). - _Peter Bala_, Apr 02 2015

%F For n > 1, a(n) = (3*F(n+1)^2 + 2*F(n-2)*F(n+1) - F(n-2)^2)/4. - _J. M. Bergot_, Feb 16 2016

%F For n > 3, a(n) = floor(MA) - 4 for n even and floor(MA) + 5 for n odd. MA is the maximum area of a quadrilateral with lengths of sides in order L(n), L(n), F(n-3), F(n+3), with L(n)=A000032(n). The ratio of the longer diagonal to the shorter approaches 5/3. - _J. M. Bergot_, Feb 16 2016

%F a(n+1) = Sum_{j=0..n} Sum_{k=0..j} binomial(n-j,k)*binomial(j,k)*2^(j-k). - _Tony Foster III_, Sep 18 2017

%F a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i,k-i). - _Wesley Ivan Hurt_, Sep 21 2017

%F a(n) = Sum_{k=1..A000041(n)} A305309(n, k), n >= 1. Also row sums of triangle A078812.- _Wolfdieter Lang_, May 31 2018

%F a(n) = H(2*n, 1, 1/2) for n > 0 where H(n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4). - _Peter Luschny_, Sep 03 2019

%F Sum_{n>=1} 1/a(n) = A153386. - _Amiram Eldar_, Oct 04 2020

%F a(n) = A249450(n) + 2. - _Leo Tavares_, Oct 10 2021

%F a(n) = -2/(sqrt(5)*tan(2*arctan(phi^(2*n)))), where phi = A001622 is the golden ratio. - _Diego Rattaggi_, Nov 21 2021

%F a(n) = sinh(2*n*arcsinh(1/2))/sqrt(5/4). - _Peter Luschny_, May 21 2022

%e G.f. = x + 3*x^2 + 8*x^3 + 21*x^4 + 55*x^5 + 144*x^6 + 377*x^7 + 987*x^8 + ...

%e a(3) = 8 because there are exactly 8 idempotent order-preserving full transformations on a 3-element chain, namely: (1,2,3)->(1,1,1),(1,2,3)->(2,2,2),(1,2,3)->(3,3,3),(1,2,3)->(1,1,3),(1,2,3)->(2,2,3),(1,2,3)->(1,2,2),(1,2,3)->(1,3,3),(1,2,3)->(1,2,3)-mappings are coordinate-wise. - _Abdullahi Umar_, Sep 08 2008

%p with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S, card > 0), S=Sequence(U, card > 1), U=Sequence(Z, card >0)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+1), n=0..28); # _Zerinvary Lajos_, Apr 04 2009

%p H := (n, a, b) -> hypergeom([a - n/2, b - n/2], [1 - n], -4):

%p a := n -> `if`(n = 0, 0, H(2*n, 1, 1/2)):

%p seq(simplify(a(n)), n=0..30); # _Peter Luschny_, Sep 03 2019

%p A001906 := proc(n)

%p combinat[fibonacci](2*n) ;

%p end proc:

%p seq(A001906(n),n=0..20) ; # _R. J. Mathar_, Jan 11 2024

%t f[n_] := Fibonacci[2n]; Array[f, 28, 0] (* or *)

%t LinearRecurrence[{3, -1}, {0, 1}, 28] (* _Robert G. Wilson v_, Jul 13 2011 *)

%t Take[Fibonacci[Range[0,60]],{1,-1,2}] (* _Harvey P. Dale_, May 23 2012 *)

%t Table[ ChebyshevU[n-1, 3/2], {n, 0, 30}] (* _Jean-François Alcover_, Jan 25 2013, after _Michael Somos_ *)

%t CoefficientList[Series[(x)/(1 - 3x + x^2), {x, 0, 30}], x] (* _Vincenzo Librandi_, Sep 10 2014 *)

%o (PARI) {a(n) = fibonacci(2*n)}; /* _Michael Somos_, Dec 06 2002 */

%o (PARI) {a(n) = subst( poltchebi(n+1)*4 - poltchebi(n)*6, x, 3/2)/5}; /* _Michael Somos_, Dec 06 2002 */

%o (PARI) {a(n) = polchebyshev( n-1, 2, 3/2)}; /* _Michael Somos_ Jun 18 2011 */

%o (PARI) Vec(x/(1-3*x+x^2)+O(x^99)) \\ _Charles R Greathouse IV_, Oct 24 2012

%o (Sage) [lucas_number1(n,3,1) for n in range(27)] # _Zerinvary Lajos_, Jun 25 2008

%o (Sage) [fibonacci(2*n) for n in range(0, 28)] # _Zerinvary Lajos_, May 15 2009

%o (MuPAD) numlib::fibonacci(2*n) $ n = 0..35; // _Zerinvary Lajos_, May 09 2008

%o (Haskell)

%o a001906 n = a001906_list !! n

%o a001906_list =

%o 0 : 1 : zipWith (-) (map (* 3) $ tail a001906_list) a001906_list

%o -- _Reinhard Zumkeller_, Oct 03 2011

%o (Python)

%o def a(n, adict={0:0, 1:1}):

%o if n in adict:

%o return adict[n]

%o adict[n]=3*a(n-1) - a(n-2)

%o return adict[n] # _David Nacin_, Mar 04 2012

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

%o (Magma) [Fibonacci(2*n): n in [0..30]]; // _Vincenzo Librandi_, Sep 10 2014

%Y Fibonacci A000045 = union of this sequence and A001519.

%Y Cf. A000041, A000032, A001622, A048996, A052529, A055991, A078812, A305309, A058038 (pairwise products), A153386.

%Y Inverse sequences A130259 and A130260.

%Y Cf. A249450.

%Y Cf. A033888, A033890.

%K nonn,easy,nice,core

%O 0,3

%A _N. J. A. Sloane_