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

1, 0, 3, 4, 13, 30, 81, 208, 547, 1428, 3741, 9790, 25633, 67104, 175683, 459940, 1204141, 3152478, 8253297, 21607408, 56568931, 148099380, 387729213, 1015088254, 2657535553, 6957518400

Offset: 0

Author

Clark Kimberling, Jul 11 2011

Keywords

• nonn
• easy

Comments

The polynomial p(n,x) is defined by p(0,x)=1, p(1,x)=x, and p(n,x) = x*p(n-1,x) + (x^2)*p(n-1,x) + 1. The resulting sequence typifies a general class which we shall describe here. Suppose that u,v,a,b,c,d,e,f are numbers used to define these polynomials:

...

q(x) = x^2

s(x) = u*x + v

p(0,x) = a, p(1,x) = b*x + c

p(n,x) = d*x*p(n-1,x) + e*(x^2)*p(n-2,x) + f.

...

We shall assume that u is not 0 and that {d,e} is not {0}. The reduction of p(n,x) by the repeated substitution q(x)->s(x), as defined and described at A192232 and A192744, has the form h(n)+k(n)*x. The numerical sequences h and k are, formally, linear recurrence sequences of order 5. The second Mathematica program below shows initial terms and the recurrence coefficients, which are too long to be included here, which imply these properties:

(1) The numbers a,b,c,f affect initial terms but not the recurrence coefficients, which depend only on u,v,d,e.

(2) If v=0 or e=0, the order of recurrence is <= 3.

(3) If v=0 and e=0, the order of recurrence is 2, and the coefficients are 1+d*u and d*u.

(See A192904 for similar results for other p(n,x).)

...

Examples:

u v a b c d e f seq h.....seq k

1 1 1 2 0 1 1 0 -A121646..A059929

1 1 1 3 0 1 1 0 A128533...A081714

1 1 2 1 0 1 1 0 A081714...A001906

1 1 1 1 1 1 1 0 A000045...A001906

1 1 2 1 1 1 1 0 A129905...A192879

1 1 1 2 1 1 1 0 A061646...A079472

1 1 1 1 0 1 1 1 A192872...A192873

1 1 1 1 1 2 1 1 A192874...A192875

1 1 1 1 1 2 1 1 A192876...A192877

1 1 1 1 1 1 2 1 A192880...A192882

1 1 1 1 1 1 1 1 A166536...A064831

The terms of several of these sequences are products of Fibonacci numbers (A000045), or Fibonacci numbers and Lucas numbers (A000032).

Examples

			The coefficients in all the polynomials p(n,x) are Fibonacci numbers (A000045).  The first six and their reductions:
p(0,x) = 1 -> 1
p(1,x) = x -> x
p(2,x) = 1 + 2*x^2 -> 3 + 2*x
p(3,x) = 1 + x + 3*x^3 -> 4 + 7*x
p(4,x) = 1 + x + 2*x^2 + 5*x^4 -> 13 + 18*x
p(5,x) = 1 + x + 2*x^2 + 3*x^3 + 8*x^5 -> 30 + 49*x
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (3,0,-3,1).

Crossrefs

Cf. A192232, A192744, A192873, A192908 (sums of adjacent terms).

Programs

GAP

a:=[1,0,3,4];; for n in [5..30] do a[n]:=3*a[n-1]-3*a[n-3]+a[n-4]; od; a; # G. C. Greubel, Jan 06 2019

Magma

m:=30; R:=PowerSeriesRing(Integers(), m); Coefficients(R!( (2*x-1)*(x^2-x+1)/((x-1)*(1+x)*(x^2-3*x +1)) )); // G. C. Greubel, Jan 06 2019

Mathematica

(* First program *)
q = x^2; s = x + 1; z = 26;
p[0, x_] := 1; p[1, x_] := x;
p[n_, x_] := p[n - 1, x]*x + p[n - 2, x]*x^2 + 1;
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}] (* A192872 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}] (* A192873 *)
(* End of 1st program *)
(* ******************************************** *)
(* Second program: much more general *)
(* u = 1; v = 1; a = 1; b = 1; c = 0; d = 1; e = 1; f = 1; Nine degrees of freedom for user; shown values generate A192872. *)
q = x^2; s = u*x + v; z = 11;
(* will apply reduction (x^2 -> u*x+v) to p(n,x) *)
p[0, x_] := a; p[1, x_] := b*x + c;
(* initial values of polynomial sequence p(n,x) *)
p[n_, x_] := d*x*p[n - 1, x] + e*(x^2)*p[n - 2, x] + f;
(* recurrence for p(n,x) *)
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}];
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}];
Simplify[FindLinearRecurrence[u1]] (* for 0-sequence *)
Simplify[FindLinearRecurrence[u2]] (* for 1-sequence *)
u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, 4}]
(* initial values for 0-sequence *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, 4}]
(* initial values for 1-sequence *)
LinearRecurrence[{3,0,-3,1},{1,0,3,4},26] (* Ray Chandler, Aug 02 2015 *)

PARI

my(x='x+O('x^30)); Vec((2*x-1)*(x^2-x+1)/((x-1)*(1+x)*(x^2-3*x +1))) \\ G. C. Greubel, Jan 06 2019

Sage

((2*x-1)*(x^2-x+1)/((x-1)*(1+x)*(x^2-3*x +1))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jan 06 2019

Formula

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

G.f.: (2*x-1)*(x^2-x+1) / ( (x-1)*(1+x)*(x^2-3*x+1) ). - R. J. Mathar, Oct 26 2011