A112576 -id:A112576 - 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

A265753 a(n) = A007949(A265399(n)).

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 3, 1, 5, 2, 2, 0, 8, 2, 13, 1, 3, 3, 21, 1, 2, 5, 3, 2, 34, 2, 55, 0, 4, 8, 3, 2, 89, 13, 6, 1, 144, 3, 233, 3, 3, 21, 377, 1, 4, 2, 9, 5, 610, 3, 4, 2, 14, 34, 987, 2, 1597, 55, 4, 0, 6, 4, 2584, 8, 22, 3, 4181, 2, 6765, 89, 3, 13, 5, 6, 10946, 1, 4, 144, 17711, 3, 9, 233, 35, 3, 28657, 3, 7, 21

Offset: 1

Antti Karttunen, Dec 15 2015

nonn

a(n) = Coefficient of x in the reduction under x^2->x+1 of the polynomial encoded in the prime factorization of n. (Assuming here only polynomials with nonnegative integer coefficients, see e.g. A206296 for the details).

Completely additive with a(prime(k)) = F(k-1), where F(k) denotes the k-th Fibonacci number, A000045(k). - Peter Munn, Mar 29 2021, incorporating comment by Antti Karttunen, Dec 15 2015

Antti Karttunen, Table of n, a(n) for n = 1..100

Cf. A007949, A112576, A192751, A206296, A265399, A265750, A265752.

Cf. also A000040, A000045.

\\ Needs also code from A265398 and A265399.
A265753 = n -> valuation(A265399(n),3);
for(n=1, 100, write("b265753.txt", n, " ", A265753(n)));

(define (A265753 n) (A007949 (A265399 n)))

a(n) = A007949(A265399(n)).
Other identities. For all n >= 1:
a(A000040(n)) = A000045(n-1). [Generalized by Peter Munn, Mar 29 2021]
a(A206296(n)) = A112576(n).
a(A265750(n)) = A192751(n).

A192387 Coefficient of x in the reduction by x^2 -> x+1 of the polynomial p(n,x) defined below in Comments.

Original entry on oeis.org

0, 2, 4, 32, 96, 512, 1856, 8576, 33792, 147456, 602112, 2566144, 10637312, 44892160, 187269120, 787087360, 3292069888, 13812760576, 57837355008, 242497880064, 1015868817408, 4258009186304, 17841063460864, 74771320537088, 313317428035584

Offset: 1

Clark Kimberling, Jun 30 2011

The polynomial p(n,x) is defined by ((x+d)^n - (x-d)^n)/(2*d), where d = sqrt(x+5). For an introduction to reductions of polynomials by substitutions such as x^2 -> x+1, see A192232.

			The first five polynomials p(n,x) and their reductions are as follows:
  p(0,x) = 1 -> 1
  p(1,x) =     2*x -> 2*x
  p(2,x) = 3 +   x +  3*x^2 -> 8 + 4*x
  p(3,x) =    12*x +  4*x^2 +  4*x^3 -> 8 + 32*x
  p(4,x) = 9 + 6*x + 31*x^2 + 10*x^3 + 5*x^4 -> 96 + 96*x.
From these, read A192386 = (1, 0, 8, 8, 96, ...) and a(n) = (0, 2, 4, 32, 96, ...).

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

Cf. A112576, A192232, A192386, A192388.

R:=PowerSeriesRing(Integers(), 41);
[0] cat Coefficients(R!( 2*x^2/(1-2*x-12*x^2+8*x^3+16*x^4) )); // G. C. Greubel, Jul 10 2023

(See A192386.)
LinearRecurrence[{2,12,-8,-16}, {0,2,4,32}, 40] (* G. C. Greubel, Jul 10 2023 *)

@CachedFunction
def a(n): # a = A192387
    if (n<5): return (0,0,2,4,32)[n]
    else: return 2*a(n-1) +12*a(n-2) -8*a(n-3) -16*a(n-4)
[a(n) for n in range(1,41)] # G. C. Greubel, Jul 10 2023

From Colin Barker, Dec 09 2012: (Start)
a(n) = 2*a(n-1) + 12*a(n-2) - 8*a(n-3) - 16*a(n-4).
G.f.: 2*x^2/(1-2*x-12*x^2+8*x^3+16*x^4). (End)
a(n) = 2^n*A112576(n). - R. J. Mathar, Mar 08 2021
From G. C. Greubel, Jul 10 2023: (Start)
T(n, k) = [x^k] ((x+sqrt(x+5))^n - (x-sqrt(x+5))^n)/(2*sqrt(x+5)).
a(n) = Sum_{k=0..n-1} T(n, k)*Fibonacci(k). (End)

A192388 a(n) = A192387(n)/2.

Original entry on oeis.org

0, 1, 2, 16, 48, 256, 928, 4288, 16896, 73728, 301056, 1283072, 5318656, 22446080, 93634560, 393543680, 1646034944, 6906380288, 28918677504, 121248940032, 507934408704, 2129004593152, 8920531730432, 37385660268544, 156658714017792

Offset: 1

Clark Kimberling, Jun 30 2011

			The first five polynomials p(n,x) and their reductions are as follows:
  p(0,x) = 1 -> 1
  p(1,x) =     2*x -> 2*x
  p(2,x) = 3 +   x +  3*x^2 -> 8 + 4*x
  p(3,x) =    12*x +  4*x^2 +  4*x^3 -> 8 + 32*x
  p(4,x) = 9 + 6*x + 31*x^2 + 10*x^3 + 5*x^4 -> 96 + 96*x.
