0,3

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).

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).

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

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

(* 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 *)

(* ******************************************** *)

(* Alternative: 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

(Magma) m:=30; R<x>:=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

(SageMath) ((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

(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

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

Sequence in context: A142860 A111954 A385267 * A036672 A174684 A286917

Adjacent sequences: A192869 A192870 A192871 * A192873 A192874 A192875

nonn,easy

Clark Kimberling, Jul 11 2011

approved