cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 21-30 of 349 results. Next

A007051 a(n) = (3^n + 1)/2.

Original entry on oeis.org

1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, 797162, 2391485, 7174454, 21523361, 64570082, 193710245, 581130734, 1743392201, 5230176602, 15690529805, 47071589414, 141214768241, 423644304722, 1270932914165, 3812798742494, 11438396227481
Offset: 0

Views

Author

Colin Mallows, N. J. A. Sloane, Simon Plouffe, Robert G. Wilson v

Keywords

Comments

Number of ordered trees with n edges and height at most 4.
Number of palindromic structures using a maximum of three different symbols. - Marks R. Nester
Number of compositions of all even natural numbers into n parts <= 2 (0 is counted as a part), see example. - Adi Dani, May 14 2011
Consider the mapping f(a/b) = (a + 2*b)/(2*a + b). Taking a = 1, b = 2 to start with, and carrying out this mapping repeatedly on each new (reduced) rational number gives the sequence 1/2, 4/5, 13/14, 40/41, ... converging to 1. The sequence contains the denominators = (3^n+1)/2. The same mapping for N, i.e., f(a/b) = (a + N*b)/(a+b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Second binomial transform of the expansion of cosh(x). - Paul Barry, Apr 05 2003
The sequence (1, 1, 2, 5, ...) = 3^n/6 + 1/2 + 0^n/3 has binomial transform A007581. - Paul Barry, Jul 20 2003
Number of (s(0), s(1), ..., s(2n+2)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| = 1 for i = 1, 2, ..., 2n+2, s(0) = 1, s(2n+2) = 1. - Herbert Kociemba, Jun 10 2004
Density of regular language L over {1,2,3}^* (i.e., number of strings of length n in L) described by regular expression 11*+11*2(1+2)*+11*2(1+2)*3(1+2+3)*. - Nelma Moreira, Oct 10 2004
Sums of rows of the triangle in A119258. - Reinhard Zumkeller, May 11 2006
Number of n-words from the alphabet A = {a,b,c} which contain an even number of a's. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Aug 30 2006
Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which either 0) x and y are disjoint and for which x is not a subset of y and y is not a subset of x, or 1) x = y. - Ross La Haye, Jan 10 2008
a(n+1) gives the number of primitive periodic multiplex juggling sequences of length n with base state <2>. - Steve Butler, Jan 21 2008
a(n) is also the number of idempotent order-preserving and order-decreasing partial transformations (of an n-chain). - Abdullahi Umar, Oct 02 2008
Equals row sums of triangle A147292. - Gary W. Adamson, Nov 05 2008
Equals leftmost column of A071919^3. - Gary W. Adamson, Apr 13 2009
A010888(a(n))=5 for n >= 2, that is, the digital root of the terms >= 5 equals 5. - Parthasarathy Nambi, Jun 03 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=5, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^n*charpoly(A,2). - Milan Janjic, Jan 27 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=6, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=(-1)^(n-1)*charpoly(A,3). - Milan Janjic, Feb 21 2010
It appears that if s(n) is a rational sequence of the form s(1)=2, s(n)= (2*s(n-1)+1)/(s(n-1)+2), n>1 then s(n)=a(n)/(a(n-1)-1).
Form an array with m(1,n)=1 and m(i,j) = Sum_{k=1..i-1} m(k,j) + Sum_{k=1..j-1} m(i,k), which is the sum of the terms to the left of m(i,j) plus the sum above m(i,j). The sum of the terms in antidiagonal(n-1) = a(n). - J. M. Bergot, Jul 16 2013
From Peter Bala, Oct 29 2013: (Start)
An Engel expansion of 3 to the base b := 3/2 as defined in A181565, with the associated series expansion 3 = b + b^2/2 + b^3/(2*5) + b^4/(2*5*14) + .... Cf. A034472.
More generally, for a positive integer n >= 3, the sequence [1, n - 1, n^2 - n - 1, ..., ( (n - 2)*n^k + 1 )/(n - 1), ...] is an Engel expansion of n/(n - 2) to the base n/(n - 1). Cases include A007583 (n = 4), A083065 (n = 5) and A083066 (n = 6). (End)
Diagonal elements (and one more than antidiagonal elements) of the matrix A^n where A=(2,1;1,2). - David Neil McGrath, Aug 17 2014
From M. Sinan Kul, Sep 07 2016: (Start)
a(n) is equal to the number of integer solutions to the following equation when x is equal to the product of n distinct primes: 1/x = 1/y + 1/z where 0 < x < y <= z.
If z = k*y where k is a fraction >= 1 then the solutions can be given as: y = ((k+1)/k)*x and z = (k+1)*x.
Here k can be equal to any divisor of x or to the ratio of two divisors.
For example for x = 2*3*5 = 30 (product of three distinct primes), k would have the following 14 values: 1, 6/5, 3/2, 5/3, 2, 5/2, 3, 10/3, 5, 6, 15/2, 10, 15, 30.
As an example for k = 10/3, we would have y=39, z=130 and 1/39 + 1/130 = 1/30.
Here finding the number of fractions would be equivalent to distributing n balls (distinct primes) to two bins (numerator and denominator) with no empty bins which can be found using Stirling numbers of the second kind. So another definition for a(n) is: a(n) = 2^n + Sum_{i=2..n} Stirling2(i,2)*binomial(n,i).
(End)
a(n+1) is the smallest i for which the Catalan number C(i) (see A000108) is divisible by 3^n for n > 0. This follows from the rule given by Franklin T. Adams-Watters for determining the multiplicity with which a prime divides C(n). We need to find the smallest number in base 3 to achieve a given count. Applied to prime 3, 1 is the smallest digit that counts but requires to be followed by 2 which cannot be at the end to count. Therefore the number in base 3 of the form 1{n-1 times}20 = (3^(n+1) + 1)/2 + 1 = a(n+1)+1 is the smallest number to achieve count n which implies the claim. - Peter Schorn, Mar 06 2020
Let A be a Toeplitz matrix of order n, defined by: A[i,j]=1, if ij; A[i,i]=2. Then, for n>=1, a(n) = det A. - Dmitry Efimov, Oct 28 2021
a(n) is the least number k such that A065363(k) = -(n-1), for n > 0. - Amiram Eldar, Sep 03 2022

Examples

			From _Adi Dani_, May 14 2011: (Start)
a(3)=14 because all compositions of even natural numbers into 3 parts <=2 are
for 0: (0,0,0)
for 2: (0,1,1), (1,0,1), (1,1,0), (0,0,2), (0,2,0), (2,0,0)
for 4: (0,2,2), (2,0.2), (2,2,0), (1,1,2), (1,2,1), (2,1,1)
for 6: (2,2,2).
(End)

References

  • J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 47.
  • Adi Dani, Quasicompositions of natural numbers, Proceedings of III congress of mathematicians of Macedonia, Struga Macedonia 29 IX -2 X 2005 pages 225-238.
  • R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E11.
  • M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
  • P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 60.
  • P. Ribenboim, The Little Book of Big Primes, Springer-Verlag, NY, 1991, p. 53.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A056449, A064881-A064886, A008277, A007581, A056272, A056273, A000392, A000079, A034472, A147292, A003462, A065363, A071919, A007583, A083065, A083066.
A row of the array in A278984.

Programs

Formula

a(n) = 3*a(n-1) - 1.
Binomial transform of Chebyshev coefficients A011782. - Paul Barry, Mar 16 2003
From Paul Barry, Mar 16 2003: (Start)
a(n) = 4*a(n-1) - 3*a(n-2) for n > 1, a(0)=1, a(1)=2.
G.f.: (1 - 2*x)/((1 - x)*(1 - 3*x)). (End)
E.g.f.: exp(2*x)*cosh(x). - Paul Barry, Apr 05 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*2^(n-2*k). - Paul Barry, May 08 2003
This sequence is also the partial sums of the first 3 Stirling numbers of second kind: a(n) = S(n+1, 1) + S(n+1, 2) + S(n+1, 3) for n >= 0; alternatively it is the number of partitions of [n+1] into 3 or fewer parts. - Mike Zabrocki, Jun 21 2004
For c=3, a(n) = (c^n)/c! + Sum_{k=1..c-2}((k^n)/k!*(Sum_{j=2..c-k}(((-1)^j)/j!))) or = Sum_{k=1..c} g(k, c)*k^n where g(1, 1) = 1, g(1, c) = g(1, c-1) + ((-1)^(c-1))/(c-1)! for c > 1, and g(k, c) = g(k-1, c-1)/k for c > 1 and 2 <= k <= c. - Nelma Moreira, Oct 10 2004
The i-th term of the sequence is the entry (1, 1) in the i-th power of the 2 X 2 matrix M = ((2, 1), (1, 2)). - Simone Severini, Oct 15 2005
If p[i]=fibonacci(2i-3) 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
INVERT transform of A001519: [1, 1, 2, 5, 13, 34, ...]. - Gary W. Adamson, Jun 13 2011
a(n) = M^n*[1,1,1,0,0,0,...], leftmost column term; where M = an infinite bidiagonal matrix with all 1's in the superdiagonal and (1,2,3,...) in the main diagonal and the rest zeros. - Gary W. Adamson, Jun 23 2011
a(n) = M^n*[1,1,1,0,0,0,...], top entry term; where M is an infinite bidiagonal matrix with all 1's in the superdiagonal, (1,2,3,...) as the main diagonal, and the rest zeros. - Gary W. Adamson, Jun 24 2011
a(n) = A201730(n,0). - Philippe Deléham, Dec 05 2011
a(n) = A006342(n) + A006342(n-1). - Yuchun Ji, Sep 19 2018
From Dmitry Efimov, Oct 29 2021: (Start)
a(2*m+1) = Product_{k=-m..m} (2+i*tan(Pi*k/(2*m+1))),
a(2*m) = Product_{k=-m..m-1} (2+i*tan(Pi*(2*k+1)/(4*m))),
where i is the imaginary unit. (End)

A005043 Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).

Original entry on oeis.org

1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also called Motzkin summands or ring numbers.
The old name was "Motzkin sums", used in certain publications. The sequence has the property that Motzkin(n) = A001006(n) = a(n) + a(n+1), e.g., A001006(4) = 9 = 3 + 6 = a(4) + a(5).
Number of 'Catalan partitions', that is partitions of a set 1,2,3,...,n into parts that are not singletons and whose convex hulls are disjoint when the points are arranged on a circle (so when the parts are all pairs we get Catalan numbers). - Aart Blokhuis (aartb(AT)win.tue.nl), Jul 04 2000
Number of ordered trees with n edges and no vertices of outdegree 1. For n > 1, number of dissections of a convex polygon by nonintersecting diagonals with a total number of n+1 edges. - Emeric Deutsch, Mar 06 2002
Number of Motzkin paths of length n with no horizontal steps at level 0. - Emeric Deutsch, Nov 09 2003
Number of Dyck paths of semilength n with no peaks at odd level. Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUDUDD, where U=(1,1), D=(1,-1). Number of Dyck paths of semilength n with no ascents of length 1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUUDDD. - Emeric Deutsch, Dec 05 2003
Arises in Schubert calculus as follows. Let P = complex projective space of dimension n+1. Take n projective subspaces of codimension 3 in P in general position. Then a(n) is the number of lines of P intersecting all these subspaces. - F. Hirzebruch, Feb 09 2004
Difference between central trinomial coefficient and its predecessor. Example: a(6) = 15 = 141 - 126 and (1 + x + x^2)^6 = ... + 126*x^5 + 141*x^6 + ... (Catalan number A000108(n) is the difference between central binomial coefficient and its predecessor.) - David Callan, Feb 07 2004
a(n) = number of 321-avoiding permutations on [n] in which each left-to-right maximum is a descent (i.e., is followed by a smaller number). For example, a(4) counts 4123, 3142, 2143. - David Callan, Jul 20 2005
The Hankel transform of this sequence give A000012 = [1, 1, 1, 1, 1, 1, 1, ...]; example: Det([1, 0, 1, 1; 0, 1, 1, 3; 1, 1, 3, 6; 1, 3, 6, 15]) = 1. - Philippe Deléham, May 28 2005
The number of projective invariants of degree 2 for n labeled points on the projective line. - Benjamin J. Howard (bhoward(AT)ima.umn.edu), Nov 24 2006
Define a random variable X=trA^2, where A is a 2 X 2 unitary symplectic matrix chosen from USp(2) with Haar measure. The n-th central moment of X is E[(X+1)^n] = a(n). - Andrew V. Sutherland, Dec 02 2007
Let V be the adjoint representation of the complex Lie algebra sl(2). The dimension of the invariant subspace of the n-th tensor power of V is a(n). - Samson Black (sblack1(AT)uoregon.edu), Aug 27 2008
Starting with offset 3 = iterates of M * [1,1,1,...], where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - Gary W. Adamson, Jan 08 2009
a(n) has the following standard-Young-tableaux (SYT) interpretation: binomial(n+1,k)*binomial(n-k-1,k-1)/(n+1)=f^(k,k,1^{n-2k}) where f^lambda equals the number of SYT of shape lambda. - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 02 2010
a(n) is also the sum of the numbers of standard Young tableaux of shapes (k,k,1^{n-2k}) for all 1 <= k <= floor(n/2). - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 10 2010
a(n) is the number of derangements of {1,2,...,n} having genus 0. The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q. Example: a(3)=1 because p=231=(123) is the only derangement of {1,2,3} with genus 0. Indeed, cp'=231*312=123=(1)(2)(3) and so g(p) = (1/2)(3+1-1-3)=0. - Emeric Deutsch, May 29 2010
Apparently: Number of Dyck 2n-paths with all ascents length 2 and no descent length 2. - David Scambler, Apr 17 2012
This is true. Proof: The mapping "insert a peak (UD) after each upstep (U)" is a bijection from all Dyck n-paths to those Dyck (2n)-paths in which each ascent is of length 2. It sends descents of length 1 in the n-path to descents of length 2 in the (2n)-path. But Dyck n-paths with no descents of length 1 are equinumerous with Riordan n-paths (Motzkin n-paths with no flatsteps at ground level) as follows. Given a Dyck n-path with no descents of length 1, split it into consecutive step pairs, then replace UU with U, DD with D, UD with a blue flatstep (F), DU with a red flatstep, and concatenate the new steps to get a colored Motzkin path. Each red F will be (immediately) preceded by a blue F or a D. In the latter case, transfer the red F so that it precedes the matching U of the D. Finally, erase colors to get the required Riordan path. For example, with lowercase f denoting a red flatstep, U^5 D^2 U D^4 U^4 D^3 U D^2 -> (U^2, U^2, UD, DU, D^2, D^2, U^2, U^2 D^2, DU, D^2) -> UUFfDDUUDfD -> UUFFDDUFUDD. - David Callan, Apr 25 2012
From Nolan Wallach, Aug 20 2014: (Start)
Let ch[part1, part2] be the value of the character of the symmetric group on n letters corresponding to the partition part1 of n on the conjucgacy class given by part2. Let A[n] be the set of (n+1) partitions of 2n with parts 1 or 2. Then deleting the first term of the sequence one has a(n) = Sum_{k=1..n+1} binomial(n,k-1)*ch[[n,n], A[n][[k]]])/2^n. This via the Frobenius Character Formula can be interpreted as the dimension of the SL(n,C) invariants in tensor^n (wedge^2 C^n).
Explanation: Let p_j denote sum (x_i)^j the sum in k variables. Then the Frobenius formula says then (p_1)^j_1 (p_2)^j_2 ... (p_r)^j_r is equal to sum(lambda, ch[lambda, 1^j_12^j_2 ... r^j_r] S_lambda) with S_lambda the Schur function corresponding to lambda. This formula implies that the coefficient of S([n,n]) in (((p_1)^1+p_2)/2)^n in its expansion in terms of Schur functions is the right hand side of our formula. If we specialize the number of variables to 2 then S[n,n](x,y)=(xy)^n. Which when restricted to y=x^(-1) is 1. That is it is 1 on SL(2).
On the other hand ((p_1)^2+p_2)/2 is the complete homogeneous symmetric function of degree 2 that is tr(S^2(X)). Thus our formula for a(n) is the same as that of Samson Black above since his V is the same as S^2(C^2) as a representation of SL(2). On the other hand, if we multiply ch(lambda) by sgn you get ch(Transpose(lambda)). So ch([n,n]) becomes ch([2,...,2]) (here there are n 2's). The formula for a(n) is now (1/2^n)*Sum_{j=0..n} ch([2,..,2], 1^(2n-2j) 2^j])*(-1)^j)*binomial(n,j), which calculates the coefficient of S_(2,...,2) in (((p_1)^2-p_2)/2)^n. But ((p_1)^2-p_2)/2 in n variables is the second elementary symmetric function which is the character of wedge^2 C^n and S_(2,...,2) is 1 on SL(n).
(End)
a(n) = number of noncrossing partitions (A000108) of [n] that contain no singletons, also number of nonnesting partitions (A000108) of [n] that contain no singletons. - David Callan, Aug 27 2014
From Tom Copeland, Nov 02 2014: (Start)
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).
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)].
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).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)].
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).
Various relations among the o.g.f.s may be easily constructed, such as Fib[-Mot(-x)] = -P[P(-x)] = x/(1-2*x) a generating fct for 2^n.
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]. (End)
Consistent with David Callan's comment above, A249548, provides a refinement of the Motzkin sums into the individual numbers for the non-crossing partitions he describes. - Tom Copeland, Nov 09 2014
The number of lattice paths from (0,0) to (n,0) that do not cross below the x-axis and use up-step=(1,1) and down-steps=(1,-k) where k is a positive integer. For example, a(4) = 3: [(1,1)(1,1)(1,-1)(1,-1)], [(1,1)(1,-1)(1,1)(1,-1)] and [(1,1)(1,1)(1,1)(1,-3)]. - Nicholas Ham, Aug 19 2015
A series created using 2*(a(n) + a(n+1)) + (a(n+1) + a(n+2)) has Hankel transform of F(2n), offset 3, F being a Fibonacci number, A001906 (Empirical observation). - Tony Foster III, Jul 30 2016
The series a(n) + A001006(n) has Hankel transform F(2n+1), offset n=1, F being the Fibonacci bisection A001519 (empirical observation). - Tony Foster III, Sep 05 2016
The Rubey and Stump reference proves a refinement of a conjecture of René Marczinzik, which they state as: "The number of 2-Gorenstein algebras which are Nakayama algebras with n simple modules and have an oriented line as associated quiver equals the number of Motzkin paths of length n. Moreover, the number of such algebras having the double centraliser property with respect to a minimal faithful projective-injective module equals the number of Riordan paths, that is, Motzkin paths without level-steps at height zero, of length n." - Eric M. Schmidt, Dec 16 2017
A connection to the Thue-Morse sequence: (-1)^a(n) = (-1)^A010060(n) * (-1)^A010060(n+1) = A106400(n) * A106400(n+1). - Vladimir Reshetnikov, Jul 21 2019
Named by Bernhart (1999) after the American mathematician John Riordan (1903-1988). - Amiram Eldar, Apr 15 2021

