login
A192872
Constant term in the reduction by (x^2 -> x+1) of the polynomial p(n,x) given in Comments.
32
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,3
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).
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
EXAMPLE
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
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 *)
PROG
(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
(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
(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
CROSSREFS
Cf. A192232, A192744, A192873, A192908 (sums of adjacent terms).
Sequence in context: A151521 A142860 A111954 * A036672 A174684 A286917
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Jul 11 2011
STATUS
approved