A192878 Constant term in the reduction by (x^2 -> x + 1) of the polynomial p(n,x) given in Comments.

3, 0, 4, 5, 18, 42, 115, 296, 780, 2037, 5338, 13970, 36579, 95760, 250708, 656357, 1718370, 4498746, 11777875, 30834872, 80726748, 211345365, 553309354, 1448582690, 3792438723, 9928733472, 25993761700, 68052551621, 178163893170, 466439127882, 1221153490483

Offset

0,1

Comments

The polynomial p(n,x) is defined by p(0,x) = 1, p(1,x) = x + 1, and p(n,x) = x*p(n-1,x) + 2*(x^2)*p(n-1,x) + 1. See A192872.

For n>0, also the coefficient of x in the reduction x^2 -> x + 1 of the polynomial A000285(n-1)*x^(n-1). - R. J. Mathar, Jul 12 2011

Links

Colin Barker, Table of n, a(n) for n = 0..1000

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

Formula

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

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

a(n) = (2^(-n)*(7*(-2)^n - (-4+sqrt(5))*(3+sqrt(5))^n + (3-sqrt(5))^n*(4+sqrt(5))))/5. - Colin Barker, Sep 29 2016

Example

The first six polynomials and reductions:
p(0,x) = 3 -> 3
p(1,x) = x -> x
p(2,x) = 4*x^2 -> 4 + 4*x
p(3,x) = 5*x^3 -> 5 + 10*x
p(4,x) = 9*x^4 -> 18 + 27*x
p(5,x) = 14*x^5 -> 42 + 27*x
In general, p(n,x) = A104449(n)*x^n -> A192878(n) + A192879(n)*x.

Mathematica

q = x^2; s = x + 1; z = 25;
p[0, x_] := 3; p[1, x_] := x;
p[n_, x_] := p[n - 1, x]*x + p[n - 2, x]*x^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}]  (* A192878 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]  (* A192879 *)
FindLinearRecurrence[u1]
FindLinearRecurrence[u2]
LinearRecurrence[{2, 2, -1}, {3, 0, 4}, 30] (* G. C. Greubel, Jan 08 2019 *)

Prog

(PARI) a(n) = round((2^(-n)*(7*(-2)^n-(-4+sqrt(5))*(3+sqrt(5))^n+(3-sqrt(5))^n*(4+sqrt(5))))/5) \\ Colin Barker, Sep 29 2016
(PARI) Vec((3-2*x^2-6*x)/((1+x)*(x^2-3*x+1)) + O(x^40)) \\ Colin Barker, Sep 29 2016
(Magma) m:=30; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!( (3-2*x^2-6*x)/((1+x)*(x^2-3*x+1)) )); // G. C. Greubel, Jan 08 2019
(Sage) ((3-2*x^2-6*x)/((1+x)*(x^2-3*x+1))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jan 08 2019
(GAP) a:=[3, 0, 4];; for n in [4..30] do a[n]:=2*a[n-1]+2*a[n-2]-a[n-3]; od; a; # G. C. Greubel, Jan 08 2019

Crossrefs

Cf. A000285, A192872, A192879.

Sequence in context: A322936 A307383 A111486 * A126826 A231983 A231982

Adjacent sequences: A192875 A192876 A192877 * A192879 A192880 A192881

Keyword

nonn,easy

Author

Clark Kimberling, Jul 11 2011

Status

approved