Examples

			a(5)=6 because the only dissections of a polygon with a total number of 6 edges are: five pentagons with one of the five diagonals and the hexagon with no diagonals.
G.f. = 1 + x^2 + x^3 + 3*x^4 + 6*x^5 + 15*x^6 + 36*x^7 + 91*x^8 + 232*x^9 + ...
From _Gus Wiseman_, Nov 15 2022: (Start)
The a(0) = 1 through a(6) = 15 lone-child-avoiding (no vertices of outdegree 1) ordered rooted trees with n + 1 vertices (ranked by A358376):
  o  .  (oo)  (ooo)  (oooo)   (ooooo)   (oooooo)
                     ((oo)o)  ((oo)oo)  ((oo)ooo)
                     (o(oo))  ((ooo)o)  ((ooo)oo)
                              (o(oo)o)  ((oooo)o)
                              (o(ooo))  (o(oo)oo)
                              (oo(oo))  (o(ooo)o)
                                        (o(oooo))
                                        (oo(oo)o)
                                        (oo(ooo))
                                        (ooo(oo))
                                        (((oo)o)o)
                                        ((o(oo))o)
                                        ((oo)(oo))
                                        (o((oo)o))
                                        (o(o(oo)))
(End)

References

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

Links

Crossrefs

Row sums of triangle A020474, first differences of A082395.
First diagonal of triangular array in A059346.
Binomial transform of A126930. - Philippe Deléham, Nov 26 2009
The Hankel transform of a(n+1) is A128834. The Hankel transform of a(n+2) is floor((2*n+4)/3) = A004523(n+2). - Paul Barry, Mar 08 2011
The Kn11 triangle sums of triangle A175136 lead to A005043(n+2), while the Kn12(n) = A005043(n+4)-2^(n+1), Kn13(n) = A005043(n+6)-(n^2+9*n+56)*2^(n-2) and the Kn4(n) = A005043(2*n+2) = A099251(n+1) triangle sums are related to the sequence given above. For the definitions of these triangle sums see A180662. - Johannes W. Meijer, May 06 2011
Cf. A187306 (self-convolution), A348210 (column 1).
Cf. A000045, A000108, A000957, A001006, A005717, A005773, A007317, A057078, A091867, A104597, A126120, A178514, A249548, A309303.
Bisections: A099251, A099252.

Programs

  • Haskell
    a005043 n = a005043_list !! n
a005043_list = 1 : 0 : zipWith div
   (zipWith (*) [1..] (zipWith (+)
       (map (* 2) $ tail a005043_list) (map (* 3) a005043_list))) [3..]
-- Reinhard Zumkeller, Jan 31 2012
  • Maple
    A005043 := proc(n) option remember; if n <= 1 then 1-n else (n-1)*(2*A005043(n-1)+3*A005043(n-2))/(n+1); fi; end;
Order := 20: solve(series((x-x^2)/(1-x+x^2),x)=y,x); # outputs g.f.
  • Mathematica
    a[0]=1; a[1]=0; a[n_]:= a[n] = (n-1)*(2*a[n-1] + 3*a[n-2])/(n+1); Table[ a[n], {n, 0, 30}] (* Robert G. Wilson v, Jun 14 2005 *)
Table[(-3)^(1/2)/6 * (-1)^n*(3*Hypergeometric2F1[1/2,n+1,1,4/3]+ Hypergeometric2F1[1/2,n+2,1,4/3]), {n,0,32}] (* cf. Mark van Hoeij in A001006 *) (* Wouter Meeussen, Jan 23 2010 *)
RecurrenceTable[{a[0]==1,a[1]==0,a[n]==(n-1) (2a[n-1]+3a[n-2])/(n+1)},a,{n,30}] (* Harvey P. Dale, Sep 27 2013 *)
a[ n_]:= SeriesCoefficient[2/(1+x +Sqrt[1-2x-3x^2]), {x, 0, n}]; (* Michael Somos, Aug 21 2014 *)
a[ n_]:= If[n<0, 0, 3^(n+3/2) Hypergeometric2F1[3/2, n+2, 2, 4]/I]; (* Michael Somos, Aug 21 2014 *)
Table[3^(n+3/2) CatalanNumber[n] (4(5+2n)Hypergeometric2F1[3/2, 3/2, 1/2-n, 1/4] -9 Hypergeometric2F1[3/2, 5/2, 1/2 -n, 1/4])/(4^(n+3) (n+1)), {n, 0, 31}] (* Vladimir Reshetnikov, Jul 21 2019 *)
Table[Sqrt[27]/8 (3/4)^n CatalanNumber[n] Hypergeometric2F1[1/2, 3/2, 1/2 - n, 1/4], {n, 0, 31}] (* Jan Mangaldan, Sep 12 2021 *)
  • Maxima
    a[0]:1$
a[1]:0$
a[n]:=(n-1)*(2*a[n-1]+3*a[n-2])/(n+1)$
makelist(a[n],n,0,12); /* Emanuele Munarini, Mar 02 2011 */
  • PARI
    {a(n) = if( n<0, 0, n++; polcoeff( serreverse( (x - x^3) / (1 + x^3) + x * O(x^n)), n))}; /* Michael Somos, May 31 2005 */
  • PARI
    my(N=66); Vec(serreverse(x/(1+x*sum(k=1,N,x^k))+O(x^N))) \\ Joerg Arndt, Aug 19 2012
  • Python
    from functools import cache
@cache
def A005043(n: int) -> int:
    if n <= 1: return 1 - n
    return (n - 1) * (2 * A005043(n - 1) + 3 * A005043(n - 2)) // (n + 1)
print([A005043(n) for n in range(32)]) # Peter Luschny, Nov 20 2022
  • Sage
    A005043 = lambda n: (-1)^n*jacobi_P(n,1,-n-3/2,-7)/(n+1)
[simplify(A005043(n)) for n in (0..29)]
# Peter Luschny, Sep 23 2014
  • Sage
    def ms():
    a, b, c, d, n = 0, 1, 1, -1, 1
    yield 1
    while True:
        yield -b + (-1)^n*d
        n += 1
        a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)/((n+1)*(n-1))
        c, d = d, (3*(n-1)*c-(2*n-1)*d)/n