From these, read a(n) = (0, 2, 4, 32, 96, ...)/2 = (0, 1, 2, 16, 48, ...).

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

Cf. A112576, A192232, A192386, A192387.

R:=PowerSeriesRing(Integers(), 41);
[0] cat Coefficients(R!( x^2/(1-2*x-12*x^2+8*x^3+16*x^4) )); // G. C. Greubel, Jul 10 2023

(* See A192386 *)
LinearRecurrence[{2,12,-8,-16}, {0,1,2,16}, 40] (* G. C. Greubel, Jul 10 2023 *)

@CachedFunction
def a(n): # a = A192388
    if (n<5): return (0,0,1,2,16)[n]
    else: return 2*a(n-1) +12*a(n-2) -8*a(n-3) -16*a(n-4)
[a(n) for n in range(1,41)] # G. C. Greubel, Jul 10 2023

From G. C. Greubel, Jul 10 2023: (Start)
T(n, k) = [x^k] ((x+sqrt(x+5))^n - (x-sqrt(x+5))^n)/(2*sqrt(x+5)).
a(n) = (1/2)*Sum_{k=0..n-1} T(n, k)*Fibonacci(k-1).
a(n) = 2*a(n-1) + 12*a(n-2) - 8*a(n-3) - 16*a(n-4).
G.f.: x^2/(1-2*x-12*x^2+8*x^3+16*x^4).
a(n) = 2^(n-1)*A112576(n). (End)

A139333 Floor of entry (2,1) of [0,1; 1,phi]^n.

Original entry on oeis.org

1, 1, 3, 7, 15, 32, 68, 144, 302, 633, 1328, 2783, 5832, 12219, 25604, 53648, 112408, 235529, 493503, 1034034, 2166605, 4539674, 9511953, 19930339, 41759920, 87499309, 183336777, 384144447, 804895549, 1686492803, 3533698227, 7404136642, 15513842972, 32506061868

Offset: 1

Gary W. Adamson and Roger L. Bagula, Apr 13 2008

nonn

Floor of entry (2,1) and (1,2) of [0,1; 1,phi]^n. Floor numerators of barover[phi] = [phi, phi, phi,...] where phi = 1.618033989... (A001622).

			a(5) = 15 since [0,1, 1,phi]^5 = [7.472...,15.708...; 15.708...,32.888...].
a(5) = 15 = floor 15.708203..., since the first five numerators of continued fraction[phi, phi, phi, phi, phi,...] = [1, phi, (phi^2 + 1), (phi^3 + 2*phi), (phi^4 + 3*phi^2 + 1), where (phi^4 + 3*phi^2 + 1) = 15.708203...

Cf. A001622, A112576, A136319, A192232.

a[n_] := Floor[MatrixPower[{{0, 1}, {1, GoldenRatio}}, n][[1, 2]]]; Array[a, 35] (* Amiram Eldar, Jun 06 2025 *)

a(n)/a(n-1) tends to 2.095293... = exp(arcsinh(phi/2)) (A136319).

a(n) = floor(A192232(n) + A112576(n)*phi), where phi is the golden ratio (A001622). - Amiram Eldar, Jun 06 2025

a(22) corrected and more terms added by Amiram Eldar, Jun 06 2025

A171731 Triangle T : T(n,k)= binomial(n,k)Fibonacci(n-k)= A007318(n,k)A000045(n-k).

Original entry on oeis.org

0, 1, 0, 1, 2, 0, 2, 3, 3, 0, 3, 8, 6, 4, 0, 5, 15, 20, 10, 5, 0, 8, 30, 45, 40, 15, 6, 0, 13, 56, 105, 105, 70, 21, 7, 0, 21, 104, 224, 280, 210, 112, 28, 8, 0, 34, 189, 468, 672, 630, 378, 168, 36, 9, 0, 55, 340, 945, 1560, 1680, 1260, 630, 240, 45, 10, 0

Offset: 0

Philippe Deléham, Dec 16 2009

Diagonal sums : A112576.

Essentially the same as A094440. - Peter Bala, Jan 06 2015

			Triangle begins :
0 ;
1,0 ;
1,2,0 ;
2,3,3,0 ;
3,8,6,4,0 ;
5,15,20,10,5,0 ;
...

Cf. A000045, A007318, A094440.

Flatten[Table[Binomial[n,k]Fibonacci[n-k],{n,0,10},{k,0,n}]] (* Harvey P. Dale, Jan 16 2013 *)

Sum_{k, 0<=k<=n} T(n,k)*x^k = A000045(n), A001906(n), A093131(n), A099453(n-1), A081574(n), A081575(n) for x = 0,1,2,3,4,5 respectively. Sum_{k, 0<=k<=n} T(n,k)*2^(n-k) = A014445(n).

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

A265753 a(n) = A007949(A265399(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A192387 Coefficient of x in the reduction by x^2 -> x+1 of the polynomial p(n,x) defined below in Comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A192388 a(n) = A192387(n)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A139333 Floor of entry (2,1) of [0,1; 1,phi]^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A171731 Triangle T : T(n,k)= binomial(n,k)*Fibonacci(n-k)= A007318(n,k)*A000045(n-k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A171731 Triangle T : T(n,k)= binomial(n,k)Fibonacci(n-k)= A007318(n,k)A000045(n-k).