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

Author

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

Keywords

• easy
• nonn

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).

Crossrefs

Cf. A007482 (inverse binomial transform).

Programs

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

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

Magma

R:=PowerSeriesRing(Integers(), 25); Coefficients(R!((1-x)/(1-5*x+2*x^2))); // Marius A. Burtea, Oct 16 2019

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 *)

PARI

Vec((1-x)/(1-5*x+2*x^2) + O(x^30)) \\ Michel Marcus, Mar 05 2015

Sage

def A052913_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1-5*x+2*x^2)).list()
A052913_list(30) # G. C. Greubel, Oct 16 2019

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

Extensions

Typo in definition corrected by Bruno Berselli, Jun 07 2010