A005043 = ms()
print([next(A005043) for  in range(32)]) # _Peter Luschny, May 16 2016

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*A000108(k). a(n) = (1/(n+1)) * Sum_{k=0..ceiling(n/2)} binomial(n+1, k)*binomial(n-k-1, k-1), for n > 1. - Len Smiley. [Comment from Amitai Regev (amitai.regev(AT)weizmann.ac.il), Mar 02 2010: the latter sum should be over the range k=1..floor(n/2).]
G.f.: (1 + x - sqrt(1-2*x-3*x^2))/(2*x*(1+x)).
G.f.: 2/(1+x+sqrt(1-2*x-3*x^2)). - Paul Peart (ppeart(AT)fac.howard.edu), May 27 2000
a(n+1) + (-1)^n = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0). - Bernhart
a(n) = (1/(n+1)) * Sum_{i} (-1)^i*binomial(n+1, i)*binomial(2*n-2*i, n-i). - Bernhart
G.f. A(x) satisfies A = 1/(1+x) + x*A^2.
E.g.f.: exp(x)*(BesselI(0, 2*x) - BesselI(1, 2*x)). - Vladeta Jovovic, Apr 28 2003
a(n) = A001006(n-1) - a(n-1).
a(n+1) = Sum_{k=0..n} (-1)^k*A026300(n, k), where A026300 is the Motzkin triangle.
a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(k, floor(k/2)). - Paul Barry, Jan 27 2005
a(n) = Sum_{k>=0} A086810(n-k, k). - Philippe Deléham, May 30 2005
a(n+2) = Sum_{k>=0} A064189(n-k, k). - Philippe Deléham, May 31 2005
Moment representation: a(n) = (1/(2*Pi))*Int(x^n*sqrt((1+x)(3-x))/(1+x),x,-1,3). - Paul Barry, Jul 09 2006
Inverse binomial transform of A000108 (Catalan numbers). - Philippe Deléham, Oct 20 2006
a(n) = (2/Pi)* Integral_{x=0..Pi} (4*cos(x)^2-1)^n*sin(x)^2 dx. - Andrew V. Sutherland, Dec 02 2007
G.f.: 1/(1-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued fraction). - Paul Barry, Jan 22 2009
G.f.: 1/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-... (continued fraction). - Paul Barry, May 16 2009
G.f.: 1/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-... (continued fraction). - Paul Barry, Mar 02 2010
a(n) = -(-1)^n * hypergeom([1/2, n+2],[2],4/3) / sqrt(-3). - Mark van Hoeij, Jul 02 2010
a(n) = (-1)^n*hypergeometric([-n,1/2],[2],4). - Peter Luschny, Aug 15 2012
Let A(x) be the g.f., then x*A(x) is the reversion of x/(1 + x^2*Sum_{k>=0} x^k); see A215340 for the correspondence to Dyck paths without length-1 ascents. - Joerg Arndt, Aug 19 2012 and Apr 16 2013
a(n) ~ 3^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 02 2012
G.f.: 2/(1+x+1/G(0)), where G(k) = 1 + x*(2+3*x)*(4*k+1)/( 4*k+2 - x*(2+3*x)*(4*k+2)*(4*k+3)/(x*(2+3*x)*(4*k+3) + 4*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 05 2013
D-finite (an alternative): (n+1)*a(n) = 3*(n-2)*a(n-3) + (5*n-7)*a(n-2) + (n-2)*a(n-1), n >= 3. - Fung Lam, Mar 22 2014
Asymptotics: a(n) = (3^(n+2)/(sqrt(3*n*Pi)*(8*n)))*(1-21/(16*n) + O(1/n^2)) (with contribution by Vaclav Kotesovec). - Fung Lam, Mar 22 2014
a(n) = T(2*n-1,n)/n, where T(n,k) = triangle of A180177. - Vladimir Kruchinin, Sep 23 2014
a(n) = (-1)^n*JacobiP(n,1,-n-3/2,-7)/(n+1). - Peter Luschny, Sep 23 2014
a(n) = Sum_{k=0..n} C(n,k)*(C(k,n-k)-C(k,n-k-1)). - Peter Luschny, Oct 01 2014
Conjecture: a(n) = A002426(n) - A005717(n), n > 0. - Mikhail Kurkov, Feb 24 2019 [The conjecture is true. - Amiram Eldar, May 17 2024]
a(n) = A309303(n) + A309303(n+1). - Vladimir Reshetnikov, Jul 22 2019
From Peter Bala, Feb 11 2022: (Start)
a(n) = A005773(n+1) - 2*A005717(n) for n >= 1.
Conjectures: for n >= 1, n divides a(2*n+1) and 2*n-1 divides a(2*n). (End)

Extensions

Thanks to Laura L. M. Yang (yanglm(AT)hotmail.com) for a correction, Aug 29 2004
Name changed to Riordan numbers following a suggestion from Ira M. Gessel. - N. J. A. Sloane, Jul 24 2020

A005248 Bisection of Lucas numbers: a(n) = L(2*n) = A000032(2*n).

Original entry on oeis.org

2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, 15127, 39603, 103682, 271443, 710647, 1860498, 4870847, 12752043, 33385282, 87403803, 228826127, 599074578, 1568397607, 4106118243, 10749957122, 28143753123, 73681302247, 192900153618, 505019158607, 1322157322203
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Drop initial 2; then iterates of A050411 do not diverge for these starting values. - David W. Wilson
All nonnegative integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = +4 together with b(n)=A001906(n), n>=0. - Wolfdieter Lang, Aug 31 2004
a(n+1) = B^(n)AB(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., 3=`10`, 7=`010`, 18=`0010`, 47=`00010`, ..., in Wythoff code. a(0) = 2 = B(1) in Wythoff code.
Output of Tesler's formula (as well as that of Lu and Wu) for the number of perfect matchings of an m X n Möbius band where m and n are both even specializes to this sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009
Numbers having two 1's in their base-phi representation. - Robert G. Wilson v, Sep 13 2010
Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... - R. J. Mathar, Aug 10 2012
From Wolfdieter Lang, Feb 18 2013: (Start)
a(n) is also one half of the total number of round trips, each of length 2*n, on the graph P_4 (o-o-o-o) (the simple path with 4 points (vertices) and 3 lines (or edges)). See the array and triangle A198632 for the general case of the graph P_N (there N is n and the length is l=2*k).
O.g.f. for w(4,l) (with zeros for odd l): y*(d/dy)S(4,y)/S(4,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form. One half of this o.g.f. for x -> sqrt(x) produces the g.f. (2-3x)/(1-3x+x^2) given below. (End)
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy - 5. - Michel Lagneau, Feb 01 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 7xy + y^2 + 45 = 0. - Colin Barker, Feb 16 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 320 = 0. - Colin Barker, Feb 16 2014
a(n) are the numbers such that a(n)^2-2 are Lucas numbers. - Michel Lagneau, Jul 22 2014
All sequences of this form, b(n+1) = 3*b(n) - b(n-1), regardless of initial values, which includes this sequence, yield this sequence as follows: a(n) = (b(j+n) + b(j-n))/b(j), for any j, except where b(j) = 0. Also note formula below relating this a(n) to all sequences of the form G(n+1) = G(n) + G(n-1). - Richard R. Forberg, Nov 18 2014
A non-simple continued fraction expansion for F(2n*(k+1))/F(2nk) k>=1 is a(n) + (-1)/(a(n) + (-1)/(a(n) + ... + (-1)/a(n))) where a(n) appears exactly k times (F(n) denotes the n-th Fibonacci number). E.g., F(16)/F(12) equals 7 + (-1)/(7 + (-1)/7). Furthermore, these a(n) are exactly the positive integers k such that the non-simple infinite continued fraction k + (-1)/(k + (-1)/(k + (-1)/(k + ...))) belongs to Q(sqrt(5)). Compare to Benoit Cloitre and Thomas Baruchel's comments at A002878. - Greg Dresden, Aug 13 2019
For n >= 1, a(n) is the number of cyclic up-down words of length 2*n over an alphabet of size 3. - Sela Fried, Apr 08 2025

Examples

			G.f. = 2 + 3*x + 7*x^2 + 18*x^3 + 47*x^4 + 123*x^5 + 322*x^6 + 843*x^7 + ... - _Michael Somos_, Aug 11 2009

References

  • 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).
  • Richard P. Stanley, Enumerative combinatorics, Vol. 2. Volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

Links

Crossrefs

Cf. A000032, A002878 (odd-indexed Lucas numbers), A001906 (Chebyshev S(n-1, 3)), a(n) = sqrt(4+5*A001906(n)^2), A228842.
a(n) = A005592(n)+1 = A004146(n)+2 = A065034(n)-1.
First differences of A002878. Pairwise sums of A001519. First row of array A103997.
Cf. A153415, A201157. Also Lucas(k*n): A000032 (k = 1), A014448 (k = 3), A056854 (k = 4), A001946 (k = 5), A087215 (k = 6), A087281 (k = 7), A087265 (k = 8), A087287 (k = 9), A065705 (k = 10), A089772 (k = 11), A089775 (k = 12).

Programs

  • Haskell
    a005248 n = a005248_list !! n
a005248_list = zipWith (+) (tail a001519_list) a001519_list
-- Reinhard Zumkeller, Jan 11 2012
  • Magma
    [Lucas(2*n) : n in [0..100]]; // Vincenzo Librandi, Apr 14 2011
  • Maple
    a:= n-> (<<2|3>>. <<3|1>, <-1|0>>^n)[1$2]: seq(a(n), n=0..30); # Alois P. Heinz, Jul 31 2008
with(combinat): seq(5*fibonacci(n)^2+2*(-1)^n, n= 0..26);
  • Mathematica
    a[0] = 2; a[1] = 3; a[n_] := 3a[n - 1] - a[n - 2]; Table[ a[n], {n, 0, 27}] (* Robert G. Wilson v, Jan 30 2004 *)
Fibonacci[1 + 2n] + 1/2 (-Fibonacci[2n] + LucasL[2n]) (* Tesler. Sarah-Marie Belcastro, Jul 04 2009 *)
LinearRecurrence[{3, -1}, {2, 3}, 50] (* Sture Sjöstedt, Nov 27 2011 *)
LucasL[Range[0,60,2]] (* Harvey P. Dale, Sep 30 2014 *)
  • PARI
    {a(n) = fibonacci(2*n + 1) + fibonacci(2*n - 1)}; /* Michael Somos, Jun 23 2002 */
  • PARI
    {a(n) = 2 * subst( poltchebi(n), x, 3/2)}; /* Michael Somos, Jun 28 2003 */
  • Sage
    [lucas_number2(n,3,1) for n in range(37)] # Zerinvary Lajos, Jun 25 2008

Formula

a(n) = Fibonacci(2*n-1) + Fibonacci(2*n+1).
G.f.: (2-3*x)/(1-3*x+x^2). - Simon Plouffe in his 1992 dissertation.
a(n) = S(n, 3) - S(n-2, 3) = 2*T(n, 3/2) with S(n-1, 3) = A001906(n) and S(-2, x) = -1. U(n, x)=S(n, 2*x) and T(n, x) are Chebyshev's U- and T-polynomials.
a(n) = a(k)*a(n - k) - a(n - 2k) for all k, i.e., a(n) = 2*a(n) - a(n) = 3*a(n - 1) - a(n - 2) = 7*a(n - 2) - a(n - 4) = 18*a(n - 3) - a(n - 6) = 47*a(n - 4) - a(n - 8) etc., a(2n) = a(n)^2 - 2. - Henry Bottomley, May 08 2001
a(n) = A060924(n-1, 0) = 3*A001906(n) - 2*A001906(n-1), n >= 1. - Wolfdieter Lang, Apr 26 2001
a(n) ~ phi^(2*n) where phi=(1+sqrt(5))/2. - Joe Keane (jgk(AT)jgk.org), May 15 2002
a(0)=2, a(1)=3, a(n) = 3*a(n-1) - a(n-2) = a(-n). - Michael Somos, Jun 28 2003
a(n) = phi^(2*n) + phi^(-2*n) where phi=(sqrt(5)+1)/2, the golden ratio. E.g., a(4)=47 because phi^(8) + phi^(-8) = 47. - Dennis P. Walsh, Jul 24 2003
With interpolated zeros, trace(A^n)/4, where A is the adjacency matrix of path graph P_4. Binomial transform is then A049680. - Paul Barry, Apr 24 2004
a(n) = (floor((3+sqrt(5))^n) + 1)/2^n. - Lekraj Beedassy, Oct 22 2004
a(n) = ((3-sqrt(5))^n + (3+sqrt(5))^n)/2^n (Note: substituting the number 1 for 3 in the last equation gives A000204, substituting 5 for 3 gives A020876). - Creighton Dement, Apr 19 2005
a(n) = (1/(n+1/2))*Sum_{k=0..n} B(2k)*L(2n+1-2k)*binomial(2n+1, 2k) where B(2k) is the (2k)-th Bernoulli number. - Benoit Cloitre, Nov 02 2005
a(n) = term (1,1) in the 1 X 2 matrix [2,3] . [3,1; -1,0]^n. - Alois P. Heinz, Jul 31 2008
a(n) = 2*cosh(2*n*psi), where psi=log((1+sqrt(5))/2). - Al Hakanson, Mar 21 2009
From Sarah-Marie Belcastro, Jul 04 2009: (Start)
a(n) - (a(n) - F(2n))/2 - F(2n+1) = 0. (Tesler)
Product_{r=1..n} (1 + 4*(sin((4r-1)*Pi/(4n)))^2). (Lu/Wu) (End)
a(n) = Fibonacci(2n+6) mod Fibonacci(2n+2), n > 1. - Gary Detlefs, Nov 22 2010
a(n) = 5*Fibonacci(n)^2 + 2*(-1)^n. - Gary Detlefs, Nov 22 2010
a(n) = A033888(n)/A001906(n), n > 0. - Gary Detlefs, Dec 26 2010
a(n) = 2^(2*n) * Sum_{k=1..2} (cos(k*Pi/5))^(2*n). - L. Edson Jeffery, Jan 21 2012
From Peter Bala, Jan 04 2013: (Start)
Let F(x) = Product_{n>=0} (1 + x^(4*n+1))/(1 + x^(4*n+3)). Let alpha = 1/2*(3 - sqrt(5)). This sequence gives the simple continued fraction expansion of 1 + F(alpha) = 2.31829 56058 81914 31334 ... = 2 + 1/(3 + 1/(7 + 1/(18 + ...))).
Also F(-alpha) = 0.64985 97768 07374 32950 has the continued fraction representation 1 - 1/(3 - 1/(7 - 1/(18 - ...))) and the simple continued fraction expansion 1/(1 + 1/((3-2) + 1/(1 + 1/((7-2) + 1/(1 + 1/((18-2) + 1/(1 + ...))))))).
F(alpha)*F(-alpha) has the simple continued fraction expansion 1/(1 + 1/((3^2-4) + 1/(1 + 1/((7^2-4) + 1/(1 + 1/((18^2-4) + 1/(1 + ...))))))).
Added Oct 13 2019: 1/2 + 1/2*F(alpha)/F(-alpha) = 1.5142923542... has the simple continued fraction expansion 1 + 1/((3 - 2) + 1/(1 + 1/((18 - 2) + 1/(1 + 1/(123 - 2) + 1/(1 + ...))))). (End)
G.f.: (W(0)+6)/(5*x), where W(k) = 5*x*k + x - 6 + 6*x*(5*k-9)/W(k+1) (continued fraction). - Sergei N. Gladkovskii, Aug 19 2013
Sum_{n >= 1} 1/( a(n) - 5/a(n) ) = 1. Compare with A001906, A002878 and A023039. - Peter Bala, Nov 29 2013
0 = a(n) * a(n+2) - a(n+1)^2 - 5 for all n in Z. - Michael Somos, Aug 24 2014
a(n) = (G(j+2n) + G(j-2n))/G(j), for n >= 0 and any j, positive or negative, except where G(j) = 0, and for any sequence of the form G(n+1) = G(n) + G(n-1) with any initial values for G(0), G(1), including non-integer values. G(n) includes Lucas, Fibonacci. Compare with A081067 for odd number offsets from j. - Richard R. Forberg, Nov 16 2014
a(n) = [x^n] ( (1 + 3*x + sqrt(1 + 6*x + 5*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
From J. M. Bergot, Oct 28 2015: (Start)
For n>0, a(n) = F(n-1) * L(n) + F(2*n+1) - (-1)^n with F(k) = A000045(k).
For n>1, a(n) = F(n+1) * L(n) + F(2*n-1) - (-1)^n.
For n>2, a(n) = 5*F(2*n-3) + 2*L(n-3) * L(n) + 8*(-1)^n. (End)
For n>1, a(n) = L(n-2)*L(n+2) -7*(-1)^n. - J. M. Bergot, Feb 10 2016
a(n) = 6*F(n-1)*L(n-1) - F(2*n-6) with F(n)=A000045(n) and L(n)=A000032(n). - J. M. Bergot, Apr 21 2017
a(n) = F(2*n) + 2*F(n-1)*L(n) with F(n)=A000045(n) and L(n)=A000032(n). - J. M. Bergot, May 01 2017
E.g.f.: exp(4*x/(1+sqrt(5))^2) + exp((1/4)*(1+sqrt(5))^2*x). - Stefano Spezia, Aug 13 2019
From Peter Bala, Oct 14 2019: (Start)
a(n) = F(2*n+2) - F(2*n-2) = A001906(n+1) - A001906(n-1).
a(n) = trace(M^n), where M is the 2 X 2 matrix [0, 1; 1, 1]^2 = [1, 1; 1, 2].
Consequently the Gauss congruences hold: a(n*p^k) = a(n*p^(k-1)) ( mod p^k ) for all prime p and positive integers n and k. See Zarelua and also Stanley (Ch. 5, Ex. 5.2(a) and its solution).
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 1/a(n) ) = 1/5.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 3/(a(n) + 2/(a(n))) ) = 1/6.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 9/(a(n) + 4/(a(n) + 1/(a(n)))) ) = 1/9.
x*exp(Sum_{n >= 1} a(n)*x^/n) = x + 3*x^2 + 8*x^3 + 21*x^4 + ... is the o.g.f. for A001906. (End)
a(n) = n + 2 + Sum_{k=1..n-1} k*a(n-k). - Yu Xiao, May 30 2020
Sum_{n>=1} 1/a(n) = A153415. - Amiram Eldar, Nov 11 2020
Sum_{n>=0} 1/(a(n) + 3) = (2*sqrt(5) + 1)/10 (André-Jeannin, 1991). - Amiram Eldar, Jan 23 2022
a(n) = 2*cosh(2*n*arccsch(2)) = 2*cosh(2*n*asinh(1/2)). - Peter Luschny, May 25 2022
a(n) = (5/2)*(Sum_{k=-n..n} binomial(2*n, n+5*k)) - (1/2)*4^n. - Greg Dresden, Jan 05 2023
a(n) = Sum_{k>=0} Lucas(2*n*k)/(Lucas(2*n)^(k+1)). - Diego Rattaggi, Jan 12 2025

Extensions

Additional comments from Michael Somos, Jun 23 2001

A002212 Number of restricted hexagonal polyominoes with n cells.

Original entry on oeis.org

1, 1, 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369, 751236, 3328218, 14878455, 67030785, 304036170, 1387247580, 6363044315, 29323149825, 135700543190, 630375241380, 2938391049395, 13739779184085, 64430797069375, 302934667061301, 1427763630578197
Offset: 0

Views

Author

N. J. A. Sloane, Ronald C. Read

Keywords

Comments

Number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0) with no peaks at odd level. Example: a(2)=3 because we have UUDD, UHD and HH. - Emeric Deutsch, Dec 06 2003
Number of 3-Motzkin paths of length n-1 (i.e., lattice paths from (0,0) to (n-1,0) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0)). Example: a(4)=36 because we have 27 HHH paths, 3 HUD paths, 3 UHD paths and 3 UDH paths. - Emeric Deutsch, Jan 22 2004
Number of rooted, planar trees having edges weighted by strictly positive integers (multi-trees) with weight-sum n. - Roland Bacher, Feb 28 2005
Number of skew Dyck paths of semilength n. A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. - Emeric Deutsch, May 10 2007
Equivalently, number of self-avoiding paths of semilength n in the first quadrant beginning at the origin, staying weakly above the diagonal, ending on the diagonal, and consisting of steps r=(+1,0) (right), U=(0,+1) (up), and D=(0,-1) (down). Self-avoidance implies that factors UD and DU and steps D reaching the diagonal before the end are forbidden. The a(3) = 10 such paths are UrUrUr, UrUUrD, UrUUrr, UUrrUr, UUrUrD, UUrUrr, UUUDrD, UUUrDD, UUUrrD, and UUUrrr. - Joerg Arndt, Jan 15 2024
Hankel transform of [1,3,10,36,137,543,...] is A000012 = [1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
From Gary W. Adamson, May 17 2009: (Start)
Convolved with A026375, (1, 3, 11, 45, 195, ...) = A026378: (1, 4, 17, 75, ...)
(1, 3, 10, 36, 137, ...) convolved with A026375 = A026376: (1, 6, 30, 144, ...).
Starting (1, 3, 10, 36, ...) = INVERT transform of A007317: (1, 2, 5, 15, 51, ...). (End)
Binomial transform of A032357. - Philippe Deléham, Sep 17 2009
a(n) = number of rooted trees with n vertices in which each vertex has at most 2 children and in case a vertex has exactly one child, it is labeled left, middle or right. These are the hex trees of the Deutsch, Munarini, Rinaldi link. This interpretation yields the second MATHEMATICA recurrence below. - David Callan, Oct 14 2012
The left shift (1,3,10,36,...) of this sequence is the binomial transform of the left-shifted Catalan numbers (1,2,5,14,...). Example: 36 =1*14 + 3*5 + 3*2 + 1*1. - David Callan, Feb 01 2014
Number of Schroeder paths from (0,0) to (2n,0) with no level steps H=(2,0) at even level. Example: a(2)=3 because we have UUDD, UHD and UDUD. - José Luis Ramírez Ramírez, Apr 27 2015
This is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the Catalan sequence A000108. See a Feb 17 2017 comment in A097805. - Wolfdieter Lang, Feb 17 2017
a(n) is the number of parking functions of size n avoiding the patterns 132 and 231. - Lara Pudwell, Apr 10 2023

Examples

			G.f. = 1 + x + 3*x^2 + 10*x^3 + 36*x^4 + 137*x^5 + 543*x^6 + 2219*x^7 + 9285*x^8 + ...

References

  • J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298, Eq 14.
  • S. J. Cyvin, J. Brunvoll, G. Xiaofeng, and Z. Fuji, Number of perifusenes with one internal vertex, Rev. Roumaine Chem., 38(1) (1993), 65-78.
  • 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).

Links

Crossrefs

Cf. A025238, A000108, A001006, A007317, A026376, A026375.
First differences of A007317.
Row sums of triangle A104259.
Cf. A005572, A025230, A182401.

Programs

  • Magma
    I:= [1,3]; [1] cat [n le 2 select I[n]  else ((6*n-3)*Self(n-1)-5*(n-2)*Self(n-2)) div (n+1): n in [1..30]]; // Vincenzo Librandi, Jun 15 2015
  • Maple
    t1 := series(1+ (1-3*x-(1-x)^(1/2)*(1-5*x)^(1/2))/(2*x), x, 50):
A002212_list := len -> seq(coeff(t1,x,n),n=0..len): A002212_list(40);
a[0] := 1: a[1] := 1: for n from 2 to 50 do a[n] := (3*(2*n-1)*a[n-1]-5*(n-2)*a[n-2])/(n+1) od: print(convert(a,list)); # Zerinvary Lajos, Jan 01 2007
a := n -> `if`(n=0,1,simplify(GegenbauerC(n-1, -n, -3/2)/n)):
seq(a(n), n=0..23); # Peter Luschny, May 09 2016
  • Mathematica
    InverseSeries[Series[(y)/(1+3*y+y^2), {y, 0, 24}], x] (* then A(x)=1+y(x) *) (* Len Smiley, Apr 14 2000 *)
(* faster *)
a[0]=1;a[1]=1;
a[n_]/;n>=2 := a[n] = a[n-1] +  Sum[a[i]a[n-1-i],{i,0,n-1}];
Table[a[n],{n,0,14}] (* See COMMENTS above, [David Callan, Oct 14 2012] *)
(* fastest *)
s[0]=s[1]=1;
s[n_]/;n>=2 := s[n] = (3(2n-1)s[n-1]-5(n-2)s[n-2])/(n+1);
Table[s[n],{n,0,14 }] (* See Deutsch, Munarini, Rinaldi link, [David Callan, Oct 14 2012] *)
(* 2nd fastest *)
a[n_] := Hypergeometric2F1[3/2, 1-n, 3, -4]; a[0]=1; Table[a[n], {n, 0, 14}]  (* Jean-François Alcover, May 16 2013 *)
CoefficientList[Series[(1 - x - Sqrt[1 - 6x + 5x^2])/(2x), {x, 0, 20}], x] (* Nikolaos Pantelidis, Jan 30 2023 *)
  • Maxima
    makelist(sum(binomial(n,k)*binomial(n-k,k)*3^(n-2*k)/(k+1),k,0,n/2),n,0,24); /* for a(n+1) */ /* Emanuele Munarini, May 18 2011 */
  • PARI
    {a(n) = polcoeff( (1 - x - sqrt(1 - 6*x + 5*x^2 + x^2 * O(x^n))) / 2, n+1)};
  • PARI
    {a(n) = if( n<1, n==0, polcoeff( serreverse( x / (1 + 3*x + x^2) + x * O(x^n)), n))}; /* Michael Somos */
  • PARI
    my(N=66,x='x+O('x^N)); Vec((1 - x - sqrt(1-6*x+5*x^2))/(2*x)) \\ Joerg Arndt, Jan 13 2024
  • Sage
    def A002212():
    x, y, n = 1, 1, 1
    while True:
        yield x
        n += 1
        x, y = y, ((6*n - 3)*y - (5*n - 10)*x) / (n + 1)
