A192236 -id:A192236 - cp's OEIS frontend

A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1. (See Comments.)

1, 0, 2, 1, 6, 7, 22, 36, 89, 168, 377, 756, 1630, 3353, 7110, 14783, 31130, 65016, 136513, 285648, 599041, 1254456, 2629418, 5508097, 11542854, 24183271, 50674318, 106173180, 222470009, 466131960, 976694489, 2046447180, 4287928678, 8984443769, 18825088134

Offset: 1

Clark Kimberling, Jun 26 2011

Polynomial reduction: an introduction
...
We begin with an example.  Suppose that p(x) is a polynomial, so that p(x)=(x^2)t(x)+r(x) for some polynomials t(x) and r(x), where r(x) has degree 0 or 1.  Replace x^2 by x+1 to get (x+1)t(x)+r(x), which is (x^2)u(x)+v(x) for some u(x) and v(x), where v(x) has degree 0 or 1.  Continuing in this manner results in a fixed polynomial w(x) of degree 0 or 1.  If p(x)=x^n, then w(x)=x*F(n)+F(n-1), where F=A000045, the sequence of Fibonacci numbers.
In order to generalize, write d(g) for the degree of an arbitrary polynomial g(x), and suppose that p, q, s are polynomials satisfying d(s)s in this manner until reaching w such that d(w)s.
The coefficients of (reduction of p by q->s) comprise a vector of length d(q)-1, so that a sequence p(n,x) of polynomials begets a sequence of vectors, such as (F(n), F(n-1)) in the above example.  We are interested in the component sequences (e.g., F(n-1) and F(n)) for various choices of p(n,x).
Following are examples of reduction by x^2->x+1:
n-th Fibonacci p(x) -> A192232+x*A112576
n-th cyclotomic p(x) -> A192233+x*A051258
n-th 1st-kind Chebyshev p(x) -> A192234+x*A071101
n-th 2nd-kind Chebyshev p(x) -> A192235+x*A192236
x(x+1)(x+2)...(x+n-1) -> A192238+x*A192239
(x+1)^n -> A001519+x*A001906
(x^2+x+1)^n -> A154626+x*A087635
(x+2)^n -> A020876+x*A030191
(x+3)^n -> A192240+x*A099453
...
Suppose that b=(b(0), b(1),...) is a sequence, and let p(n,x)=b(0)+b(1)x+b(2)x^2+...+b(n)x^n.  We define (reduction of sequence b by q->s) to be the vector given by (reduction of p(n,x) by q->s), with components in the order of powers, from 0 up to d(q)-1.  For k=0,1,...,d(q)-1, we then have the "k-sequence of (reduction of sequence b by q->s)".  Continuing the example, if b is the sequence given by b(k)=1 if k=n and b(k)=0 otherwise, then the 0-sequence of (reduction of b by x^2->x+1) is (F(n-1)), and the 1-sequence is (F(n)).
...
For selected sequences b, here are the 0-sequences and 1-sequences of (reduction of b by x^2->x+1):
b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields
   0-sequence A166536 and 1-sequence A064831.
b=(1,A000045)=(1,1,1,2,3,5,8,...) yields
   0-sequence A166516 and 1-sequence A001654.
b=A000027, natural number sequence (1,2,3,4,...) yields
  0-sequence A190062 and 1-sequence A122491.
b=A000032, Lucas sequence (1,3,4,7,11,...) yields
  0-sequence A192243 and 1-sequence A192068.
b=A000217, triangular sequence (1,3,6,10,...) yields
  0-sequence A192244 and 1-sequence A192245.
b=A000290, squares sequence (1,4,9,16,...) yields
  0-sequence A192254 and 1-sequence A192255.
More examples:  A192245-A192257.
...
More comments:
(1) If s(n,x)=(reduction of x^n by q->s) and
    p(x)=p(0)x^n+p(1)x^(n-1)+...+p(n)x^0, then
    (reduction of p by q->s)=p(0)s(n,x)+p(1)s(n-1,x)
    +...+p(n-1)s(1,x)+p(n)s(0,x).  See A192744.
(2) For any polynomial p(x), let P(x)=(reduction of p(x)
    by q->s).  Then P(r)=p(r) for each zero r of
    q(x)-s(x).  In particular, if q(x)=x^2 and s(x)=x+1,
    then P(r)=p(r) if r=(1+sqrt(5))/2 (golden ratio) or
    r=(1-sqrt(5))/2.

			The first four Fibonacci polynomials and their reductions by x^2->x+1 are shown here:
F1(x)=1 -> 1 + 0x
F2(x)=x -> 0 + 1x
F3(x)=x^2+1 -> 2+1x
F4(x)=x^3+2x -> 1+4x
F5(x)=x^4+3x^2+1 -> (x+1)^2+3(x+1)+1 -> 6+6x.
From these, read A192232=(1,0,1,1,6,...) and A112576=(0,1,1,4,6,...).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,3,-1,-1).

Cf. A168561, A192233 - A192240, A192744.

Cf. A206296, A265398, A265399, A265752, A265753.

