login
This site is supported by donations to The OEIS Foundation.

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001519 a(n) = 3*a(n-1) - a(n-2), with a(0) = a(1) = 1.
(Formerly M1439 N0569)
230
1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025, 196418, 514229, 1346269, 3524578, 9227465, 24157817, 63245986, 165580141, 433494437, 1134903170, 2971215073, 7778742049, 20365011074, 53316291173, 139583862445, 365435296162, 956722026041 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

This is a bisection of the Fibonacci sequence A000045. a(n) = F(2*n-1), with F(n) = A000045(n).

Number of ordered trees with n+1 edges and height at most 3 (height=number of edges on a maximal path starting at the root). Number of directed column-convex polyominoes of area n+1. Number of nondecreasing Dyck paths of length 2n+2. - Emeric Deutsch, Jul 11 2001

Terms for n>1 are the solutions to : 5x^2-4 is a square. - Benoit Cloitre, Apr 07 2002

a(1) = 1, a(n+1) = smallest Fibonacci number greater than the n-th partial sum. - Amarnath Murthy, Oct 21 2002

The fractional part of tau*a(n) decreases monotonically to zero. - Benoit Cloitre, Feb 01 2003

n such that floor(phi^2*n^2)-floor(phi*n)^2 = 1 where phi=(1+sqrt(5))/2 - Benoit Cloitre, Mar 16 2003

Number of leftist horizontally convex polyominoes with area n+1.

Number of 31-avoiding words of length n on alphabet {1,2,3} which do not end in 3. (E.g., at n=3, we have 111,112,121,122,132,211,212,221,222,232,321,322 and 332.) See A028859. - Jon Perry, Aug 04 2003

Appears to give all solutions >1 to the equation : x^2=ceiling(x*r*floor(x/r)) where r=phi=(1+sqrt(5))/2. - Benoit Cloitre, Feb 24 2004

a(1) = 1, a(2) = 2, then the least number such that the square of any term is just less than the geometric mean of its neighbors. a(n+1)*a(n-1)> a(n)^2. - Amarnath Murthy, Apr 06 2004

All positive integer solutions of Pell equation b(n)^2 - 5*a(n)^2 = -4 together with b(n)=A002878(n), n>=0. - Wolfdieter Lang, Aug 31 2004

a(n) = L(n,3), where L is defined as in A108299; see also A002878 for L(n,-3). - Reinhard Zumkeller, Jun 01 2005

Essentially same as Pisot sequence E(2,5).

Number of permutations of [n+1] avoiding 321 and 3412. E.g. a(3) = 13 because the permutations of [4] avoiding 321 and 3412 are: 1234, 2134, 1324, 1243, 3124, 2314, 2143, 1423, 1342, 4123, 3142, 2413, 2341. - Bridget Tenner, Aug 15 2005

Number of 1324-avoiding circular permutations on [n+1].

A subset of the Markoff numbers (A002559). - Robert G. Wilson v, Oct 05 2005

(x,y)=(a(n),a(n+1)) are the solutions of x/(yz)+y/(xz)+z/(xy)=3 with z=1. - Floor van Lamoen (fvlamoen(AT)hotmail.com), Nov 29 2001

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) = 1. - Herbert Kociemba, Jun 10 2004

With interpolated zeros, counts closed walks of length n at the start or end node of P_4. a(n) counts closed walks of length 2n at the start or end node of P_4. The sequence 0,1,0,2,0,5,.. counts walks of length n between the start and second node of P_4. - Paul Barry, Jan 26 2005

a(n) = number of ordered trees on n edges containing exactly one non-leaf vertex all of whose children are leaves (every ordered tree must contain at least one such vertex). For example, a(0) = 1 because the root of the tree with no edges is not considered to be a leaf and the condition "all children are leaves" is vacuously satisfied by the root and a(4) = 13 counts all 14 ordered trees on 4 edges (A000108) except (ignore dots)

  |..|

  .\/.

  which has two such vertices. - David Callan, Mar 02 2005

Number of directed column-convex polyominoes of area n. Example: a(2)=2 because we have the 1 X 2 and the 2 X 1 rectangles. - Emeric Deutsch, Jul 31 2006