a = A002212()
[next(a) for i in range(24)]  # Peter Luschny, Oct 12 2013

Formula

a(0)=1, for n > 0: a(n) = Sum_{j=0..n-1} Sum_{i=0..j} a(i)*a(j-i). G.f.: A(x) = 1 + x*A(x)^2/(1-x). - Mario Catalani (mario.catalani(AT)unito.it), Jun 19 2003
a(n) = Sum_{i=ceiling((n-1)/2)..n-1} (3^(2i+1-n)*binomial(n, i)*binomial(i, n-i-1))/n. - Emeric Deutsch, Jul 23 2002
a(n) = Sum_{k=1..n} binomial(2k, k)*binomial(n-1, k-1)/(k+1), i.e., binomial transform of the Catalan numbers 1, 2, 5, 14, 42, ... (A000108). a(n) = Sum_{k=0..floor((n-1)/2)} 3^(n-1-2*k)*binomial(2k, k)*binomial(n-1, 2k)/(k+1). - Emeric Deutsch, Aug 05 2002
D-finite with recurrence: a(1)=1, a(n) = (3(2n-1)*a(n-1)-5(n-2)*a(n-2))/(n+1) for n > 1. - Emeric Deutsch, Dec 18 2002
a(n) is asymptotic to c*5^n/n^(3/2) with c=0.63.... - Benoit Cloitre, Jun 23 2003
In closed form, c = (1/2)*sqrt(5/Pi) = 0.63078313050504... - Vaclav Kotesovec, Oct 04 2012
Reversion of Sum_{n>0} a(n)x^n = -Sum_{n>0} A001906(n)(-x)^n.
G.f. A(x) satisfies xA(x)^2 + (1-x)(1-A(x)) = 0.
G.f.: (1 - x - sqrt(1 - 6x + 5x^2))/(2x). For n > 1, a(n) = 3*a(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1). - John W. Layman, Feb 22 2001
The Hankel transform of this sequence gives A001519 = 1, 2, 5, 13, 34, 89, ... E.g., Det([1, 1, 3, 10, 36; 1, 3, 10, 36, 137; 3, 10, 36, 137, 543; 10, 36, 137, 543, 2219; 36, 137, 543, 2219, 9285 ])= 34. - Philippe Deléham, Jan 25 2004
a(m+n+1) = Sum_{k>=0} A091965(m, k)*A091965(n, k) = A091965(m+n, 0). - Philippe Deléham, Sep 14 2005
a(n+1) = Sum_{k=0..n} 2^(n-k)*M(k)*binomial(n,k), where M(k) = A001006(k) is the k-th Motzkin number (from here it follows that a(n+1) and M(n) have the same parity). - Emeric Deutsch, May 10 2007
a(n+1) = Sum_{k=0..n} A097610(n,k)*3^k. - Philippe Deléham, Oct 02 2007
G.f.: 1/(1-x/(1-x-x/(1-x/(1-x-x/(1-x/(1-x-x/(1-... (continued fraction). - Paul Barry, May 16 2009
G.f.: (1-x)/(1-2x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-.... (continued fraction). - Paul Barry, Oct 17 2009
G.f.: 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1-x) (continued fraction); more generally g.f. C(x/(1-x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011
a(n) = -5^(1/2)/(10*(n+1)) * (5*hypergeom([1/2, n], [1], 4/5) -3*hypergeom([1/2, n+1], [1], 4/5)) (for n>0). - Mark van Hoeij, Nov 12 2009
For n >= 1, a(n) = (1/(2*Pi))*Integral_{x=1..5} x^(n-1)*sqrt((x-1)*(5-x)) dx. - Groux Roland, Mar 16 2011
a(n+1) = [x^n](1-x^2)(1+3*x+x^2)^n. - Emanuele Munarini, May 18 2011
From Gary W. Adamson, Jul 21 2011: (Start)
a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows (with 3,2,2,2,... as the main diagonal):
3, 1, 0, 0, 0, 0, ...
1, 2, 1, 0, 0, 0, ...
1, 1, 2, 1, 0, 0, ...
1, 1, 1, 2, 1, 0, ...
1, 1, 1, 1, 2, 0, ...
...
Alternatively, let M = the previous matrix but change the 3 to a 2. Then a(n) = sum of top row terms of M^(n-1). (End)
a(n) = hypergeometric([1-n,3/2],[3],-4), for n>0. - Peter Luschny, Aug 15 2012
a(n) = GegenbauerC(n-1, -n, -3/2)/n for n >= 1. - Peter Luschny, May 09 2016
E.g.f.: 1 + Integral (exp(3*x) * BesselI(1,2*x) / x) dx. - Ilya Gutkovskiy, Jun 01 2020
G.f.: 1 + x/G(0) with G(k) = (1 - 3*x - x^2/G(k+1)) (continued fraction). - Nikolaos Pantelidis, Dec 12 2022
From Peter Bala, Feb 03 2024: (Start)
G.f.: 1 + x/(1 - x) * c(x/(1 - x))^2 = 1 + x/(1 - 5*x) * c(-x/(1 - 5*x))^2, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
a(n+1) = Sum_{k = 0..n} binomial(n, k)*Catalan(k+1).
a(n+1) = hypergeom([-n, 3/2], [3], -4).
a(n+1) = 5^n * Sum_{k = 0..n} (-5)^(-k)*binomial(n, k)*Catalan(k+1).
a(n+1) = 5^n * hypergeom([-n, 3/2], [3], 4/5). (End)

A001654 Golden rectangle numbers: F(n) * F(n+1), where F(n) = A000045(n) (Fibonacci numbers).

Original entry on oeis.org

0, 1, 2, 6, 15, 40, 104, 273, 714, 1870, 4895, 12816, 33552, 87841, 229970, 602070, 1576239, 4126648, 10803704, 28284465, 74049690, 193864606, 507544127, 1328767776, 3478759200, 9107509825, 23843770274, 62423800998, 163427632719, 427859097160, 1120149658760
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n)/A007598(n) ~= golden ratio, especially for larger n. - Robert Happelberg (roberthappelberg(AT)yahoo.com), Jul 25 2005
Let phi be the golden ratio (cf. A001622). Then 1/phi = phi - 1 = Sum_{n>=1} (-1)^(n-1)/a(n), an alternating infinite series consisting solely of unit fractions. - Franz Vrabec, Sep 14 2005
a(n+2) is the Hankel transform of A005807 aerated. - Paul Barry, Nov 04 2008
A more exact name would be: Golden convergents to rectangle numbers. These rectangles are not actually golden (ratio of sides is not phi) but are golden convergents (sides are numerator and denominator of convergents in the continued fraction expansion of phi, whence ratio of sides converges to phi). - Daniel Forgues, Nov 29 2009
The Kn4 sums (see A180662 for definition) of the "Races with Ties" triangle A035317 lead to this sequence. - Johannes W. Meijer, Jul 20 2011
Numbers m such that m(5m+2)+1 or m(5m-2)+1 is a square. - Bruno Berselli, Oct 22 2012
In pairs, these numbers are important in finding binomial coefficients that appear in at least six places in Pascal's triangle. For instance, the pair (m,n) = (40, 104) finds the numbers binomial(n-1,m) = binomial(n,m-1). Two additional numbers are found on the other side of the triangle. The final two numbers appear in row binomial(n-1,m). See A003015. - T. D. Noe, Mar 13 2013
For n>1, a(n) is one-half the area of the trapezoid created by the four points (F(n),L(n)), (L(n),F(n)), (F(n+1), L(n+1)), (L(n+1), F(n+1)) where F(n) = A000045(n) and L(n) = A000032(n). - J. M. Bergot, May 14 2014
[Note on how to calculate: take the two points (a,b) and (c,d) with a
a(n) = A067962(n-1) / A067962(n-2), n > 1. - Reinhard Zumkeller, Sep 24 2015
Can be obtained (up to signs) by setting x = F(n)/F(n+1) in g.f. for Fibonacci numbers - see Pongsriiam. - N. J. A. Sloane, Mar 23 2017

Examples

			G.f. = x + 2*x^2 + 6*x^3 + 15*x^4 + 40*x^5 + 104*x^6 + 273*x^7 + 714*x^8 + ...

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 9.
  • 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).

Links

Crossrefs

Cf. A001655, A001656, A001657, A001658, A010048, A067962.
Cf. A005968, A005969, A098531, A098532, A098533, A119283, A128697.
Cf. A000071, A079472, A080145, A239798, A290565.
Bisection of A006498, A070550, A080239.
First differences of A064831.
Partial sums of A007598.

Programs

  • Haskell
    a001654 n = a001654_list !! n
a001654_list = zipWith (*) (tail a000045_list) a000045_list
-- Reinhard Zumkeller, Jun 08 2013
  • Magma
    I:=[0,1,2]; [n le 3 select I[n] else 2*Self(n-1) + 2*Self(n-2) - Self(n-3): n in [1..30]]; // G. C. Greubel, Jan 17 2018
  • Maple
    with(combinat): A001654:=n->fibonacci(n)*fibonacci(n+1):
seq(A001654(n), n=0..28); # Zerinvary Lajos, Oct 07 2007
  • Mathematica
    LinearRecurrence[{2,2,-1}, {0,1,2}, 100] (* Vladimir Joseph Stephan Orlovsky, Jul 03 2011 *)
Times@@@Partition[Fibonacci[Range[0,30]],2,1] (* Harvey P. Dale, Aug 18 2011 *)
Accumulate[Fibonacci[Range[0, 30]]^2] (* Paolo Xausa, May 31 2024 *)
  • PARI
    A001654(n)=fibonacci(n)*fibonacci(n+1);
  • PARI
    b(n, k)=prod(j=1, k, fibonacci(n+j)/fibonacci(j));
vector(30, n, b(n-1, 2))  \\ Joerg Arndt, May 08 2016
  • Python
    from sympy import fibonacci as F
def a(n): return F(n)*F(n + 1)
[a(n) for n in range(101)] # Indranil Ghosh, Aug 03 2017
  • Python
    from math import prod
from gmpy2 import fib2
def A001654(n): return prod(fib2(n+1)) # Chai Wah Wu, May 19 2022

Formula

a(n) = A010048(n+1, 2) = Fibonomial(n+1, 2).
a(n) = A006498(2*n-1).
a(n) = a(n - 1) + A007598(n) = a(n - 1) + A000045(n)^2 = Sum_{j <= n} Fibonacci(j)^2. - Henry Bottomley, Feb 09 2001 [corrected by Ridouane Oudra, Apr 12 2025]
For n > 0, 1 - 1/a(n+1) = Sum_{k=1..n} 1/(F(k)*F(k+2)) where F(k) is the k-th Fibonacci number. - Benoit Cloitre, Aug 31 2002.
G.f.: x/(1-2*x-2*x^2+x^3) = x/((1+x)*(1-3*x+x^2)). (Simon Plouffe in his 1992 dissertation; see Comments to A055870),
a(n) = 3*a(n-1) - a(n-2) - (-1)^n = -a(-1-n).
Let M = the 3 X 3 matrix [1 2 1 / 1 1 0 / 1 0 0]; then a(n) = the center term in M^n *[1 0 0]. E.g., a(5) = 40 since M^5 * [1 0 0] = [64 40 25]. - Gary W. Adamson, Oct 10 2004
a(n) = Sum{k=0..n} Fibonacci(k)^2. The proof is easy. Start from a square (1*1). On the right side, draw another square (1*1). On the above side draw a square ((1+1)*(1+1)). On the left side, draw a square ((1+2)*(1+2)) and so on. You get a rectangle (F(n)*F(1+n)) which contains all the squares of side F(1), F(2), ..., F(n). - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 19 2007
With phi = (1+sqrt(5))/2, a(n) = round((phi^(2*n+1))/5) = floor((1/2) + (phi^(2*n+1))/5), n >= 0. - Daniel Forgues, Nov 29 2009
a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3), a(1)=1, a(2)=2, a(3)=6. - Sture Sjöstedt, Feb 06 2010
a(n) = (A002878(n) - (-1)^n)/5. - R. J. Mathar, Jul 22 2010
a(n) = 1/|F(n+1)/F(n) - F(n)/F(n-1)| where F(n) = Fibonacci numbers A000045. b(n) = F(n+1)/F(n) - F(n)/F(n-1): 1/1, -1/2, 1/6, -1/15, 1/40, -1/104, ...; c(n) = 1/b(n) = a(n)*(-1)^(n+1): 1, -2, 6, -15, 40, -104, ... (n=1,2,...). - Thomas Ordowski, Nov 04 2010
a(n) = (Fibonacci(n+2)^2 - Fibonacci(n-1)^2)/4. - Gary Detlefs, Dec 03 2010
Let d(n) = n mod 2, a(0)=0 and a(1)=1. For n > 1, a(n) = d(n) + 2*a(n-1) + Sum_{k=0..n-2} a(k). - L. Edson Jeffery, Mar 20 2011
From Tim Monahan, Jul 11 2011: (Start)
a(n+1) = ((2+sqrt(5))*((3+sqrt(5))/2)^n+(2-sqrt(5))*((3-sqrt(5))/2)^n+(-1)^n)/5.
a(n) = ((1+sqrt(5))*((3+sqrt(5))/2)^n+(1-sqrt(5))*((3-sqrt(5))/2)^n-2*(-1)^n)/10. (End)
From Wolfdieter Lang, Jul 21 2012: (Start)
a(n) = (2*A059840(n+2) - A027941(n))/3, n >= 0, with A059840(n+2) = Sum_{k=0..n} F(k)*F(k+2) and A027941(n) = A001519(n+1) - 1, n >= 0, where A001519(n+1) = F(2*n+1). (End)
a(n) = (-1)^n * Sum_{k=0..n} (-1)^k*F(2*k), n >= 0. - Wolfdieter Lang, Aug 11 2012
a(-1-n) = -a(n) for all n in Z. - Michael Somos, Sep 19 2014
0 = a(n)*(+a(n+1) - a(n+2)) + a(n+1)*(-2*a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Sep 19 2014
a(n) = (L(2*n+1) - (-1)^n)/5 with L(k) = A000032(k). - J. M. Bergot, Apr 15 2016
E.g.f.: ((3 + sqrt(5))*exp((5+sqrt(5))*x/2) - 2*exp((2*x)/(3+sqrt(5))+x) - 1 - sqrt(5))*exp(-x)/(5*(1 + sqrt(5))). - Ilya Gutkovskiy, Apr 15 2016
From Klaus Purath, Apr 24 2019: (Start)
a(n) = A061646(n) - Fibonacci(n-1)^2.
a(n) = (A061646(n+1) - A061646(n))/2. (End)
a(n) = A226205(n+1) + (-1)^(n+1). - Flávio V. Fernandes, Apr 23 2020
Sum_{n>=1} 1/a(n) = A290565. - Amiram Eldar, Oct 06 2020
Product_{n>=2} (1 + (-1)^n/a(n)) = phi^2/2 (A239798). - Amiram Eldar, Dec 02 2024
G.f.: x * exp( Sum_{k>=1} F(3*k)/F(k) * x^k/k ), where F(n) = A000045(n). - Seiichi Manyama, May 07 2025

Extensions

Extended by Wolfdieter Lang, Jun 27 2000

A002878 Bisection of Lucas sequence: a(n) = L(2*n+1).

Original entry on oeis.org

1, 4, 11, 29, 76, 199, 521, 1364, 3571, 9349, 24476, 64079, 167761, 439204, 1149851, 3010349, 7881196, 20633239, 54018521, 141422324, 370248451, 969323029, 2537720636, 6643838879, 17393796001, 45537549124, 119218851371, 312119004989, 817138163596, 2139295485799
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

In any generalized Fibonacci sequence {f(i)}, Sum_{i=0..4n+1} f(i) = a(n)*f(2n+2). - Lekraj Beedassy, Dec 31 2002
The continued fraction expansion for F((2n+1)*(k+1))/F((2n+1)*k), k>=1 is [a(n),a(n),...,a(n)] where there are exactly k elements (F(n) denotes the n-th Fibonacci number). E.g., continued fraction for F(12)/F(9) is [4, 4,4]. - Benoit Cloitre, Apr 10 2003
See A135064 for a possible connection with Galois groups of quintics.
Sequence of all positive integers k such that continued fraction [k,k,k,k,k,k,...] belongs to Q(sqrt(5)). - Thomas Baruchel, Sep 15 2003
All positive integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = -4 together with b(n)=A001519(n), n>=0.
a(n) = L(n,-3)*(-1)^n, where L is defined as in A108299; see also A001519 for L(n,+3).
Inverse binomial transform of A030191. - Philippe Deléham, Oct 04 2005
General recurrence is a(n) = (a(1)-1)*a(n-1) - a(n-2), a(1) >= 4, lim_{n->infinity} a(n) = x*(k*x+1)^n, k =(a(1)-3), x=(1+sqrt((a(1)+1)/(a(1)-3)))/2. Examples in OEIS: a(1)=4 gives A002878. a(1)=5 gives A001834. a(1)=6 gives A030221. a(1)=7 gives A002315. a(1)=8 gives A033890. a(1)=9 gives A057080. a(1)=10 gives A057081. - Ctibor O. Zizka, Sep 02 2008
Let r = (2n+1), then a(n), n>0 = Product_{k=1..floor((r-1)/2)} (1 + sin^2 k*Pi/r); e.g., a(3) = 29 = (3.4450418679...)*(4.801937735...)*(1.753020396...). - Gary W. Adamson, Nov 26 2008
a(n+1) is the Hankel transform of A001700(n)+A001700(n+1). - Paul Barry, Apr 21 2009
a(n) is equal to the permanent of the (2n) X (2n) tridiagonal matrix with sqrt(5)'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
Conjecture: for n > 0, a(n) = sqrt(Fibonacci(4*n+3) + Sum_{k=2..2*n} Fibonacci(2*k)). - Alex Ratushnyak, May 06 2012
Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... . - R. J. Mathar, Aug 10 2012
The continued fraction [a(n); a(n), a(n), ...] = phi^(2n+1), where phi is the golden ratio, A001622. - Thomas Ordowski, Jun 05 2013
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 5. - Michel Lagneau, Feb 01 2014
Conjecture: except for the number 3, a(n) are the numbers such that a(n)^2+2 are Lucas numbers. - Michel Lagneau, Jul 22 2014
Comment on the preceding conjecture: It is clear that all a(n) satisfy a(n)^2 + 2 = L(2*(2*n+1)) due to the identity (17 c) of Vajda, p. 177: L(2*n) + 2*(-1)^n = L(n)^2 (take n -> 2*n+1). - Wolfdieter Lang, Oct 10 2014
Limit_{n->oo} a(n+1)/a(n) = phi^2 = phi + 1 = (3+sqrt(5))/2. - Derek Orr, Jun 18 2015
If d[k] denotes the sequence of k-th differences of this sequence, then d[0](0), d[1](1), d[2](2), d[3](3), ... = A048876, cf. message to SeqFan list by P. Curtz on March 2, 2016. - M. F. Hasler, Mar 03 2016
a(n-1) and a(n) are the least phi-antipalindromic numbers (A178482) with 2*n and 2*n+1 digits in base phi, respectively. - Amiram Eldar, Jul 07 2021
Triangulate (hyperbolic) 2-space such that around every vertex exactly 7 triangles touch. Call any 7 triangles having a common vertex the first layer and let the (n+1)-st layer be all triangles that do not appear in any of the first n layers and have a common vertex with the n-th layer. Then the n-th layer contains 7*a(n-1) triangles. E.g., the first layer (by definition) contains 7 triangles, the second layer (the "ring" of triangles around the first layer) consists of 28 triangles, the third layer (the next "ring") consists of 77 triangles, and so on. - Nicolas Nagel, Aug 13 2022

Examples

			G.f. = 1 + 4*x + 11*x^2 + 29*x^3 + 76*x^4 + 199*x^5 + 521*x^6 + ... - _Michael Somos_, Jan 13 2019

References

  • J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p. 91.
  • 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).
  • Steven Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

Links

Crossrefs

Cf. A000204. a(n) = A060923(n, 0), a(n)^2 = A081071(n).
Cf. A005248 [L(2n) = bisection (even n) of Lucas sequence].
Cf. A001906 [F(2n) = bisection (even n) of Fibonacci sequence], A000045, A002315, A004146, A029907, A113224, A153387, A153416, A178482, A192425, A285992 (prime subsequence).
Cf. similar sequences of the type k*F(n)*F(n+1)+(-1)^n listed in A264080.

Programs

  • GAP
    List([0..40], n-> Lucas(1,-1,2*n+1)[2] ); # G. C. Greubel, Jul 15 2019
  • Haskell
    a002878 n = a002878_list !! n
a002878_list = zipWith (+) (tail a001906_list) a001906_list
-- Reinhard Zumkeller, Jan 11 2012
  • Magma
    [Lucas(2*n+1): n in [0..40]]; // Vincenzo Librandi, Apr 16 2011
  • Maple
    A002878 := proc(n)
    option remember;
    if n <= 1 then
        op(n+1,[1,4]);
    else
        3*procname(n-1)-procname(n-2) ;
    end if;
end proc: # R. J. Mathar, Apr 30 2017
  • Mathematica
    a[n_]:= FullSimplify[GoldenRatio^n - GoldenRatio^-n]; Table[a[n], {n, 1, 40, 2}]
a[1]=1; a[2]=4; a[n_]:=a[n]= 3a[n-1] -a[n-2]; Array[a, 40]
LinearRecurrence[{3, -1}, {1, 4}, 41] (* Jean-François Alcover, Sep 23 2017 *)
Table[Sum[(-1)^Floor[k/2] Binomial[n -Floor[(k+1)/2], Floor[k/2]] 3^(n - k), {k, 0, n}], {n, 0, 40}] (* L. Edson Jeffery, Feb 26 2018 *)
a[ n_] := Fibonacci[2n] + Fibonacci[2n+2]; (* Michael Somos, Jul 31 2018 *)
a[ n_]:= LucasL[2n+1]; (* Michael Somos, Jan 13 2019 *)
  • PARI
    a(n)=fibonacci(2*n)+fibonacci(2*n+2) \\ Charles R Greathouse IV, Jun 16 2011
  • PARI
    for(n=1,40,q=((1+sqrt(5))/2)^(2*n-1);print1(contfrac(q)[1],", ")) \\ Derek Orr, Jun 18 2015
  • PARI
    Vec((1+x)/(1-3*x+x^2) + O(x^40)) \\ Altug Alkan, Oct 26 2015
  • Python
    a002878 = [1, 4]
for n in range(30): a002878.append(3*a002878[-1] - a002878[-2])
print(a002878) # Gennady Eremin, Feb 05 2022
  • Sage
    [lucas_number2(2*n+1,1,-1) for n in (0..40)] # G. C. Greubel, Jul 15 2019

Formula

a(n+1) = 3*a(n) - a(n-1).
G.f.: (1+x)/(1-3*x+x^2). - Simon Plouffe in his 1992 dissertation
a(n) = S(2*n, sqrt(5)) = S(n, 3) + S(n-1, 3); S(n, x) := U(n, x/2), Chebyshev polynomials of 2nd kind, A049310. S(n, 3) = A001906(n+1) (even-indexed Fibonacci numbers).
a(n) ~ phi^(2*n+1). - Joe Keane (jgk(AT)jgk.org), May 15 2002
Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i); then (-1)^n*q(n, -1) = a(n). - Benoit Cloitre, Nov 10 2002
a(n) = A005248(n+1) - A005248(n) = -1 + Sum_{k=0..n} A005248(k). - Lekraj Beedassy, Dec 31 2002
a(n) = 2^(-n)*A082762(n) = 4^(-n)*Sum_{k>=0} binomial(2*n+1, 2*k)*5^k; see A091042. - Philippe Deléham, Mar 01 2004
a(n) = (-1)^n*Sum_{k=0..n} (-5)^k*binomial(n+k, n-k). - Benoit Cloitre, May 09 2004
From Paul Barry, May 27 2004: (Start)
Both bisection and binomial transform of A000204.
a(n) = Fibonacci(2n) + Fibonacci(2n+2). (End)
Sequence lists the numerators of sinh((2*n-1)*psi) where the denominators are 2; psi=log((1+sqrt(5))/2). Offset 1. a(3)=11. - Al Hakanson (hawkuu(AT)gmail.com), Mar 25 2009
a(n) = A001906(n) + A001906(n+1). - Reinhard Zumkeller, Jan 11 2012
a(n) = floor(phi^(2n+1)), where phi is the golden ratio, A001622. - Thomas Ordowski, Jun 10 2012
a(n) = A014217(2*n+1) = A014217(2*n+2) - A014217(2*n). - Paul Curtz, Jun 11 2013
Sum_{n >= 0} 1/(a(n) + 5/a(n)) = 1/2. Compare with A005248, A001906, A075796. - Peter Bala, Nov 29 2013
a(n) = lim_{m->infinity} Fibonacci(m)^(4n+1)*Fibonacci(m+2*n+1)/ Sum_{k=0..m} Fibonacci(k)^(4n+2). - Yalcin Aktar, Sep 02 2014
From Peter Bala, Mar 22 2015: (Start)
The aerated sequence (b(n))n>=1 = [1, 0, 4, 0, 11, 0, 29, 0, ...] is a fourth-order linear divisibility sequence; that is, if n | m then b(n) | b(m). It is the case P1 = 0, P2 = -1, Q = -1 of the 3-parameter family of divisibility sequences found by Williams and Guy.
b(n) = (1/2)*((-1)^n - 1)*F(n) + (1 + (-1)^(n-1))*F(n+1), where F(n) is a Fibonacci number. The o.g.f. is x*(1 + x^2)/(1 - 3*x^2 + x^4).
Exp( Sum_{n >= 1} 2*b(n)*x^n/n ) = 1 + Sum_{n >= 1} 2*F(n)*x^n.
Exp( Sum_{n >= 1} (-2)*b(n)*x^n/n ) = 1 + Sum_{n >= 1} 2*F(n)*(-x)^n.
Exp( Sum_{n >= 1} 4*b(n)*x^n/n ) = 1 + Sum_{n >= 1} 4*A029907(n)*x^n.
Exp( Sum_{n >= 1} (-4)*b(n)*x^n/n ) = 1 + Sum_{n >= 1} 4*A029907(n)*(-x)^n. Cf. A002315, A004146, A113224 and A192425. (End)
a(n) = sqrt(5*F(2*n+1)^2-4), where F(n) = A000045(n). - Derek Orr, Jun 18 2015
For n > 1, a(n) = 5*F(2*n-1) + L(2*n-3) with F(n) = A000045(n). - J. M. Bergot, Oct 25 2015
For n > 0, a(n) = L(n-1)*L(n+2) + 4*(-1)^n. - J. M. Bergot, Oct 25 2015
For n > 2, a(n) = a(n-2) + F(n+2)^2 + F(n-3)^2 = L(2*n-3) + F(n+2)^2 + F(n-3)^2. - J. M. Bergot, Feb 05 2016 and Feb 07 2016
E.g.f.: ((sqrt(5) - 5)*exp((3-sqrt(5))*x/2) + (5 + sqrt(5))*exp((3+sqrt(5))*x/2))/(2*sqrt(5)). - Ilya Gutkovskiy, Apr 24 2016
a(n) = Sum_{k=0..n} (-1)^floor(k/2)*binomial(n-floor((k+1)/2), floor(k/2))*3^(n-k). - L. Edson Jeffery, Feb 26 2018
a(n)*F(m+2n-1) = F(m+4n-2)-F(m), with Fibonacci number F(m), empirical observation. - Dan Weisz, Jul 30 2018
a(n) = -a(-1-n) for all n in Z. - Michael Somos, Jul 31 2018
Sum_{n>=0} 1/a(n) = A153416. - Amiram Eldar, Nov 11 2020
a(n) = Product_{k=1..n} (1 + 4*sin(2*k*Pi/(2*n+1))^2). - Seiichi Manyama, Apr 30 2021
Sum_{n>=0} (-1)^n/a(n) = (1/sqrt(5)) * A153387 (Carlitz, 1967). - Amiram Eldar, Feb 05 2022
The continued fraction [a(n);a(n),a(n),...] = phi^(2*n+1), with phi = A001622. - A.H.M. Smeets, Feb 25 2022
a(n) = 2*sinh((2*n + 1)*arccsch(2)). - Peter Luschny, May 25 2022
This gives the sequence with 2 1's prepended: b(1)=b(2)=1 and, for k >= 3, b(k) = Sum_{j=1..k-2} (2^(k-j-1) - 1)*b(j). - Neal Gersh Tolunsky, Oct 28 2022 (formula due to Jon E. Schoenfield)
For n > 0, a(n) = 1 + 1/(Sum_{k>=1} F(k)/phi^(2*n*k + k)). - Diego Rattaggi, Nov 08 2023
From Peter Bala, Apr 16 2025: (Start)
a(3*n+1) = a(n)^3 + 3*a(n).
a(5*n+2) = a(n)^5 + 5*a(n)^3 + 5*a(n).
a(7*n+3) = a(n)^7 + 7*a(n)^5 + 14*a(n)^3 + 7*a(n).
For the coefficients see A034807.
The general result is: for k >= 0, a(k*n + (k-1)/2) = 2 * T(k, a(n)/2), where T(k, x) denotes the k-th Chebyshev polynomial of the first kind and a(n) = ((1 + sqrt(5))/2)^(2*n+1) + ((1 - sqrt(5))/2)^(2*n+1).
Sum_{n >= 0} (-1)^n/a(n) = (1/4)* (theta_3(phi) - theta_3(phi^2)) = 0.815947983588122..., where theta_3(x) = 1 + 2*Sum_{n >= 1} x^(n^2) (see A000122) and phi = (sqrt(5) - 1)/2. See Borwein and Borwein, Exercise 3 a, p. 94 and Carlitz, 1967. (End)
From Peter Bala, May 15 2025: (Start)
Sum_{n >= 1} (-1)^(n+1)/(a(n) - 1/a(n)) = 1/5 (telescoping series: 5/(a(n) - 1/a(n)) = 1/A001906(n+1) + 1/A001906(n) ).
More generally, for k >= 1, Sum_{n >= 1} (-1)^(n+1)/(a(k*n) - s(k)/a(k*n)) = 1/(1 + a(k)) where s(k) = a(0) + a(1) + ... + a(k-1) = Lucas(2*k) - 2.
For k >= 1, Sum_{n >= 1} (-1)^(n+1)/(a(n) + L(2*k)^2/a(n)) = (1/5) * A064170(k+2).
Sum_{n >= 1} 1/(a(n) + 9/a(n)) = 3/10 (follows from 1/(a(n) + 9/a(n)) = L(2*n)/A081076(n) - L(2*n+2)/A081076(n+1) ).
More generally, it appears that for k >= 1, Sum_{n >= 1} 1/(a(n) + L(2*k)^2/a(n)) is rational.
Product_{n >= 1} (a(n) + 1)/(a(n) - 1) = sqrt(5) [telescoping product: Product_{k = 1..n} ((a(k) + 1)/(a(k) - 1))^2 = 5*(1 - 4/A240926(n+1)) ]. (End)

Extensions

Chebyshev and Pell comments from Wolfdieter Lang, Aug 31 2004

A007317 Binomial transform of Catalan numbers.

Original entry on oeis.org

1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, 223191, 974427, 4302645, 19181100, 86211885, 390248055, 1777495635, 8140539950, 37463689775, 173164232965, 803539474345, 3741930523740, 17481709707825, 81912506777200, 384847173838501, 1812610804416698
Offset: 1

Views

Author

N. J. A. Sloane, Mira Bernstein

Keywords

Comments

Partial sums of A002212 (the restricted hexagonal polyominoes with n cells). Number of Schroeder paths (i.e., consisting of steps U=(1,1),D=(1,-1),H=(2,0) and never going below the x-axis) from (0,0) to (2n-2,0), with no peaks at even level. Example: a(3)=5 because among the six Schroeder paths from (0,0) to (4,0) only UUDD has a peak at an even level. - Emeric Deutsch, Dec 06 2003
Number of binary trees of weight n where leaves have positive integer weights. Non-commutative Non-associative version of partitions of n. - Michael Somos, May 23 2005
Appears also as the number of Euler trees with total weight n (associated with even switching class of matrices of order 2n). - David Garber, Sep 19 2005
Number of symmetric hex trees with 2n-1 edges; also number of symmetric hex trees with 2n-2 edges. A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read reference). A hex tree is symmetric if it is identical with its reflection in a bisector through the root. - Emeric Deutsch, Dec 19 2006
The Hankel transform of [1, 2, 5, 15, 51, 188, ...] is [1, 1, 1, 1, 1, ...], see A000012 ; the Hankel transform of [2, 5, 15, 51, 188, 731, ...] is [2, 5, 13, 34, 89, ...], see A001519. - Philippe Deléham, Dec 19 2006
a(n) = number of 321-avoiding partitions of [n]. A partition is 321-avoiding if the permutation obtained from its canonical form (entries in each block listed in increasing order and blocks listed in increasing order of their first entries) is 321-avoiding. For example, the only partition of [5] that fails to be 321-avoiding is 15/24/3 because the entries 5,4,3 in the permutation 15243 form a 321 pattern. - David Callan, Jul 22 2008
The sequence 1,1,2,5,15,51,188,... has Hankel transform A001519. - Paul Barry, Jan 13 2009
From Gary W. Adamson, May 17 2009: (Start)
Equals INVERT transform of A033321: (1, 1, 2, 6, 21, 79, 311, ...).
Equals INVERTi transform of A002212: (1, 3, 10, 36, 137, ...).
Convolved with A026378, (1, 4, 17, 75, 339, ...) = A026376: (1, 6, 30, 144, ...)
(End)
a(n) is the number of vertices of the composihedron CK(n). The composihedra are a sequence of convex polytopes used to define maps of certain homotopy H-spaces. They are cellular quotients of the multiplihedra and cellular covers of the cubes. - Stefan Forcey (sforcey(AT)gmail.com), Dec 17 2009
a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps at level 0 come in 2 colors and those at a higher level come in 3 colors. Example: a(4)=15 because we have 2^3 = 8 paths of shape UHD, 2 paths of shape HUD, 2 paths of shape UDH, and 3 paths of shape UHD; here U=(1,1), H=(1,0), and D=(1,-1). - Emeric Deutsch, May 02 2011
REVERT transform of (1, 2, -3, 5, -8, 13, -21, 34, ... ) where the entries are Fibonacci numbers, A000045. Equivalently, coefficients in the series reversion of x(1-x)/(1+x-x^2). This means that the substitution of the gf (1-x-(1-6x+5x^2)^(1/2))/(2(1-x)) for x in x(1-x)/(1+x-x^2) will simplify to x. - David Callan, Nov 11 2012
The number of plane trees with nodes that have positive integer weights and whose total weight is n. - Brad R. Jones, Jun 12 2014
From Tom Copeland, Nov 02 2014: (Start)
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).
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)].
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).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).
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).
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].
(End)
Starting with offset 0, a(n) is also the number of Schröder paths of semilength n avoiding UH (an up step directly followed by a long horizontal step). Example: a(2)=5 because among the six possible Schröder paths of semilength 2 only UHD contains UH. - Valerie Roitner, Jul 23 2020