q[x_] := x + 1;
reductionRules = {x^y_?EvenQ -> q[x]^(y/2),  x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[FixedPoint[Expand[#1 /. reductionRules] &, Fibonacci[n, x]], {n, 1, 40}];
Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}]
  (* A192232 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]
(* A112576 *)
(* Peter J. C. Moses, Jun 25 2011 *)
LinearRecurrence[{1, 3, -1, -1}, {1, 0, 2, 1}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

Vec((1-x-x^2)/(1-x-3*x^2+x^3+x^4)+O(x^99)) \\ Charles R Greathouse IV, Jan 08 2013

Empirical G.f.: -x*(x^2+x-1)/(x^4+x^3-3*x^2-x+1). - Colin Barker, Sep 11 2012
The above formula is correct. - Charles R Greathouse IV, Jan 08 2013
a(n) = A265752(A206296(n)). - Antti Karttunen, Dec 15 2015
a(n) = A112576(n) -A112576(n-1) -A112576(n-2). - R. J. Mathar, Dec 16 2015

Example corrected by Clark Kimberling, Dec 18 2017

A192235 Constant term of the reduction of the n-th 2nd-kind Chebyshev polynomial by x^2 -> x+1.

Original entry on oeis.org

0, 3, 8, 21, 64, 183, 528, 1529, 4416, 12763, 36888, 106605, 308096, 890415, 2573344, 7437105, 21493632, 62117747, 179523624, 518832901, 1499454912, 4333505127, 12524062256, 36195211689, 104606103232, 302317249227, 873713066040

Offset: 1

Clark Kimberling, Jun 26 2011

nonn

See A192232.

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

Cf. A192232, A192236, A192237.

a:=[0,3,8,21];; for n in [5..40] do a[n]:=2*a[n-1]+2*a[n-2]+ 2*a[n-3]-a[n-4]; od; a; # G. C. Greubel, Jul 30 2019

I:=[0, 3, 8, 21]; [n le 4 select I[n] else 2*Self(n-1) +2*Self(n-2) +2*Self(n-3) -Self(n-4): n in [1..40]]; // G. C. Greubel, Jul 30 2019

q[x_]:= x + 1;
reductionRules = {x^y_?EvenQ -> q[x]^(y/2), x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[Last[Most[FixedPointList[Expand[#1 /. reductionRules] &, ChebyshevU[n, x]]]], {n, 1, 40}];
Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}] (* A192235 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}] (* A192236 *)
Table[Coefficient[Part[t, n]/2, x, 1], {n, 1, 40}] (* A192237 *)
(* by Peter J. C. Moses, Jun 25 2011 *)
LinearRecurrence[{2,2,2,-1}, {0,3,8,21}, 40] (* G. C. Greubel, Jul 30 2019 *)

a(n)=my(t=polchebyshev(n,2));while(poldegree(t)>1, t=substpol(t, x^2,x+1));subst(t,x,0) \\ Charles R Greathouse IV, Feb 09 2012

m=40; v=concat([0, 3, 8, 21], vector(m-4)); for(n=5, m, v[n] = 2*v[n-1]+2*v[n-2]+2*v[n-3]-v[n-4]); v \\ G. C. Greubel, Jul 30 2019

@cached_function
def a(n):
    if (n==0): return 0
    elif (1 <= n <= 3): return fibonacci(2*n+2)
    else: return 2*(a(n-1) + a(n-2) + a(n-3)) - a(n-4)
[a(n) for n in (0..40)] # G. C. Greubel, Jul 30 2019

Empirical G.f.: x^2*(3-x)*(1+x)/(1-2*x-2*x^2-2*x^3+x^4). - Colin Barker, Sep 11 2012

A192237 a(n) = 2*(a(n-1) + a(n-2) + a(n-3)) - a(n-4) for n >= 4, with initial terms 0,0,0,1.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 18, 51, 148, 428, 1236, 3573, 10326, 29842, 86246, 249255, 720360, 2081880, 6016744, 17388713, 50254314, 145237662, 419744634, 1213084507, 3505879292, 10132179204, 29282541372, 84628115229, 244579792318, 706848718634, 2042830710990, 5903890328655, 17062559724240, 49311712809136, 142513495013072

Offset: 0

Clark Kimberling, Jun 26 2011

nonn

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,2,2,-1).

Cf. A192232, A192235.
With a different offset, equals (A192236)/2.
Other sequences with this recurrence but different initial conditions: A192234, A317973, A317974, A317975, A317976.

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

I:=[0,0,0,1]; [n le 4 select I[n] else 2*(Self(n-1)+Self(n-2) +Self(n-3))-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Sep 06 2018

q[x_]:= x + 1;
reductionRules = {x^y_?EvenQ -> q[x]^(y/2), x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[Last[Most[FixedPointList[Expand[#1 /. reductionRules] &, ChebyshevU[n, x]]]], {n, 1, 40}];
Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}] (* A192235 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}] (* A192236 *)
Table[Coefficient[Part[t, n]/2, x, 1], {n, 1, 40}] (* A192237 *)
(* by Peter J. C. Moses, Jun 25 2011 *)
LinearRecurrence[{2,2,2,-1}, {0,0,0,1}, 40] (* Vincenzo Librandi, Sep 06 2018 *)

concat(vector(3), Vec(x^3/(1-2*x-2*x^2-2*x^3+x^4) + O(x^40))) \\ Colin Barker, Sep 06 2018

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

G.f.: x^3 / (1 - 2*x - 2*x^2 - 2*x^3 + x^4). - Colin Barker, Sep 12 2012 and Sep 06 2018

Entry revised (with new offset and initial terms) by N. J. A. Sloane, Sep 03 2018

cp's OEIS Frontend

A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1. (See Comments.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A192235 Constant term of the reduction of the n-th 2nd-kind Chebyshev polynomial by x^2 -> x+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

PARI

Sage

Formula

A192237 a(n) = 2*(a(n-1) + a(n-2) + a(n-3)) - a(n-4) for n >= 4, with initial terms 0,0,0,1.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions