login
Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.
124

%I #16 Dec 16 2015 04:29:03

%S 1,1,3,8,29,133,762,5215,41257,369032,3676209,40333241,483094250,

%T 6271446691,87705811341,1314473334832,21017294666173,357096406209005,

%U 6424799978507178,122024623087820183,2439706330834135361,51219771117454755544

%N Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

%C The titular polynomial is defined recursively by p(n,x)=x*p(n-1,x)+n! for n>0, where p(0,x)=1; see the Example. For an introduction to polynomial reduction, see A192232. The discussion at A192232 Comments continues here:

%C ...

%C Let R(p,q,s) denote the "reduction of polynomial p by q->s" as defined at A192232. Suppose that q(x)=x^k for some k>0 and that s(x)=s(k,0)*x^(k-1)+s(k,1)*x^(k-2)+...+s(k,k-2)x+s(k,k-1).

%C ...

%C First, we shall take p(x)=x^n, where n>=0; the results will be used to formulate R(p,q,s) for general p. Represent R(x^n,q,s) by

%C ...

%C R(x^n)=s(n,0)*x^(k-1)+s(n,1)*x^(k-2)+...+s(n,k-2)*x+s(n,k-1).

%C ...

%C Then each of the sequences u(n)=s(n,h), for h=0,1,...,k-1, satisfies this linear recurrence relation:

%C ...

%C u(n)=s(k,0)*u(n-1)+s(k,1)*u(n-2)+...+s(k,k-2)*u(n-k-1)+s(k,k-1)*u(n-k), with initial values tabulated here:

%C ...

%C n: ..s(n,0)...s(n,1)..s(n,2).......s(n,k-2)..s(n,k-1)

%C 0: ....0........0.......0..............0.......1

%C 1: ....0........0.......0..............1.......0

%C ...

%C k-2: ..0........1.......0..............0.......0

%C k-1: ..0........0.......0..............0.......0

%C k: ..s(k,0)...s(k,1)..s(k,2).......s(k,k-2)..s(k,k-1)

%C ...

%C That completes the formulation for p(x)=x^n. Turning to the general case, suppose that

%C ...

%C p(n,x)=p(n,0)*x^n+p(n,1)*x^(n-1)+...+p(n,n-1)*x+p(n,n)

%C ...

%C is a polynomial of degree n>=0. Then the reduction denoted by (R(p(n,x) by x^k -> s(x)) is the polynomial of degree k-1 given by the matrix product P*S*X, where P=(p(n,0)...p(n,1).........p(n-k)...p(n,n-k+1); X has all 0's except for main diagonal (x^(k-1), x^(k-2)...x,1); and S has

%C ...

%C row 1: ... s(n,0) ... s(n,1) ...... s(n,k-2) . s(n,k-1)

%C row 2: ... s(n-1,0) . s(n-1,1) .... s(n-1,k-2) s(n-1,k-1)

%C ...

%C row n-k+1: s(k,0).... s(k,1) ...... s(k,k-2) ..s(k,k-1)

%C row n-k+2: p(n,n-k+1) p(n,n-k+2) .. p(n,n-1) ..p(n,n)

%C *****

%C As a class of examples, suppose that (v(n)), for n>=0, is a sequence, that p(0,x)=1, and p(n,x)=v(n)+p(n-1,x) for n>0. If q(x)=x^2 and s(x)=x+1, and we write the reduction R(p(n,x)) as u1(n)*x+u2(n), then the sequences u1 and u2 are convolutions with the Fibonacci sequence, viz., let F=(0,1,1,2,3,5,8,...)=A000045 and let G=(1,0,1,1,2,3,5,8...); then u1=G**v and u2=F**v, where ** denotes convolution. Examples (with a few exceptions for initial terms):

%C ...

%C If v(n)=n! then u1=A192744, u2=A192745.

%C If v(n)=n+1 then u1=A000071, u2=A001924.

%C If v(n)=2n then u1=A014739, u2=A027181.

%C If v(n)=2n+1 then u1=A001911, u2=A001891.

%C If v(n)=3n+1 then u1=A027961, u2=A023537.

%C If v(n)=3n+2 then u1=A192746, u2=A192747.

%C If v(n)=3n then u1=A154691, u2=A192748.

%C If v(n)=4n+1 then u1=A053311, u2=A192749.

%C If v(n)=4n+2 then u1=A192750, u2=A192751.

%C If v(n)=4n+3 then u1=A192752, u2=A192753.

%C If v(n)=4n then u1=A147728, u2=A023654.

%C If v(n)=5n+1 then u1=A192754, u2=A192755.

%C If v(n)=5n then u1=A166863, u2=A192756.

%C If v(n)=floor((n+1)tau) then u1=A192457, u2=A023611.

%C If v(n)=floor((n+2)/2) then u1=A052952, u2=A129696.

%C If v(n)=floor((n+3)/3) then u1=A004695, u2=A178982.

%C If v(n)=floor((n+4)/4) then u1=A080239, u2=A192758.

%C If v(n)=floor((n+5)/5) then u1=A124502, u2=A192759.

%C If v(n)=n+2 then u1=A001594, u2=A192760.

%C If v(n)=n+3 then u1=A022318, u2=A192761.

%C If v(n)=n+4 then u1=A022319, u2=A192762.

%C If v(n)=2^n then u1=A027934, u2=A008766.

%C If v(n)=3^n then u1=A106517, u2=A094688.

%F G.f.: (1-x)/(1-x-x^2)/Q(0), where Q(k)= 1 - x*(k+1)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - _Sergei N. Gladkovskii_, May 20 2013

%F Conjecture: a(n) +(-n-2)*a(n-1) +2*(n-1)*a(n-2) +3*a(n-3) +(-n+2)*a(n-4)=0. - _R. J. Mathar_, May 04 2014

%F Conjecture: (-n+2)*a(n) +(n^2-n-1)*a(n-1) +(-n^2+3*n-3)*a(n-2) -(n-1)^2*a(n-3)

%F =0. - _R. J. Mathar_, Dec 16 2015

%e The first five polynomials and their reductions:

%e 1 -> 1

%e 1+x -> 1+x

%e 2+x+x^2 -> 3+2x

%e 6+2x+x^2+x^3 -> 8+5x

%e 24+6x+2x^2+x^3+x^4 -> 29+13x, so that

%e A192744=(1,1,3,8,29,...) and A192745=(0,1,2,5,13,...).

%p A192744p := proc(n,x)

%p option remember;

%p if n = 0 then

%p 1;

%p else

%p x*procname(n-1,x)+n! ;

%p expand(%) ;

%p end if;

%p end proc:

%p A192744 := proc(n)

%p local p;

%p p := A192744p(n,x) ;

%p while degree(p,x) > 1 do

%p p := algsubs(x^2=x+1,p) ;

%p p := expand(p) ;

%p end do:

%p coeftayl(p,x=0,0) ;

%p end proc: # _R. J. Mathar_, Dec 16 2015

%t q = x^2; s = x + 1; z = 40;

%t p[0, n_] := 1; p[n_, x_] := x*p[n - 1, x] + n!;

%t Table[Expand[p[n, x]], {n, 0, 7}]

%t reduce[{p1_, q_, s_, x_}] :=

%t FixedPoint[(s PolynomialQuotient @@ #1 +

%t PolynomialRemainder @@ #1 &)[{#1, q, x}] &, p1]

%t t = Table[reduce[{p[n, x], q, s, x}], {n, 0, z}];

%t u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}]

%t (* A192744 *)

%t u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]

%t (* A192745 *)

%Y Cf. A192232.

%K nonn

%O 0,3

%A _Clark Kimberling_, Jul 09 2011