A052913 a(n+2) = 5*a(n+1) - 2*a(n), with a(0) = 1, a(1) = 4.

1, 4, 18, 82, 374, 1706, 7782, 35498, 161926, 738634, 3369318, 15369322, 70107974, 319801226, 1458790182, 6654348458, 30354161926, 138462112714, 631602239718, 2881086973162, 13142230386374, 59948977985546, 273460429154982, 1247404189803818, 5690100090709126

Offset

0,2

Comments

Main diagonal of the array: m(1,j)=3^(j-1), m(i,1)=1; m(i,j) = m(i-1,j) + m(i,j-1): 1 3 9 27 81 ... / 1 4 13 40 ... / 1 5 18 58 ... / 1 6 24 82 ... - Benoit Cloitre, Aug 05 2002

a(n) is also the number of 3 X n matrices of integers for which the upper-left hand corner is a 1, the rows and columns are weakly increasing, and two adjacent entries differ by at most 1. - Richard Stanley, Jun 06 2010

a(n) is the number of compositions of n when there are 4 types of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010

If a Stern's sequence based enumeration system of positive irreducible fractions is considered (for example, A007305/A047679, or A162909/A162910, or A071766/A229742, or A245325/A245326, ...), and if it is organized by blocks or levels (n) with 2^n terms (n>=0), and the products numerator*denominator, term by term, are summed at each level n, then the resulting sequence of integers is a(n). - Yosu Yurramendi, May 23 2015

Number of 1’s in the substitution system {0 -> 110, 1 -> 11110} at step n from initial string "1" (1 -> 11110 -> 11110111101111011110110 -> ...) . - Ilya Gutkovskiy, Apr 10 2017

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 894

J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.

Index entries for linear recurrences with constant coefficients, signature (5,-2).

Formula

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

a(n) = Sum_{alpha=RootOf(1 - 5*z + 2*z^2)} (1/17)*(3+alpha)*alpha^(-1-n).

a(n) = ((17+3*sqrt(17))/34)*((5+sqrt(17))/2)^n + ((17-3*sqrt(17))/34)*((5-sqrt(17))/2)^n. - N. J. A. Sloane, Jun 03 2002

a(n) = A107839(n) - A107839(n-1). - R. J. Mathar, May 21 2015

a(n) = 2*A020698(n-1), n>1. - R. J. Mathar, Nov 23 2015

E.g.f.: (1/17)*exp(5*x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2)). - Stefano Spezia, Oct 16 2019

a(n) = 3*A107839(n-1) + (-1)^n*A152594(n) with A107839(-1) = 0. - Klaus Purath, Jul 29 2020

Maple

spec := [S, {S=Sequence(Union(Prod(Sequence(Z), Union(Z, Z)), Z, Z))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
seq(coeff(series((1-x)/(1-5*x+2*x^2), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 16 2019

Mathematica

Transpose[NestList[{Last[#], 5Last[#]-2First[#]}&, {1, 4}, 20]][[1]] (* Harvey P. Dale, Mar 12 2011 *)
LinearRecurrence[{5, -2}, {1, 4}, 25] (* Jean-François Alcover, Jan 08 2019 *)

Prog

(PARI) Vec((1-x)/(1-5*x+2*x^2) + O(x^30)) \\ Michel Marcus, Mar 05 2015
(Magma) I:=[1, 4]; [n le 2 select I[n] else 5*Self(n-1)-2*Self(n-2): n in [1..35]]; // Vincenzo Librandi, May 24 2015
(Sage)
def A052913_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1-5*x+2*x^2)).list()
A052913_list(30) # G. C. Greubel, Oct 16 2019
(GAP) a:=[1, 4];; for n in [3..30] do a[n]:=5*a[n-1]-2*a[n-2]; od; a; # G. C. Greubel, Oct 16 2019
(Magma) R<x>:=PowerSeriesRing(Integers(), 25); Coefficients(R!((1-x)/(1-5*x+2*x^2))); // Marius A. Burtea, Oct 16 2019

Crossrefs

Cf. A007482 (inverse binomial transform).

Sequence in context: A194460 A356289 A100192 * A279285 A129160 A187077

Adjacent sequences: A052910 A052911 A052912 * A052914 A052915 A052916

Keyword

easy,nonn

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Extensions

Typo in definition corrected by Bruno Berselli, Jun 07 2010

Status

approved