Examples

			a(3)=5 since {3, (1+2), (1+(1+1)), (2+1), ((1+1)+1)} are the five weighted binary trees of weight 3.
G.f. = x + 2*x^2 + 5*x^3 + 15*x^4 + 51*x^5 + 188*x^6 + 731*x^7 + 2950*x^8 + 12235*x^9 + ... _Michael Somos_, Jan 17 2018

References

  • J. Brunvoll et al., Studies of some chemically relevant polygonal systems: mono-q-polyhexes, ACH Models in Chem., 133 (3) (1996), 277-298, Eq. 15.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

See A181768 for another version. - N. J. A. Sloane, Nov 12 2010
First column of triangle A104259. Row sums of absolute values of A091699.
Number of vertices of multiplihedron A121988.
m-th binomial transform of the Catalan numbers: A126930 (m = -2), A005043 (m = -1), A000108 (m = 0), A064613 (m = 2), A104455 (m = 3), A104498 (m = 4) and A154623 (m = 5).
Cf. A055879, A033321, A026376, A026378, A059346, A000045, A000957, A057078, A091867, A104597, A249548, A162326.

Programs

  • Maple
    G := (1-sqrt(1-4*z/(1-z)))*1/2: Gser := series(G, z = 0, 30): seq(coeff(Gser, z, n), n = 1 .. 26); # Emeric Deutsch, Aug 12 2007
