This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1.  (See Comments.) 279
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 (list; graph; refs; listen; history; text; internal format)



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)<d(q).  By the division algorithm, there exists a unique pair t and r of polynomials such that p=q*t+r and d(r)<d(q).  Replace q by s to get s*t+r, which is q*u+v for some u and v, where d(v)<d(q).  Continue applying q->s in this manner until reaching w such that d(w)<d(q).  We call w the reduction of p by q->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



Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (1,3,-1,-1).


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


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 -> 1+2x

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


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


Cf. A168561, A192233 - A192240, A192744.

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

Sequence in context: A252746 A182883 A172285 * A243320 A193734 A110608

Adjacent sequences:  A192229 A192230 A192231 * A192233 A192234 A192235




Clark Kimberling, Jun 26 2011



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 26 00:58 EDT 2017. Contains 289798 sequences.