Same as the number of Kekule structures in polyphenanthrene in terms of the number of hexagons in extended (1,1)-nanotubes. See Table 1 on page 411 of I. Lukovits and D. Janezic. - Parthasarathy Nambi, Aug 22 2006

Number of free generators of degree n of symmetric polynomials in 3-noncommuting variables. - Mike Zabrocki, Oct 24 2006

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

Consider a teacher who teaches one student, then he finds he can teach two students while the original student learns to teach a student. And so on with every generation an individual can teach one more student then he could before. a(n) starting at a(2) gives the total number of new students/teachers (see program). - Ben Paul Thurston, Apr 11 2007

The Diophantine equation a(n)=m has a solution (for m>=1) iff ceiling(arcsinh(sqrt(5)*m/2)/log(phi))) != ceiling(arccosh(sqrt(5)*m/2)/log(phi))) where phi is the golden ratio. An equivalent condition is A130255(m)=A130256(m). - Hieronymus Fischer, May 24 2007

a(n+1)= B^(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., 2=`0`, 5=`00`, 13=`000`,..., in Wythoff code.

Bisection of the Fibonacci sequence into odd indexed non-zero terms (1, 2, 5, 13,...) and even indexed terms (1, 3, 8, 21,...) may be represented as row sums of companion triangles A140068 and A140069. - Gary W. Adamson, May 04 2008

a(n) = number of partitions pi of [n] (in standard increasing form) such that Flatten[pi] is a (2-1-3)-avoiding permutation. Example: a(4)=13 counts all 15 partitions of [4] except 13/24 and 13/2/4. Here "standard increasing form" means the entries are increasing in each block and the blocks are arranged in increasing order of their first entries. Also number that avoid 3-1-2. - David Callan, Jul 22 2008

Let P = the partial sum operator, A000012: (1; 1,1; 1,1,1;...) and A153463 = M, the partial sum & shift operator. It appears that beginning with any randomly taken sequence S(n), iterates of the operations M * S(n), -> M * ANS, -> P * ANS,...etc, (or starting with P) will rapidly converge upon a two-sequence limit cycle of (1, 2, 5, 13, 34,...) and (1, 1, 3, 8, 21,...). - Gary W. Adamson, Dec 27 2008

4*a(n) = A153266(n) + A153267(n), apart from initial terms. - Creighton Dement, Jan 02 2009

Sum_{n>=0} atan(1/a(n)) = (3/4)Pi. - Jaume Oliver Lafont, Feb 27 2009

Summation of the squares of fibonacci numbers taken 2 at a time. Offset 1. a(3)=5. - Al Hakanson (hawkuu(AT)gmail.com), May 27 2009

Number of musical compositions of Rhythm-music over a time period of n-1 units. Example: a(4)=13; indeed, denoting by R a rest over a time period of 1 unit and by N[j] a note over a period of j units, we have (writing N for N[1]): NNN, NNR, NRN, RNN, NRR, RNR, RRN, RRR, N[2]R, RN[2], NN[2], N[2]N, N[3]) (see the J. Groh reference, pp. 43-48). - Juergen K. Groh (juergen.groh(AT)lhsystems.com), Jan 17 2010

Given an infinite lower triangular matrix M with (1, 2, 3,...) in every column but the leftmost column shifted upwards one row. Then (1, 2, 5,...)= Lim_{n->inf} M^n. (Cf. A144257). - Gary W. Adamson, Feb 18 2010

As a fraction: 8/71 = 0.112676 or 98/9701 = 0.010102051334... (Fraction 9/71 or 99/9701 for sequence without initial term). 19/71 or 199/9701 for sequence in reverse. - M. Dols (markdols99(AT)yahoo.com), May 18 2010

For n>=1, a(n) is the number of compositions (ordered integer partitions) of 2n-1 into an odd number of odd parts. O.g.f.:(x-x^3)/(1-3x^2+x^4)= A(A(x))where A(x)= 1/(1-x)-1/(1-x^2).

For n>0, determinant of the n x n tridiagonal matrix with 1's in the super and subdiagonals, (1,3,3,3,...) in the main diagonal, and the rest zeros. - Gary W. Adamson, Jun 27 2011

The Hosoya index H(n) of the n-path graph P_n is given by H(2n-1) = 0 and H(2n) = a(n+1). - Eric W. Weisstein, Jul 11 2011

