cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

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

Original entry on oeis.org

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

Views

Author

Clark Kimberling, Jun 26 2011

Keywords

Comments

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.

Examples

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

Links

Crossrefs

Cf. A168561, A192233 - A192240, A192744.
Cf. A206296, A265398, A265399, A265752, A265753.

Programs

  • Mathematica
    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 *)
  • PARI
    Vec((1-x-x^2)/(1-x-3*x^2+x^3+x^4)+O(x^99)) \\ Charles R Greathouse IV, Jan 08 2013

Formula

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

Extensions

Example corrected by Clark Kimberling, Dec 18 2017

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

Original entry on oeis.org

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

Views

Author

Clark Kimberling, Jul 11 2011

Keywords

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

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
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.