A192967 Constant term of the reduction by x^2 -> x+1 of the polynomial p(n,x) defined at Comments.

1, 0, 2, 4, 9, 17, 31, 54, 92, 154, 255, 419, 685, 1116, 1814, 2944, 4773, 7733, 12523, 20274, 32816, 53110, 85947, 139079, 225049, 364152, 589226, 953404, 1542657, 2496089, 4038775, 6534894, 10573700, 17108626, 27682359, 44791019, 72473413, 117264468

Offset

0,3

Comments

The titular polynomials are defined recursively: p(n,x) = x*p(n-1,x) + n(n-1)/2, with p(0,x)=1. For an introduction to reductions of polynomials by substitutions such as x^2->x+1, see A192232 and A192744.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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

Formula

a(0)=1, a(1)=0, for n > 1, a(n) = a(n-1) + a(n-2) + n - 1. - Alex Ratushnyak, May 10 2012

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

G.f.: (1 -3*x +4*x^2 -x^3)/((1-x-x^2)*(1-x)^2). - R. J. Mathar, May 11 2014

a(n) = 3*Fibonacci(n+1) - n - 2. - G. C. Greubel, Jul 11 2019

Mathematica

q = x^2; s = x + 1; z = 40;
p[0, x]:= 1;
p[n_, x_]:= x*p[n-1, x] + n*(n-1)/2;
Table[Expand[p[n, x]], {n, 0, 7}]
reduce[{p1_, q_, s_, x_}]:= FixedPoint[(s PolynomialQuotient @@ #1 + PolynomialRemainder @@ #1 &)[{#1, q, x}] &, p1]
t = Table[reduce[{p[n, x], q, s, x}], {n, 0, z}];
u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}] (* A192967 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}] (* A192968 *)
LinearRecurrence[{3, -2, -1, 1}, {1, 0, 2, 4}, 41] (* Vladimir Joseph Stephan Orlovsky, Feb 15 2012 *)
Table[3*Fibonacci[n+1] -n-2, {n, 0, 40}] (* G. C. Greubel, Jul 11 2019 *)

Prog

(Magma) I:=[1, 0, 2, 4]; [n le 4 select I[n] else 3*Self(n-1)-2*Self(n-2)-Self(n-3)+Self(n-4): n in [1..40]]; // Vincenzo Librandi, Feb 20 2012
(Magma) [3*Fibonacci(n+1) -n-2: n in [0..40]]; // G. C. Greubel, Jul 11 2019
(PARI) vector(40, n, n--; f=fibonacci; 3*f(n+1)-n-2) \\ G. C. Greubel, Jul 11 2019
(Sage) [3*fibonacci(n+1) -n-2 for n in (0..40)] # G. C. Greubel, Jul 11 2019
(GAP) List([0..40], n-> 3*Fibonacci(n+1) -n-2); # G. C. Greubel, Jul 11 2019

Crossrefs

Cf. A000045, A192232, A192744, A192951.

Sequence in context: A136379 A065026 A199205 * A182806 A302832 A007502

Adjacent sequences: A192964 A192965 A192966 * A192968 A192969 A192970

Keyword

nonn,easy

Author

Clark Kimberling, Jul 13 2011

Status

approved