cp's OEIS Frontend

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

%I A192232 #47 Oct 21 2024 09:02:06
%S A192232 1,0,2,1,6,7,22,36,89,168,377,756,1630,3353,7110,14783,31130,65016,
%T A192232 136513,285648,599041,1254456,2629418,5508097,11542854,24183271,
%U A192232 50674318,106173180,222470009,466131960,976694489,2046447180,4287928678,8984443769,18825088134
%N A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1.  (See Comments.)
%C A192232 Polynomial reduction: an introduction
%C A192232 ...
%C A192232 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.
%C A192232 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.
%C A192232 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).
%C A192232 Following are examples of reduction by x^2->x+1:
%C A192232 n-th Fibonacci p(x) -> A192232+x*A112576
%C A192232 n-th cyclotomic p(x) -> A192233+x*A051258
%C A192232 n-th 1st-kind Chebyshev p(x) -> A192234+x*A071101
%C A192232 n-th 2nd-kind Chebyshev p(x) -> A192235+x*A192236
%C A192232 x(x+1)(x+2)...(x+n-1) -> A192238+x*A192239
%C A192232 (x+1)^n -> A001519+x*A001906
%C A192232 (x^2+x+1)^n -> A154626+x*A087635
%C A192232 (x+2)^n -> A020876+x*A030191
%C A192232 (x+3)^n -> A192240+x*A099453
%C A192232 ...
%C A192232 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)).
%C A192232 ...
%C A192232 For selected sequences b, here are the 0-sequences and 1-sequences of (reduction of b by x^2->x+1):
%C A192232 b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields
%C A192232    0-sequence A166536 and 1-sequence A064831.
%C A192232 b=(1,A000045)=(1,1,1,2,3,5,8,...) yields
%C A192232    0-sequence A166516 and 1-sequence A001654.
%C A192232 b=A000027, natural number sequence (1,2,3,4,...) yields
%C A192232   0-sequence A190062 and 1-sequence A122491.
%C A192232 b=A000032, Lucas sequence (1,3,4,7,11,...) yields
%C A192232   0-sequence A192243 and 1-sequence A192068.
%C A192232 b=A000217, triangular sequence (1,3,6,10,...) yields
%C A192232   0-sequence A192244 and 1-sequence A192245.
%C A192232 b=A000290, squares sequence (1,4,9,16,...) yields
%C A192232   0-sequence A192254 and 1-sequence A192255.
%C A192232 More examples:  A192245-A192257.
%C A192232 ...
%C A192232 More comments:
%C A192232 (1) If s(n,x)=(reduction of x^n by q->s) and
%C A192232     p(x)=p(0)x^n+p(1)x^(n-1)+...+p(n)x^0, then
%C A192232     (reduction of p by q->s)=p(0)s(n,x)+p(1)s(n-1,x)
%C A192232     +...+p(n-1)s(1,x)+p(n)s(0,x).  See A192744.
%C A192232 (2) For any polynomial p(x), let P(x)=(reduction of p(x)
%C A192232     by q->s).  Then P(r)=p(r) for each zero r of
%C A192232     q(x)-s(x).  In particular, if q(x)=x^2 and s(x)=x+1,
%C A192232     then P(r)=p(r) if r=(1+sqrt(5))/2 (golden ratio) or
%C A192232     r=(1-sqrt(5))/2.
%H A192232 Vincenzo Librandi, <a href="/A192232/b192232.txt">Table of n, a(n) for n = 1..1000</a>
%H A192232 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-1,-1).
%F A192232 Empirical G.f.: -x*(x^2+x-1)/(x^4+x^3-3*x^2-x+1). - _Colin Barker_, Sep 11 2012
%F A192232 The above formula is correct. - _Charles R Greathouse IV_, Jan 08 2013
%F A192232 a(n) = A265752(A206296(n)). - _Antti Karttunen_, Dec 15 2015
%F A192232 a(n) = A112576(n) -A112576(n-1) -A112576(n-2). - _R. J. Mathar_, Dec 16 2015
%e A192232 The first four Fibonacci polynomials and their reductions by x^2->x+1 are shown here:
%e A192232 F1(x)=1 -> 1 + 0x
%e A192232 F2(x)=x -> 0 + 1x
%e A192232 F3(x)=x^2+1 -> 2+1x
%e A192232 F4(x)=x^3+2x -> 1+4x
%e A192232 F5(x)=x^4+3x^2+1 -> (x+1)^2+3(x+1)+1 -> 6+6x.
%e A192232 From these, read A192232=(1,0,1,1,6,...) and A112576=(0,1,1,4,6,...).
%t A192232 q[x_] := x + 1;
%t A192232 reductionRules = {x^y_?EvenQ -> q[x]^(y/2),  x^y_?OddQ -> x q[x]^((y - 1)/2)};
%t A192232 t = Table[FixedPoint[Expand[#1 /. reductionRules] &, Fibonacci[n, x]], {n, 1, 40}];
%t A192232 Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}]
%t A192232   (* A192232 *)
%t A192232 Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]
%t A192232 (* A112576 *)
%t A192232 (* _Peter J. C. Moses_, Jun 25 2011 *)
%t A192232 LinearRecurrence[{1, 3, -1, -1}, {1, 0, 2, 1}, 60] (* _Vladimir Joseph Stephan Orlovsky_, Feb 08 2012 *)
%o A192232 (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
%Y A192232 Cf. A168561, A192233 - A192240, A192744.
%Y A192232 Cf. A206296, A265398, A265399, A265752, A265753.
%K A192232 nonn,easy
%O A192232 1,3
%A A192232 _Clark Kimberling_, Jun 26 2011
%E A192232 Example corrected by _Clark Kimberling_, Dec 18 2017