A094002 a(n+3) = 3*a(n+2) - 2*a(n+1) + 1 with a(0)=1, a(1)=5.

1, 5, 14, 33, 72, 151, 310, 629, 1268, 2547, 5106, 10225, 20464, 40943, 81902, 163821, 327660, 655339, 1310698, 2621417, 5242856, 10485735, 20971494, 41943013, 83886052, 167772131, 335544290, 671088609, 1342177248, 2684354527

Offset: 0

Author

Gary W. Adamson, May 30 2004

Keywords

• nonn
• easy

Comments

A sequence generated from the Bell difference row triangle (as a matrix).

Companion sequence A095151 has the same recursion rule but is generated from the multiplier [1 0 0] instead of [1 1 1].

a(n) is the sum of the terms in row n of a triangle with first column T(n,0) = (n+1)*(n+2)/2 and diagonal T(n,n) = n+1; T(i,j) = T(i-1,j-1) + T(i-1,j). - J. M. Bergot, Jun 26 2018

Examples

			a(9) = 2547 = 3*a(8) - 2*a(7) + 1 = 3*1268 - 2*629 + 1 = 3804 - 1258 + 1.
		

Links

• Harry J. Smith, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

Cf. A000079, A000247, A095149, A095151.

Programs

Magma

[5*2^n -(n+4): n in [0..35]]; // G. C. Greubel, Dec 27 2021

Mathematica

a[n_]:= (MatrixPower[{{1,0,0}, {1,1,0}, {2,1,2}}, n].{{1}, {1}, {1}})[[3, 1]]; Table[a[n], {n, 35}] (* Robert G. Wilson v, Jun 01 2004 *)
LinearRecurrence[{4,-5,2},{1,5,14},40] (* Harvey P. Dale, Jan 20 2021 *)

PARI

vector(35, n, 5*2^(n-1) -(n+3)) \\ Harry J. Smith, Jun 16 2009; edited Dec 27 2021

Sage

[5*2^n -(n+4) for n in (0..35)] # G. C. Greubel, Dec 27 2021

Formula

Let M = a 3 X 3 matrix formed from A095149 rows (fill in with zeros): {1, 0, 0 ; 1, 1, 0 ; 2, 1, 2}. Then M^n * {1, 1, 1} = {1, n+1, a(n)}.

a(n) = 5*2^n - n - 4 = 2*a(n-1) + n + 2 = A000247(n) + A000079(n). - Henry Bottomley, Oct 25 2004

From Colin Barker, Apr 23 2012: (Start)

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

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

Extensions

More terms from Robert G. Wilson v, Jun 01 2004