The Gi3 sums, see A180662, of the triangles A108299 and A065941 equal the terms of this sequence without a(0). - Johannes W. Meijer, Aug 14 2011

The number of permutations for which length equals reflection length. - Bridget Tenner, Feb 22 2012

Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n+1, with exactly 2 elements of each rank between 0 and 1. (Uniform used in the sense of Retakh, Serconek and Wilson. Graded used in R. Stanley's sense that all maximal chains have the same length.)

HANKEL transform of sequence and the sequence omitting a(0) is the sequence A019590(n). This is the unique sequence with that property. - Michael Somos, May 03 2012

a(n) = 2^n a(n;1/2), where a(n;d). n=0,1,..., d, denote the so-called delta-Fibonacci number (see Witula et al. papers and comments in A000045). - Roman Witula, Jul 12 2012

The number of Dyck paths of length 2n and height at most 3. - Ira M. Gessel, Aug 06 2012

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

Primes in the sequence are 2, 5, 13, 89, 233, 1597, 28657,... (apparently A005478 without the 3). - R. J. Mathar, May 09 2013

a(n+1)= sum of rising diagonal of the Pascal triangle written as a square - cf. comments in A085812. E.g., 13 = 1+5+6+1. - John Molokach, Sep 26 2013

a(n) is the top left entry of the n-th power of any of the 3X3 matrices [1, 1, 1; 1, 1, 1; 0, 1, 1] or  [1, 1, 1; 0, 1, 1; 1, 1, 1] or [1, 1, 0; 1, 1, 1; 1, 1, 1] or [1, 0, 1; 1, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker, Feb 04 2014

Except for the initial term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 64 = 0. - Colin Barker, Feb 16 2014

Positive values of x such that there is a y satisfying x^2 - xy - y^2 - 1 = 0. - Ralf Stephan, Jun 30 2014

1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - Michael Somos, Jul 08 2014

a(n) is also the number of permutations simultaneously avoiding 231, 312 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. Manda Riehl Aug 07 2014

REFERENCES

W. K. Alt, Enumeration of Domino Tilings on the Projective Grid Graph, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013; http://www.wyattalt.com/static/thesis.pdf.

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.

E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin, 1993, pp. 282-298.

J.-L. Baril, A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, 2014; http://jl.baril.u-bourgogne.fr/Dyck.pdf.

A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014, http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf

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

S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.

D. Chmiela, K. Kaczmarek, R. Witula, Binomials Transformation Formulae of Scaled Fibonacci Numbers (submitted 2012).

Dairyko, Michael; Tyner, Samantha; Pudwell, Lara; Wynn, Casey. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From N. J. A. Sloane, Feb 01 2013

N. G. de Bruijn, D. E. Knuth and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.

E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding, Fib. Quart., 9 (1971), 277-295, 298.

Jurgen Groh, Computerimprovisation mit Markoffketten und "kognitiven Algorithmen", Studienarbeit, Technische Hochschule Darmstadt, 1987. [From Juergen K. Groh (juergen.groh(AT)lhsystems.com), Jan 17 2010]

I. Lukovits and D. Janezic, "Enumeration of conjugated circuits in nanotubes", J. Chem. Inf. Comput. Sci., vol. 44 (2004) pp. 410-414.

D. Necas, I. Ohlidal, Consolidated series for efficient calculation of the reflection and transmission in rough multilayers, Optics Express, Vol. 22, 2014, No. 4; DOI:10.1364/OE.22.004499. See Table 1.

J. G. Penaud and O. Roques, Generation de chemins de Dyck a pics croissants, Discrete Mathematics, Vol. 246, no. 1-3 (2002), 255-267.

L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf, 2014

S. Rinaldi and D. G. Rogers, Indecomposability: polyominoes and polyomino tilings, Math. Gaz., to appear, 2008.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 39.

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

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

R. Stanley, Enumerative combinatorics. Vol. 1.Cambridge University Press, Cambridge, 1997, p. 96-100.

M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.

F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

LINKS

T. D. Noe, Table of n, a(n) for n=0..200

E. Barcucci, A. Del Lungo, R. Pinzani and R. Sprugnoli, La hauteur des polyominos...

N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and coinvariants of the symmetric group in noncommuting variables, Canadian Journal of Mathematics 60:2 (2008), pp. 266-296.

D. Callan, Pattern avoidance in circular permutations.

David Callan, Pattern avoidance in "flattened" partitions .

Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

Aleksandar Cvetkovic, Predrag Rajkovic and Milos Ivkovic, Catalan Numbers, the Hankel Transform and Fibonacci Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.3

Enrica Duchi, Andrea Frosini, Renzo Pinzani and Simone Rinaldi, A Note on Rational Succession Rules, J. Integer Seqs., Vol. 6, 2003.

J.-P. Ehrmann et al., POLYA003: Integers of the form a/(bc) + b/(ca) + c/(ab).

S. B. Ekhad and D. Zeilberger, How To Generate As Many Somos-Like Miracles as You Wish, arXiv preprint arXiv:1303.5306, 2013.

Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.

M. Hyatt and J. Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052, 2012. - From N. J. A. Sloane, Dec 24 2012

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 127

M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - From N. J. A. Sloane, Sep 16 2012

I. Jensen, Series exapansions for self-avoiding polygons

Tanya Khovanova, Recursive Sequences

S. Kitaev, J. Remmel and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243, 2012. - From N. J. A. Sloane, May 09 2012

R. Knott, Pi and the Fibonacci numbers

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738, 2012.

D. Nacin, The Minimal Non-Koszul A(Gamma), arXiv preprint arXiv:1204.1534, 2012. - From N. J. A. Sloane, Oct 05 2012

T. K. Petersen and Bridget Eileen Tenner, The depth of a permutation, arXiv:1202.4765.

T. Kyle Petersen and Bridget Eileen Tenner, How to write a permutation as a product of involutions (and why you might care), arXiv:1202.5319, 2012

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

L. Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012. - From N. J. A. Sloane, Jan 03 2013

M. Renault, Dissertation

V. Retakh, S. Serconek, and R. Wilson,  Hilbert Series of Algebras Associated to Directed Graphs and Order Homology

Eric Weisstein's World of Mathematics, Fibonacci Hyperbolic Functions

Eric Weisstein, MathWorld: Hosoya Index

R. Witula, Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009) 310-329, MR2555042

D. Zeilberger, [math/9801016] Automated counting of LEGO towers

Index entries for sequences related to Chebyshev polynomials.

Index entries for sequences related to linear recurrences with constant coefficients, signature (3,-1)

FORMULA

G.f.: (1-2*x)/(1-3*x+x^2).

G.f.: 1 / (1 - x / (1 - x / (1 - x))). - Michael Somos, May 03 2012

a(n) = 3*a(n-1) - a(n-2) = A001906(n+1)-2*A001906(n).

a(n) = a(1-n).

a(n+2) = (a(n+1)^2+1)/a(n) with a(1)=1, a(2)=2. - Benoit Cloitre, Aug 29 2002

a(n) = (phi^(2n-1)+phi^(1-2n))/sqrt(5) where phi=(1+sqrt(5))/2. - Michael Somos, Oct 28 2002

a(n) = A007598(n-1)+A007598(n) = A000045(n-1)^2+A000045(n)^2 = F(n)^2+F(n+1)^2. - Henry Bottomley, Feb 09 2001

a(n)=sum(binomial(n+k, 2k), k=0..n). - Len Smiley (smiley(AT)math.uaa.alaska.edu), Dec 09 2001

a(n) ~ (1/5)*sqrt(5)*phi^(2*n+1). - Joe Keane (jgk(AT)jgk.org), May 15 2002

a(n) = Sum(k=0, n, C(n, k)*F(k+1)). - Benoit Cloitre, Sep 03 2002

Let q(n, x)=sum(i=0, n, x^(n-i)*binomial(2*n-i, i)); then q(n, 1)=a(n) (this comment is essentially the same as that of L. Smiley). - Benoit Cloitre, Nov 10 2002

a(n) = (1/2)*(3*a(n-1)+sqrt(5*a(n-1)^2-4)). - Benoit Cloitre, Apr 12 2003

Main 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

Hankel transform of A002212. E.g., Det([1, 1, 3;1, 3, 10;3, 10, 36])= 5. - Philippe Deléham, Jan 25 2004

Solutions x > 0 to equation floor(x*r*floor(x/r)) = floor(x/r*floor(x*r)) when r=phi. - Benoit Cloitre, Feb 15 2004

a(n)=sum(i=0, n, binomial(n+i, n-i)). - Jon Perry, Mar 08 2004

a(n)= S(n-1, 3) - S(n-2, 3) = T(2*n-1, sqrt(5)/2)/(sqrt(5)/2) with S(n, x) = U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first kind. See triangle A049310, resp. A053120. - Wolfdieter Lang, Aug 31 2004

a(n)= ((-1)^(n-1))*S(2*(n-1), I), with the imaginary unit I and S(n, x)=U(n, x/2) Chebyshev's polynomials of the second kind, A049310. - Wolfdieter Lang, Aug 31 2004

a(n)=sum_{0<=i_1<=i_2<=n}binomial(i_2, i_1)*binomial(n, i_1+i_2). - Benoit Cloitre, Oct 14 2004

a( n ) = a( n - 1 ) + SUM[ i = 0 to n - 1 ] a( i ) a( n ) = Fib( 2n + 1 ) SUM[ i = 0 to n - 1 ] a(i) = Fib( 2n ) - Andras Erszegi (erszegi.andras(AT)chello.hu), Jun 28 2005

The i-th term of the sequence is the entry (1, 1) of the i-th power of the 2 by 2 matrix M=((1, 1), (1, 2)). - Simone Severini, Oct 15 2005

a(n-1)=(1/n)*sum_{k=0...n}B(2k)*F(2n-2k)*binomial(2n, 2k) where B(2k) is the (2k)-th Bernoulli number. - Benoit Cloitre, Nov 02 2005

a(n) = A055105(n,1)+A055105(n,2)+A055105(n,3) = A055106(n,1)+A055106(n,2). - Mike Zabrocki, Oct 24 2006

a(n)=2/sqrt(5)*cosh((2n-1)*psi), where psi=ln(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007

a(n) = (phi+1)^n - phi*A001906(n) with phi=(1+sqrt(5))/2. - Reinhard Zumkeller, Nov 22 2007

a(n) = 2*a(n-1)+2*a(n-2)-a(n-3); a(n) = (sqrt(5.0) + 5.0)/10.0*(3.0/2.0 + sqrt(5.0)/2.0)^(n-2) + (-sqrt(5.0) + 5.0)/10.0*(3.0/2.0 - sqrt(5.0)/2.0)^(n-2). - Antonio Alberto Olivares, Mar 21 2008

a(n)=A147703(n,0). - Philippe Deléham, Nov 29 2008

a(n) = -a(n-1)+11*a(n-2)-4*a(n-3), this formula (it is one of two 3rd order linear recurrence relations given for this sequence) is a result of the generating floretion Z = X*Y with X = 1.5'i + 0.5i' + .25(ii + jj + kk + ee) and Y = 0.5'i + 1.5i' + .25(ii + jj + kk + ee). - Creighton Dement, Jan 02 2009

With X,Y defined as X = ( F(n) F(n+1) ), Y = ( F(n+2) F(n+3) ), where F(n) is the n-th Fibonacci number (A000045), it follows a(n+2) = X.Y', where Y' is the transpose of Y (n >= 0). - K.V.Iyer, Apr 24 2009

a(n)= Fibonacci(2n+2) mod Fibonacci(2n), n>1. - Gary Detlefs, Nov 22 2010

a(n) = (Fibonacci(n-1)^2+Fibonacci(n)^2+Fibonacci(2n-1))/2. - _Gary Detlefs, Nov 22 2010

INVERT transform is A007051. First difference is A001906. Partial sums is A055588. Binomial transform is A093129. Binomial transform of A000045(n-1). - Michael Somos, May 03 2012

a(n) = (Fibonacci(n+2)^2 + Fibonacci(n-3)^2)/5. - Gary Detlefs, Dec 14 2012

G.f.: 1 + x/( Q(0) - x ) where Q(k) = 1 - x/(x*k + 1 )/Q(k+1) ; (recursively defined continued fraction). - Sergei N. Gladkovskii, Feb 23 2013

G.f.: (1-2*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 19 2013

G.f.: 1 + x*(1-x^2)*Q(0)/2 , where Q(k) = 1 + 1/(1 - x*(4*k+2 + 2*x - x^2)/( x*(4*k+4 + 2*x - x^2 ) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 11 2013

G.f.: Q(0,u), where u=x/(1-x), Q(k,u) = 1 + u^2 + (k+2)*u - u*(k+1 + u)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013

sum {n >= 2} 1/( a(n) - 1/a(n) ) = 1. Compare with A001906, A007805 and A097843. - Peter Bala, Nov 29 2013

Let F(n) be the Fibonacci number, A000045(n), and L(n) the Lucas number, A000032(n). Then for n>0, a(n) = F(n)*L(n-1) + (-1)^n. - Charlie Marion, Jan 01 2014

a(n) = A238731(n,0). - Philippe Deléham, Mar 05 2014

EXAMPLE

a(3)=13: there are 14 ordered trees with 4 edges; all of them, except for the path with 4 edges, have height at most 3.

G.f. = 1 + x + 2*x^2 + 5*x^3 + 13*x^4 + 34*x^5 + 89*x^6 + 233*x^7 + ...

MAPLE

A001519:=-(-1+z)/(1-3*z+z**2); #Simon Plouffe in his 1992 dissertation; gives sequence without an initial 1

A001519 := proc(n) option remember: if n=0 then 1 elif n=1 then 1 elif n>=2 then 3*procname(n-1)-procname(n-2) fi: end: seq(A001519(n), n=0..28); # Johannes W. Meijer, Aug 14 2011

MATHEMATICA

Fibonacci /@ (2Range[29] - 1) (* Robert G. Wilson v, Oct 05 2005 *)

LinearRecurrence[{3, -1}, {1, 1}, 29] (* Robert G. Wilson v, Jun 28 2012 *)

a[n_] := With[{c = Sqrt[5]/2}, ChebyshevT[2 n - 1, c]/c]; (* Michael Somos, Jul 08 2014 *)

PROG

(PARI) {a(n) = fibonacci(2*n - 1)}; /* Michael Somos, Jul 19 2003 */

(PARI) {a(n) = real( quadgen(5) ^ (2*n))}; /* Michael Somos, Jul 19 2003 */

(PARI) {a(n) = subst( poltchebi(n) + poltchebi(n - 1), x, 3/2) * 2/5}; /* Michael Somos, Jul 19 2003 */

(Sage) [lucas_number1(n, 3, 1)-lucas_number1(n-1, 3, 1) for n in xrange(0, 30)] # Zerinvary Lajos, Apr 29 2009

(Haskell)

a001519 n = a001519_list !! n

a001519_list = 1 : zipWith (-) (tail a001906_list) a001906_list

-- Reinhard Zumkeller, Jan 11 2012

a001519_list = 1 : f a000045_list where f (_:x:xs) = x : f xs

-- Reinhard Zumkeller, Aug 09 2013

(Maxima) a[0]:1$ a[1]:1$ a[n]:=3*a[n-1]-a[n-2]$ makelist(a[n], n, 0, 30); /* Martin Ettl, Nov 15 2012 */

(MAGMA) [1] cat [(Lucas(2*n) - Fibonacci(2*n))/2: n in [1..50]]; // Vincenzo Librandi, Jul 02 2014

CROSSREFS

Cf. A000045. a(n)= A060920(n, 0).

Row 3 of array A094954.

Equals A001654(n+1) - A001654(n-1), n>0.

Cf. A001653. A122367 is another version.

Cf. A055105, A055106, A055107, A074664, A124292, A124293, A124294, A124295, A140068, A140069, A153463.

Cf. inverse sequences A130255 and A130256.

Cf. A153266, A153267.

Cf. A144257.

Cf. A211216.

Row sums of A140068, A152251, A153342, A179806, A179745, A213948.

Sequence in context: A122367 * A048575 A099496 A114299 A112842 A097417

Adjacent sequences:  A001516 A001517 A001518 * A001520 A001521 A001522

KEYWORD

nonn,nice,easy,core,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Entry revised by N. J. A. Sloane, Aug 24 2006, May 13 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 25 23:20 EDT 2014. Contains 248565 sequences.