OFFSET
1,3
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)<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:
...
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
b=(1,A000045)=(1,1,1,2,3,5,8,...) yields
b=A000027, natural number sequence (1,2,3,4,...) yields
b=A000032, Lucas sequence (1,3,4,7,11,...) yields
b=(A000217, triangular sequence (1,3,6,10,...) yields
b=(A000290, squares sequence (1,4,9,16,...) yields
...
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.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,3,-1,-1).
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
EXAMPLE
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Jun 26 2011
EXTENSIONS
Example corrected by Clark Kimberling, Dec 18 2017
STATUS
approved