seq(round(evalf(JacobiP(n-1,1,-n-1/2,9)/n,99)),n=1..25); # Peter Luschny, Sep 23 2014
  • Mathematica
    Rest@ CoefficientList[ InverseSeries[ Series[(y - y^2)/(1 + y - y^2), {y, 0, 26}], x], x] (* then A(x)=y(x); note that InverseSeries[Series[y-y^2, {y, 0, 24}], x] produces A000108(x) *) (* Len Smiley, Apr 10 2000 *)
Range[0, 25]! CoefficientList[ Series[ Exp[ 3x] (BesselI[0, 2x] - BesselI[1, 2x]), {x, 0, 25}], x] (* Robert G. Wilson v, Apr 15 2011 *)
a[n_] := Sum[ Binomial[n, k]*CatalanNumber[k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 07 2012 *)
Rest[CoefficientList[Series[3/2 - (1/2) Sqrt[(1 - 5 x)/(1 - x)], {x, 0, 40}], x]] (* Vincenzo Librandi, Nov 03 2014 *)
Table[Hypergeometric2F1[1/2, -n+1, 2, -4], {n, 1, 30}] (* Vaclav Kotesovec, May 12 2022 *)
  • PARI
    {a(n) = my(A); if( n<2, n>0, A=vector(n); for(j=1,n, A[j] = 1 + sum(k=1,j-1, A[k]*A[j-k])); A[n])}; /* Michael Somos, May 23 2005 */
  • PARI
    {a(n) = if( n<1, 0, polcoeff( serreverse( (x - x^2) / (1 + x - x^2) + x * O(x^n)), n))}; /* Michael Somos, May 23 2005 */
  • PARI
    /* Offset = 0: */ {a(n)=local(A=1+x);for(i=1,n, A=sum(m=0,n, x^m*sum(k=0,m,A^k)+x*O(x^n))); polcoeff(A,n)} \\ Paul D. Hanna

Formula

(n+2)*a(n+2) = (6n+4)*a(n+1) - 5n*a(n).
G.f.: 3/2-(1/2)*sqrt((1-5*x)/(1-x)) [Gessel-Kim]. - N. J. A. Sloane, Jul 05 2014
G.f. for sequence doubled: (1/(2*x))*(1+x-(1-x)^(-1)*(1-x^2)^(1/2)*(1-5*x^2)^(1/2)).
a(n) = hypergeom([1/2, -n], [2], -4), n=0, 1, 2...; Integral representation as n-th moment of a positive function on a finite interval of the positive half-axis: a(n)=int(x^n*sqrt((5-x)/(x-1))/(2*Pi), x=1..5), n=0, 1, 2... This representation is unique. - Karol A. Penson, Sep 24 2001
a(1)=1, a(n)=1+sum(i=1, n-1, a(i)*a(n-i)). - Benoit Cloitre, Mar 16 2004
a(n) = Sum_{k=0..n} (-1)^k*3^(n-k)*binomial(n, k)*binomial(k, floor(k/2)) [offset 0]. - Paul Barry, Jan 27 2005
G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=x-(1-x)(y-y^2). - Michael Somos, May 23 2005
G.f. A(x) satisfies 0=f(x, A(x), A(A(x))) where f(x, y, z)=x(z-z^2)+(x-1)y^2 . - Michael Somos, May 23 2005
G.f. (for offset 0): (-1+x+(1-6*x+5*x^2)^(1/2))/(2*(-x+x^2)).
G.f. =z*c(z/(1-z))/(1-z) = 1/2 - (1/2)sqrt(1-4z/(1-z)), where c(z)=(1-sqrt(1-4z))/(2z) is the Catalan function (follows from Michael Somos' first comment). - Emeric Deutsch, Aug 12 2007
G.f.: 1/(1-2x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-3x-x^2/(1-.... (continued fraction). - Paul Barry, Apr 19 2009
a(n) = Sum_{k, 0<=k<=n} A091965(n,k)*(-1)^k. - Philippe Deléham, Nov 28 2009
E.g.f.: exp(3x)*(I_0(2x)-I_1(2x)), where I_k(x) is a modified Bessel function of the first kind. - Emanuele Munarini, Apr 15 2011
If we prefix sequence with an additional term a(0)=1, g.f. is (3-3*x-sqrt(1-6*x+5*x^2))/(2*(1-x)). [See Kim, 2011] - N. J. A. Sloane, May 13 2011
From Gary W. Adamson, Jul 21 2011: (Start)
a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows:
2, 1, 0, 0, 0, 0, ...
1, 2, 1, 0, 0, 0, ...
1, 1, 2, 1, 0, 0, ...
1, 1, 1, 2, 1, 0, ...
1, 1, 1, 1, 2, 1, ...
1, 1, 1, 1, 1, 2, ...
... (End)
G.f. satisfies: A(x) = Sum_{n>=0} x^n * (1 - A(x)^(n+1))/(1 - A(x)); offset=0. - Paul D. Hanna, Nov 07 2011
G.f.: 1/x - 1/x/Q(0), where Q(k)= 1 + (4*k+1)*x/((1-x)*(k+1) - x*(1-x)*(2*k+2)*(4*k+3)/(x*(8*k+6)+(2*k+3)*(1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
G.f.: (1-x - (1-5*x)*G(0))/(2*x*(1-x)), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1-x) - 2*x*(1-x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 25 2013
Asymptotics (for offset 0): a(n) ~ 5^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 28 2013
G.f.: G(0)/(1-x), where G(k) = 1 + (4*k+1)*x/((k+1)*(1-x) - 2*x*(1-x)*(k+1)*(4*k+3)/(2*x*(4*k+3) + (2*k+3)*(1-x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 29 2014
a(n) = JacobiP(n-1,1,-n-1/2,9)/n. - Peter Luschny, Sep 23 2014
0 = +a(n)*(+25*a(n+1) -50*a(n+2) +15*a(n+3)) +a(n+1)*(-10*a(n+1) +31*a(n+2) -14*a(n+3)) +a(n+2)*(+2*a(n+2) +a(n+3)) for all n in Z. - Michael Somos, Jan 17 2018
a(n+1) = (2/Pi) * Integral_{x = -1..1} (m + 4*x^2)^n*sqrt(1 - x^2) dx at m = 1. In general, the integral, qua sequence in n, gives the m-th binomial transform of the Catalan numbers. - Peter Bala, Jan 26 2020

A007598 Squared Fibonacci numbers: a(n) = F(n)^2 where F = A000045.

Original entry on oeis.org

0, 1, 1, 4, 9, 25, 64, 169, 441, 1156, 3025, 7921, 20736, 54289, 142129, 372100, 974169, 2550409, 6677056, 17480761, 45765225, 119814916, 313679521, 821223649, 2149991424, 5628750625, 14736260449, 38580030724, 101003831721, 264431464441, 692290561600
Offset: 0

Views

Author

N. J. A. Sloane, Robert G. Wilson v

Keywords

Comments

a(n)*(-1)^(n+1) = (2*(1-T(n,-3/2))/5), n>=0, with Chebyshev's polynomials T(n,x) of the first kind, is the r=-1 member of the r-family of sequences S_r(n) defined in A092184 where more information can be found. - Wolfdieter Lang, Oct 18 2004
From Giorgio Balzarotti, Mar 11 2009: (Start)
Determinant of power series with alternate signs of gamma matrix with determinant 1!.
a(n) = Determinant(A - A^2 + A^3 - A^4 + A^5 - ... - (-1)^n*A^n) where A is the submatrix A(1..2,1..2) of the matrix with factorial determinant.
A = [[1,1,1,1,1,1,...], [1,2,1,2,1,2,...], [1,2,3,1,2,3,...], [1,2,3,4,1,2,...], [1,2,3,4,5,1,...], [1,2,3,4,5,6,...], ...]; note: Determinant A(1..n,1..n) = (n-1)!.
a(n) is even with respect to signs of power of A.
See A158039...A158050 for sequence with matrix 2!, 3!, ... (End)
Equals the INVERT transform of (1, 3, 2, 2, 2, ...). Example: a(7) = 169 = (1, 1, 4, 9, 25, 64) dot (2, 2, 2, 2, 3, 1) = (2 + 2 + 8 + 18 + 75 + 64). - Gary W. Adamson, Apr 27 2009
This is a divisibility sequence.
a(n+1)*(-1)^n, n>=0, is the sequence of the alternating row sums of the Riordan triangle A158454. - Wolfdieter Lang, Dec 18 2010
a(n+1) is the number of tilings of a 2 X 2n rectangle with n tetrominoes of any shape, cf. A230031. - Alois P. Heinz, Nov 29 2013
This is the case P1 = 1, P2 = -6, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014
Differences between successive golden rectangle numbers A001654. - Jonathan Sondow, Nov 05 2015
a(n+1) is the number of 2 X n matrices that can be obtained from a 2 X n matrix by moving each element to an adjacent position, horizontally or vertically. This is because F(n+1) is the number of domino tilings of that matrix, therefore with a checkerboard coloring and two domino tilings we can move the black element of each domino of the first tiling to the white element of the same domino and similarly move the white element of each domino of the second tiling to the black element of the same domino. - Fabio Visonà, May 04 2022
In general, squaring the terms of a second-order linear recurrence with signature (c,d) will result in a third-order linear recurrence with signature (c^2+d,(c^2+d)*d,-d^3). - Gary Detlefs, Jan 05 2023

Examples

			G.f. = x + x^2 + 4*x^3 + 9*x^4 + 25*x^5 + 64*x^6 + 169*x^7 + 441*x^8 + ...

References

  • Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 8.
  • Ross Honsberger, Mathematical Gems III, M.A.A., 1985, p. 130.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Richard P. Stanley, Enumerative Combinatorics I, Example 4.7.14, p. 251.

Links

Crossrefs

Cf. A000032, A000045, A001254, A001622, A001654, A047946, A056570, A059260, A061646, A065885, A079291, A080097, A105393.
Bisection of A006498 and A074677. First differences of A001654.
Second row of array A103323.
Half of A175395.

Programs

  • GAP
    List([0..30], n -> Fibonacci(n)^2); # G. C. Greubel, Dec 10 2018
  • Haskell
    a007598 = (^ 2) . a000045  -- Reinhard Zumkeller, Sep 01 2013
  • Magma
    [Fibonacci(n)^2: n in [0..30]]; // Vincenzo Librandi, Apr 14 2011
  • Maple
    with(combinat): seq(fibonacci(n)^2, n=0..27); # Zerinvary Lajos, Sep 21 2007
  • Mathematica
    f[n_] := Fibonacci[n]^2; Array[f, 4!, 0] (* Vladimir Joseph Stephan Orlovsky, Oct 25 2009 *)
LinearRecurrence[{2,2,-1},{0,1,1},41] (* Harvey P. Dale, May 18 2011 *)
  • PARI
    {a(n) = fibonacci(n)^2};
  • PARI
    concat(0, Vec(x*(1-x)/((1+x)*(1-3*x+x^2)) + O(x^30))) \\ Altug Alkan, Nov 06 2015
  • Python
    from sympy import fibonacci
def A007598(n): return fibonacci(n)**2 # Chai Wah Wu, Apr 14 2025
  • Sage
    [(fibonacci(n))^2 for n in range(0, 28)]# Zerinvary Lajos, May 15 2009
  • Sage
    [fibonacci(n)^2 for n in range(30)] # G. C. Greubel, Dec 10 2018

Formula

G.f.: x*(1-x)/((1+x)*(1-3*x+x^2)).
a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3), n > 2. a(0)=0, a(1)=1, a(2)=1.
a(-n) = a(n) for all n in Z.
a(n) = A080097(n-2) + 1.
L.g.f.: 1/5*log((1+3*x+x^2)/(1-6*x+x^2)) = Sum_{n>=0} a(n)/n*x^n; special case of l.g.f. given in A079291. - Joerg Arndt, Apr 13 2011
a(0) = 0, a(1) = 1; a(n) = a(n-1) + Sum(a(n-i)) + k, 0 <= i < n where k = 1 when n is odd, or k = -1 when n is even. E.g., a(2) = 1 = 1 + (1 + 1 + 0) - 1, a(3) = 4 = 1 + (1 + 1 + 0) + 1, a(4) = 9 = 4 + (4 + 1 + 1 + 0) - 1, a(5) = 25 = 9 + (9 + 4 + 1 + 1 + 0) + 1. - Sadrul Habib Chowdhury (adil040(AT)yahoo.com), Mar 02 2004
a(n) = (2*Fibonacci(2*n+1) - Fibonacci(2*n) - 2*(-1)^n)/5. - Ralf Stephan, May 14 2004
a(n) = F(n-1)*F(n+1) - (-1)^n = A059929(n-1) - A033999(n).
Sum_{j=0..2*n} binomial(2*n,j)*a(j) = 5^(n-1)*A005248(n+1) for n >= 1 [P. Stanica]. Sum_{j=0..2*n+1} binomial(2*n+1,j)*a(j) = 5^n*A001519(n+1) [P. Stanica]. - R. J. Mathar, Oct 16 2006
a(n) = (A005248(n) - 2*(-1)^n)/5. - R. J. Mathar, Sep 12 2010
a(n) = (-1)^k*(Fibonacci(n+k)^2-Fibonacci(k)*Fibonacci(2*n+k)), for any k. - Gary Detlefs, Dec 13 2010
a(n) = 3*a(n-1) - a(n-2) + 2*(-1)^(n+1), n > 1. - Gary Detlefs, Dec 20 2010
a(n) = Fibonacci(2*n-2) + a(n-2). - Gary Detlefs, Dec 20 2010
a(n) = (Fibonacci(3*n) - 3*(-1)^n*Fibonacci(n))/(5*Fibonacci(n)), n > 0. - Gary Detlefs, Dec 20 2010
a(n) = (Fibonacci(n)*Fibonacci(n+4) - 3*Fibonacci(n)*Fibonacci(n+1))/2. - Gary Detlefs, Jan 17 2011
a(n) = (((3+sqrt(5))/2)^n + ((3-sqrt(5))/2)^n - 2*(-1)^n)/5; without leading zero we would have a(n) = ((3+sqrt(5))*((3+sqrt(5))/2)^n + (3-sqrt(5))*((3-sqrt(5))/2)^n + 4*(-1)^n)/10. - Tim Monahan, Jul 17 2011
E.g.f.: (exp((phi+1)*x) + exp((2-phi)*x) - 2*exp(-x))/5, with the golden section phi:=(1+sqrt(5))/2. From the Binet-de Moivre formula for F(n). - Wolfdieter Lang, Jan 13 2012
Starting with "1" = triangle A059260 * the Fibonacci sequence as a vector. - Gary W. Adamson, Mar 06 2012
a(0) = 0, a(1) = 1; a(n+1) = (a(n)^(1/2) + a(n-1)^(1/2))^2. - Thomas Ordowski, Jan 06 2013
a(n) + a(n-1) = A001519(n), n > 0. - R. J. Mathar, Mar 19 2014
From Peter Bala, Mar 31 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = 3/2 and beta = -1 and T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 3/2; 1, 1/2].
a(n) = U(n-1,i/2)*U(n-1,-i/2), where U(n,x) denotes the Chebyshev polynomial of the second kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)
a(n) = (F(n+2)*F(n+3) - L(n)*L(n+1))/3 for F = A000045 and L = A000032. - J. M. Bergot, Jun 02 2014
0 = a(n)*(+a(n) - 2*a(n+1) - 2*a(n+2)) + a(n+1)*(+a(n+1) - 2*a(n+2)) + a(n+2)*(+a(n+2)) for all n in Z. - Michael Somos, Jun 03 2014
(F(n)*b(n+2))^2 + (F(n+1)*b(n-1))^2 = F(2*n+1)^3 = A001519(n+1)^3, with b(n) = a(n) + 2*(-1)^n and F(n) = A000045(n) (see Bruckman link). - Michel Marcus, Jan 24 2015
a(n) = 1/4*( a(n-2) - a(n-1) - a(n+1) + a(n+2) ). The same recurrence holds for A001254. - Peter Bala, Aug 18 2015
a(n) = F(n)*F(n+1) - F(n-1)*F(n). - Jonathan Sondow, Nov 05 2015
For n>2, a(n) = F(n-2)*(3*F(n-1) + F(n-3)) + F(2*n-5). Also, for n>2 a(n)=2*F(n-3)*F(n) + F(2*n-3) -(2)*(-1)^n. - J. M. Bergot, Nov 05 2015
a(n) = (F(n+2)^2 + L(n+1)^2) - 2*F(n+2)*L(n+1). - J. M. Bergot, Nov 08 2015
a(n) = F(n+3)^2 - 4*F(n+1)*F(n+2). - J. M. Bergot, Mar 17 2016
a(n) = (F(n-2)*F(n+2) + F(n-1)*F(n+1))/2. - J. M. Bergot, May 25 2017
4*a(n) = L(n+1)*L(n-1) - F(n+2)*F(n-2), where L = A000032. - Bruno Berselli, Sep 27 2017
a(n) = F(n+k)*F(n-k) + (-1)^(n+k)*a(k), for every integer k >= 0. - Federico Provvedi, Dec 10 2018
From Peter Bala, Nov 19 2019: (Start)
Sum_{n >= 3} 1/(a(n) - 1/a(n)) = 4/9.
Sum_{n >= 3} (-1)^n/(a(n) - 1/a(n)) = (10 - 3*sqrt(5))/18.
Conjecture: Sum_{n >= 1, n != 2*k+1} 1/(a(n) + (-1)^n*a(2*k+1)) = 1/a(4*k+2) for k = 0,1,2,.... (End)
Sum_{n>=1} 1/a(n) = A105393. - Amiram Eldar, Oct 22 2020
Product_{n>=2} (1 + (-1)^n/a(n)) = phi (A001622) (Falcon, 2016, p. 189, eq. (3.1)). - Amiram Eldar, Dec 03 2024

A289780 p-INVERT of the positive integers (A000027), where p(S) = 1 - S - S^2.

Original entry on oeis.org

1, 4, 14, 47, 156, 517, 1714, 5684, 18851, 62520, 207349, 687676, 2280686, 7563923, 25085844, 83197513, 275925586, 915110636, 3034975799, 10065534960, 33382471801, 110713382644, 367182309614, 1217764693607, 4038731742156, 13394504020957, 44423039068114
Offset: 0

Views

Author

Clark Kimberling, Aug 10 2017

Keywords

Comments

Suppose s = (c(0), c(1), c(2), ...) is a sequence and p(S) is a polynomial. Let S(x) = c(0)*x + c(1)*x^2 + c(2)*x^3 + ... and T(x) = (-p(0) + 1/p(S(x)))/x. The p-INVERT of s is the sequence t(s) of coefficients in the Maclaurin series for T(x).
Taking p(S) = 1 - S gives the INVERT transform of s, so that p-INVERT is a generalization of the INVERT transform (e.g., A033453).
Guide to p-INVERT sequences using p(S) = 1 - S - S^2:
t(A000012) = t(1,1,1,1,1,1,1,...) = A001906
t(A000290) = t(1,4,9,16,25,36,...) = A289779
t(A000027) = t(1,2,3,4,5,6,7,8,...) = A289780
t(A000045) = t(1,2,3,5,8,13,21,...) = A289781
t(A000032) = t(2,1,3,4,7,11,14,...) = A289782
t(A000244) = t(1,3,9,27,81,243,...) = A289783
t(A000302) = t(1,4,16,64,256,...) = A289784
t(A000351) = t(1,5,25,125,625,...) = A289785
t(A005408) = t(1,3,5,7,9,11,13,...) = A289786
t(A005843) = t(2,4,6,8,10,12,14,...) = A289787
t(A016777) = t(1,4,7,10,13,16,...) = A289789
t(A016789) = t(2,5,8,11,14,17,...) = A289790
t(A008585) = t(3,6,9,12,15,18,...) = A289795
t(A000217) = t(1,3,6,10,15,21,...) = A289797
t(A000225) = t(1,3,7,15,31,63,...) = A289798
t(A000578) = t(1,8,27,64,625,...) = A289799
t(A000984) = t(1,2,6,20,70,252,...) = A289800
t(A000292) = t(1,4,10,20,35,56,...) = A289801
t(A002620) = t(1,2,4,6,9,12,16,...) = A289802
t(A001906) = t(1,3,8,21,55,144,...) = A289803
t(A001519) = t(1,1,2,5,13,34,...) = A289804
t(A103889) = t(2,1,4,3,6,5,8,7,,...) = A289805
t(A008619) = t(1,1,2,2,3,3,4,4,...) = A289806
t(A080513) = t(1,2,2,3,3,4,4,5,...) = A289807
t(A133622) = t(1,2,1,3,1,4,1,5,...) = A289809
t(A000108) = t(1,1,2,5,14,42,...) = A081696
t(A081696) = t(1,1,3,9,29,97,...) = A289810
t(A027656) = t(1,0,2,0,3,0,4,0,5...) = A289843
t(A175676) = t(1,0,0,2,0,0,3,0,...) = A289844
t(A079977) = t(1,0,1,0,2,0,3,...) = A289845
t(A059841) = t(1,0,1,0,1,0,1,...) = A289846
t(A000040) = t(2,3,5,7,11,13,...) = A289847
t(A008578) = t(1,2,3,5,7,11,13,...) = A289828
t(A000142) = t(1!, 2!, 3!, 4!, ...) = A289924
t(A000201) = t(1,3,4,6,8,9,11,...) = A289925
t(A001950) = t(2,5,7,10,13,15,...) = A289926
t(A014217) = t(1,2,4,6,11,17,29,...) = A289927
t(A000045*) = t(0,1,1,2,3,5,...) = A289975 (* indicates prepended 0's)
t(A000045*) = t(0,0,1,1,2,3,5,...) = A289976
t(A000045*) = t(0,0,0,1,1,2,3,5,...) = A289977
t(A290990*) = t(0,1,2,3,4,5,...) = A290990
t(A290990*) = t(0,0,1,2,3,4,5,...) = A290991
t(A290990*) = t(0,0,01,2,3,4,5,...) = A290992

Examples

			Example 1:  s = (1,2,3,4,5,6,...) = A000027 and p(S) = 1 - S.
S(x) = x + 2x^2 + 3x^3 + 4x^4 + ...
p(S(x)) = 1 - (x + 2x^2 + 3x^3 + 4x^4 + ... )
- p(0) + 1/p(S(x)) = -1 + 1 + x + 3x^2 + 8x^3 + 21x^4 + ...
T(x) = 1 + 3x + 8x^2 + 21x^3 + ...
t(s) = (1,3,8,21,...) = A001906.
***
Example 2:  s = (1,2,3,4,5,6,...) = A000027 and p(S) = 1 - S - S^2.
S(x) =  x + 2x^2 + 3x^3 + 4x^4 + ...
p(S(x)) = 1 - ( x + 2x^2 + 3x^3 + 4x^4 + ...) - ( x + 2x^2 + 3x^3 + 4x^4 + ...)^2
- p(0) + 1/p(S(x)) = -1 + 1 + x + 4x^2 + 14x^3 + 47x^4 + ...
T(x) = 1 + 4x + 14x^2 + 47x^3 + ...
t(s) = (1,4,14,47,...) = A289780.

Links

Crossrefs

Cf. A000027.

Programs

  • GAP
    P:=[1,4,14,47];; for n in [5..10^2] do P[n]:=5*P[n-1]-7*P[n-2]+5*P[n-3]-P[n-4]; od; P; # Muniru A Asiru, Sep 03 2017
  • Mathematica
    z = 60; s = x/(1 - x)^2; p = 1 - s - s^2;
Drop[CoefficientList[Series[s, {x, 0, z}], x], 1] (* A000027 *)
Drop[CoefficientList[Series[1/p, {x, 0, z}], x], 1] (* A289780 *)
  • PARI
    x='x+O('x^99); Vec((1-x+x^2)/(1-5*x+7*x^2-5*x^3+x^4)) \\ Altug Alkan, Aug 13 2017

Formula

G.f.: (1 - x + x^2)/(1 - 5 x + 7 x^2 - 5 x^3 + x^4).
a(n) = 5*a(n-1) - 7*a(n-2) + 5*a(n-3) - a(n-4).

A001835 a(n) = 4*a(n-1) - a(n-2), with a(0) = 1, a(1) = 1.

Original entry on oeis.org

1, 1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, 413403, 1542841, 5757961, 21489003, 80198051, 299303201, 1117014753, 4168755811, 15558008491, 58063278153, 216695104121, 808717138331, 3018173449203, 11263976658481, 42037733184721, 156886956080403, 585510091136891
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

See A079935 for another version.
Number of ways of packing a 3 X 2*(n-1) rectangle with dominoes. - David Singmaster.
Equivalently, number of perfect matchings of the P_3 X P_{2(n-1)} lattice graph. - Emeric Deutsch, Dec 28 2004
The terms of this sequence are the positive square roots of the indices of the octagonal numbers (A046184) - Nicholas S. Horne (nairon(AT)loa.com), Dec 13 1999
Terms are the solutions to: 3*x^2 - 2 is a square. - Benoit Cloitre, Apr 07 2002
Gives solutions x > 0 of the equation floor(x*r*floor(x/r)) == floor(x/r*floor(x*r)) where r = 1 + sqrt(3). - Benoit Cloitre, Feb 19 2004
a(n) = L(n-1,4), where L is defined as in A108299; see also A001834 for L(n,-4). - Reinhard Zumkeller, Jun 01 2005
Values x + y, where (x, y) solves for x^2 - 3*y^2 = 1, i.e., a(n) = A001075(n) + A001353(n). - Lekraj Beedassy, Jul 21 2006
Number of 01-avoiding words of length n on alphabet {0,1,2,3} which do not end in 0. (E.g., for n = 2 we have 02, 03, 11, 12, 13, 21, 22, 23, 31, 32, 33.) - Tanya Khovanova, Jan 10 2007
sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571) + ... - Gary W. Adamson, Dec 18 2007
The lower principal convergents to 3^(1/2), beginning with 1/1, 5/3, 19/11, 71/41, comprise a strictly increasing sequence; numerators = A001834, denominators = A001835. - Clark Kimberling, Aug 27 2008
From Gary W. Adamson, Jun 21 2009: (Start)
A001835 and A001353 = bisection of denominators of continued fraction [1, 2, 1, 2, 1, 2, ...]; i.e., bisection of A002530.
a(n) = determinant of an n*n tridiagonal matrix with 1's in the super- and subdiagonals and (3, 4, 4, 4, ...) as the main diagonal.
Also, the product of the eigenvalues of such matrices: a(n) = Product_{k=1..(n-1)/2)} (4 + 2*cos(2*k*Pi/n).
(End)
Let M = a triangle with the even-indexed Fibonacci numbers (1, 3, 8, 21, ...) in every column, and the leftmost column shifted up one row. a(n) starting (1, 3, 11, ...) = lim_{n->oo} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010
a(n+1) is the number of compositions of n when there are 3 types of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
For n >= 2, a(n) equals the permanent of the (2*n-2) X (2*n-2) tridiagonal matrix with sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
Primes in the sequence are apparently those in A096147. - R. J. Mathar, May 09 2013
Except for the first term, positive values of x (or y) satisfying x^2 - 4xy + y^2 + 2 = 0. - Colin Barker, Feb 04 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 14xy + y^2 + 32 = 0. - Colin Barker, Feb 10 2014
The (1,1) element of A^n where A = (1, 1, 1; 1, 2, 1; 1, 1, 2). - David Neil McGrath, Jul 23 2014
Yong Hao Ng has shown that for any n, a(n) is coprime with any member of A001834 and with any member of A001075. - René Gy, Feb 25 2018
a(n+1) is the number of spanning trees of the graph T_n, where T_n is a 2 X n grid with an additional vertex v adjacent to (1,1) and (2,1). - Kevin Long, May 04 2018
a(n)/A001353(n) is the resistance of an n-ladder graph whose edges are replaced by one-ohm resistors. The resistance in ohms is measured at two nodes at one end of the ladder. It approaches sqrt(3) - 1 for n -> oo. See A342568, A357113, and A357115 for related information. - Hugo Pfoertner, Sep 17 2022
a(n) is the number of ways to tile a 1 X (n-1) strip with three types of tiles: small isosceles right triangles (with small side length 1), 1 X 1 squares formed by joining two of those right triangles along the hypotenuse, and large isosceles right triangles (with large side length 2) formed by joining two of those right triangles along a short leg. As an example, here is one of the a(6)=571 ways to tile a 1 X 5 strip with these kinds of tiles:
____________
| / \ |\ /| |
|/_\|\/_||. - Greg Dresden and Arjun Datta, Jun 30 2023
From Klaus Purath, May 11 2024: (Start)
For any two consecutive terms (a(n), a(n+1)) = (x,y): x^2 - 4xy + y^2 = -2 = A028872(-1). In general, the following applies to all sequences (t) satisfying t(i) = 4t(i-1) - t(i-2) with t(0) = 1 and two consecutive terms (x,y): x^2 - 4xy + y^2 = A028872(t(1)-2). This includes and interprets the Feb 04 2014 comments here and on A001075 by Colin Barker and the Dec 12 2012 comment on A001353 by Max Alekseyev. By analogy to this, for three consecutive terms (x,y,z) y^2 - xz = A028872(t(1)-2). This includes and interprets the Jul 10 2021 comment on A001353 by Bernd Mulansky.
If (t) is a sequence satisfying t(k) = 3t(k-1) + 3t(k-2) - t(k-3) or t(k) = 4t(k-1) - t(k-2) without regard to initial values and including this sequence itself, then a(n) = (t(k+2n+1) + t(k))/(t(k+n+1) + t(k+n)) always applies, as long as t(k+n+1) + t(k+n) != 0 for integer k and n >= 1. (End)
Binomial transform of 1, 0, 2, 4, 12, ... (A028860 without the initial -1) and reverse binomial transform of 1, 2, 6, 24, 108, ... (A094433 without the initial 1). - Klaus Purath, Sep 09 2024

References

  • Julio R. Bastida, Quadratic properties of a linearly recurrent sequence. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 163-166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009).
  • Leonhard Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 375.
  • F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.
  • Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
  • 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. P. Stanley, Enumerative Combinatorics I, p. 292.

Links

Crossrefs

Row 3 of array A099390.
Essentially the same as A079935.
First differences of A001353.
Partial sums of A052530.
Pairwise sums of A006253.
Bisection of A002530, A005246 and A048788.
First column of array A103997.
Cf. A001519, A003699, A082841, A101265, A125077, A001353, A001542, A096147 (subsequence of primes).

Programs

  • GAP
    a:=[1,1];; for n in [3..20] do a[n]:=4*a[n-1]-a[n-2]; od; a; # G. C. Greubel, Dec 23 2019
  • Haskell
    a001835 n = a001835_list !! n
a001835_list =
   1 : 1 : zipWith (-) (map (4 *) $ tail a001835_list) a001835_list
-- Reinhard Zumkeller, Aug 14 2011
  • Magma
    [n le 2 select 1 else 4*Self(n-1)-Self(n-2): n in [1..25]]; // Vincenzo Librandi, Sep 16 2016
  • Maple
    f:=n->((3+sqrt(3))^(2*n-1)+(3-sqrt(3))^(2*n-1))/6^n; [seq(simplify(expand(f(n))),n=0..20)]; # N. J. A. Sloane, Nov 10 2009
  • Mathematica
    CoefficientList[Series[(1-3x)/(1-4x+x^2), {x, 0, 24}], x] (* Jean-François Alcover, Jul 25 2011, after g.f. *)
LinearRecurrence[{4,-1},{1,1},30] (* Harvey P. Dale, Jun 08 2013 *)
Table[Round@Fibonacci[2n-1, Sqrt[2]], {n, 0, 20}] (* Vladimir Reshetnikov, Sep 15 2016 *)
Table[(3*ChebyshevT[n, 2] - ChebyshevU[n, 2])/2, {n, 0, 20}] (* G. C. Greubel, Dec 23 2019 *)
  • PARI
    {a(n) = real( (2 + quadgen(12))^n * (1 - 1 / quadgen(12)) )} /* Michael Somos, Sep 19 2008 */
  • PARI
    {a(n) = subst( (polchebyshev(n) + polchebyshev(n-1)) / 3, x, 2)} /* Michael Somos, Sep 19 2008 */
  • Sage
    [lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in range(25)] # Zerinvary Lajos, Apr 29 2009
  • Sage
    [(3*chebyshev_T(n,2) - chebyshev_U(n,2))/2 for n in (0..20)] # G. C. Greubel, Dec 23 2019

Formula

G.f.: (1 - 3*x)/(1 - 4*x + x^2). - Simon Plouffe in his 1992 dissertation
a(1-n) = a(n).
a(n) = ((3 + sqrt(3))^(2*n - 1) + (3 - sqrt(3))^(2*n - 1))/6^n. - Dean Hickerson, Dec 01 2002
a(n) = (8 + a(n-1)*a(n-2))/a(n-3). - Michael Somos, Aug 01 2001
a(n+1) = Sum_{k=0..n} 2^k * binomial(n + k, n - k), n >= 0. - Len Smiley, Dec 09 2001
Limit_{n->oo} a(n)/a(n-1) = 2 + sqrt(3). - Gregory V. Richardson, Oct 10 2002
a(n) = 2*A061278(n-1) + 1 for n > 0. - Bruce Corrigan (scentman(AT)myfamily.com), Nov 04 2002
Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n - i, i); then q(n, 2) = a(n+1). - Benoit Cloitre, Nov 10 2002
a(n+1) = Sum_{k=0..n} ((-1)^k)*((2*n+1)/(2*n + 1 - k))*binomial(2*n + 1 - k, k)*6^(n - k) (from standard T(n,x)/x, n >= 1, Chebyshev sum formula). The Smiley and Cloitre sum representation is that of the S(2*n, i*sqrt(2))*(-1)^n Chebyshev polynomial. - Wolfdieter Lang, Nov 29 2002
a(n) = S(n-1, 4) - S(n-2, 4) = T(2*n-1, sqrt(3/2))/sqrt(3/2) = S(2*(n-1), i*sqrt(2))*(-1)^(n - 1), with S(n, x) := U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first, kind. See A049310 and A053120. S(-1, x) = 0, S(-2, x) = -1, S(n, 4) = A001353(n+1), T(-1, x) = x.
a(n+1) = sqrt((A001834(n)^2 + 2)/3), n >= 0 (see Cloitre comment).
Sequence satisfies -2 = f(a(n), a(n+1)) where f(u, v) = u^2 + v^2 - 4*u*v. - Michael Somos, Sep 19 2008
a(n) = (1/6)*(3*(2 - sqrt(3))^n + sqrt(3)*(2 - sqrt(3))^n + 3*(2 + sqrt(3))^n - sqrt(3)*(2 + sqrt(3))^n) (Mathematica's solution to the recurrence relation). - Sarah-Marie Belcastro, Jul 04 2009
If p[1] = 3, p[i] = 2, (i > 1), 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+1) = det A. - Milan Janjic, Apr 29 2010
a(n) = (a(n-1)^2 + 2)/a(n-2). - Irene Sermon, Oct 28 2013
a(n) = A001353(n+1) - 3*A001353(n). - R. J. Mathar, Oct 30 2015
a(n) = a(n-1) + 2*A001353(n-1). - Kevin Long, May 04 2018
From Franck Maminirina Ramaharo, Nov 11 2018: (Start)
a(n) = (-1)^n*(A125905(n) + 3*A125905(n-1)), n > 0.
E.g.f.: exp^(2*x)*(3*cosh(sqrt(3)*x) - sqrt(3)*sinh(sqrt(3)*x))/3. (End)
From Peter Bala, Feb 12 2024: (Start)
For n in Z, a(n) = A001353(n) + A001353(1-n).
For n, j, k in Z, a(n)*a(n+j+k) - a(n+j)*a(n+k) = 2*A001353(j)*A001353(k). The case j = 1, k = 2 is given above. (End)
Previous Showing 21-30 of 349 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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