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

%I #35 Sep 08 2022 08:45:13

%S 1,5,14,33,72,151,310,629,1268,2547,5106,10225,20464,40943,81902,

%T 163821,327660,655339,1310698,2621417,5242856,10485735,20971494,

%U 41943013,83886052,167772131,335544290,671088609,1342177248,2684354527

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

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

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

%C 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

%H Harry J. Smith, <a href="/A094002/b094002.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).

%F 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)}.

%F a(n) = 5*2^n - n - 4 = 2*a(n-1) + n + 2 = A000247(n) + A000079(n). - _Henry Bottomley_, Oct 25 2004

%F From _Colin Barker_, Apr 23 2012: (Start)

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

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

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

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

%t LinearRecurrence[{4,-5,2},{1,5,14},40] (* _Harvey P. Dale_, Jan 20 2021 *)

%o (PARI) vector(35, n, 5*2^(n-1) -(n+3)) \\ _Harry J. Smith_, Jun 16 2009; edited Dec 27 2021

%o (Magma) [5*2^n -(n+4): n in [0..35]]; // _G. C. Greubel_, Dec 27 2021

%o (Sage) [5*2^n -(n+4) for n in (0..35)] # _G. C. Greubel_, Dec 27 2021

%Y Cf. A000079, A000247, A095149, A095151.

%K nonn,easy

%O 0,2

%A _Gary W. Adamson_, May 30 2004

%E More terms from _Robert G. Wilson v_, Jun 01 2004