A192232 -id:A192232 - cp's OEIS frontend

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

1, 1, 3, 8, 29, 133, 762, 5215, 41257, 369032, 3676209, 40333241, 483094250, 6271446691, 87705811341, 1314473334832, 21017294666173, 357096406209005, 6424799978507178, 122024623087820183, 2439706330834135361, 51219771117454755544

Offset: 0

Clark Kimberling, Jul 09 2011

nonn

The titular polynomial is defined recursively by p(n,x)=x*p(n-1,x)+n! for n>0, where p(0,x)=1; see the Example.  For an introduction to polynomial reduction, see A192232.  The discussion at A192232 Comments continues here:
...
Let R(p,q,s) denote the "reduction of polynomial p by q->s" as defined at A192232.  Suppose that q(x)=x^k for some k>0 and that s(x)=s(k,0)*x^(k-1)+s(k,1)*x^(k-2)+...+s(k,k-2)x+s(k,k-1).
...
First, we shall take p(x)=x^n, where n>=0; the results will be used to formulate R(p,q,s) for general p.  Represent R(x^n,q,s) by
...
R(x^n)=s(n,0)*x^(k-1)+s(n,1)*x^(k-2)+...+s(n,k-2)*x+s(n,k-1).
...
Then each of the sequences u(n)=s(n,h), for h=0,1,...,k-1, satisfies this linear recurrence relation:
...
u(n)=s(k,0)*u(n-1)+s(k,1)*u(n-2)+...+s(k,k-2)*u(n-k-1)+s(k,k-1)*u(n-k), with initial values tabulated here:
...
n: ..s(n,0)...s(n,1)..s(n,2).......s(n,k-2)..s(n,k-1)
0: ....0........0.......0..............0.......1
1: ....0........0.......0..............1.......0
...
k-2: ..0........1.......0..............0.......0
k-1: ..0........0.......0..............0.......0
k: ..s(k,0)...s(k,1)..s(k,2).......s(k,k-2)..s(k,k-1)
...
That completes the formulation for p(x)=x^n.  Turning to the general case, suppose that
...
p(n,x)=p(n,0)*x^n+p(n,1)*x^(n-1)+...+p(n,n-1)*x+p(n,n)
...
is a polynomial of degree n>=0.  Then the reduction denoted by (R(p(n,x) by x^k -> s(x)) is the polynomial of degree k-1 given by the matrix product P*S*X, where P=(p(n,0)...p(n,1).........p(n-k)...p(n,n-k+1); X has all 0's except for main diagonal (x^(k-1), x^(k-2)...x,1); and S has
...
row 1: ... s(n,0) ... s(n,1) ...... s(n,k-2) . s(n,k-1)
row 2: ... s(n-1,0) . s(n-1,1) .... s(n-1,k-2) s(n-1,k-1)
...
row n-k+1: s(k,0).... s(k,1) ...... s(k,k-2) ..s(k,k-1)
row n-k+2: p(n,n-k+1) p(n,n-k+2) .. p(n,n-1) ..p(n,n)
*****
As a class of examples, suppose that (v(n)), for n>=0, is a sequence, that p(0,x)=1, and p(n,x)=v(n)+p(n-1,x) for n>0.  If q(x)=x^2 and s(x)=x+1, and we write the reduction R(p(n,x)) as u1(n)*x+u2(n), then the sequences u1 and u2 are convolutions with the Fibonacci sequence, viz., let F=(0,1,1,2,3,5,8,...)=A000045 and let G=(1,0,1,1,2,3,5,8...); then u1=G**v and u2=F**v, where ** denotes convolution.  Examples (with a few exceptions for initial terms):
...
If v(n)=n! then u1=A192744, u2=A192745.
If v(n)=n+1 then u1=A000071, u2=A001924.
If v(n)=2n then u1=A014739, u2=A027181.
If v(n)=2n+1 then u1=A001911, u2=A001891.
If v(n)=3n+1 then u1=A027961, u2=A023537.
If v(n)=3n+2 then u1=A192746, u2=A192747.
If v(n)=3n then u1=A154691, u2=A192748.
If v(n)=4n+1 then u1=A053311, u2=A192749.
If v(n)=4n+2 then u1=A192750, u2=A192751.
If v(n)=4n+3 then u1=A192752, u2=A192753.
If v(n)=4n then u1=A147728, u2=A023654.
If v(n)=5n+1 then u1=A192754, u2=A192755.
If v(n)=5n then u1=A166863, u2=A192756.
If v(n)=floor((n+1)tau) then u1=A192457, u2=A023611.
If v(n)=floor((n+2)/2) then u1=A052952, u2=A129696.
If v(n)=floor((n+3)/3) then u1=A004695, u2=A178982.
If v(n)=floor((n+4)/4) then u1=A080239, u2=A192758.
If v(n)=floor((n+5)/5) then u1=A124502, u2=A192759.
If v(n)=n+2 then u1=A001594, u2=A192760.
If v(n)=n+3 then u1=A022318, u2=A192761.
If v(n)=n+4 then u1=A022319, u2=A192762.
If v(n)=2^n then u1=A027934, u2=A008766.
If v(n)=3^n then u1=A106517, u2=A094688.

			The first five polynomials and their reductions:
1 -> 1
1+x -> 1+x
2+x+x^2 -> 3+2x
6+2x+x^2+x^3 -> 8+5x
24+6x+2x^2+x^3+x^4 -> 29+13x, so that
A192744=(1,1,3,8,29,...) and A192745=(0,1,2,5,13,...).

Cf. A192232.

A192744p := proc(n,x)
    option remember;
    if n = 0 then
        1;
    else
        x*procname(n-1,x)+n! ;
        expand(%) ;
    end if;
end proc:
A192744 := proc(n)
    local p;
    p := A192744p(n,x) ;
    while degree(p,x) > 1 do
        p := algsubs(x^2=x+1,p) ;
        p := expand(p) ;
    end do:
    coeftayl(p,x=0,0) ;
end proc: # R. J. Mathar, Dec 16 2015

q = x^2; s = x + 1; z = 40;
p[0, n_] := 1; p[n_, x_] := x*p[n - 1, x] + n!;
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}]
  (* A192744 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
  (* A192745 *)

G.f.: (1-x)/(1-x-x^2)/Q(0), where Q(k)= 1 - x*(k+1)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 20 2013
Conjecture: a(n) +(-n-2)*a(n-1) +2*(n-1)*a(n-2) +3*a(n-3) +(-n+2)*a(n-4)=0. - R. J. Mathar, May 04 2014
Conjecture: (-n+2)*a(n) +(n^2-n-1)*a(n-1) +(-n^2+3*n-3)*a(n-2) -(n-1)^2*a(n-3)
=0. - R. J. Mathar, Dec 16 2015

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

Original entry on oeis.org

0, 1, 3, 9, 20, 40, 74, 131, 225, 379, 630, 1038, 1700, 2773, 4511, 7325, 11880, 19252, 31182, 50487, 81725, 132271, 214058, 346394, 560520, 906985, 1467579, 2374641, 3842300, 6217024, 10059410, 16276523, 26336025, 42612643, 68948766

Offset: 0

Clark Kimberling, Jul 13 2011

The titular polynomials are defined recursively:  p(n,x) = x*p(n-1,x) + 3n - 1, with p(0,x)=1.  For an introduction to reductions of polynomials by substitutions such as x^2 -> x+1, see A192232 and A192744.
...
The list of examples at A192744 is extended here; the recurrence is given by p(n,x) = x*p(n-1,x) + v(n), with p(0,x)=1, and the reduction of p(n,x) by x^2 -> x+1 is represented by u1 + u2*x:
...
If v(n)=        n, then u1=A001595, u2=A104161.
If v(n)=      n-1, then u1=A001610, u2=A066982.
If v(n)=     3n-1, then u1=A171516, u2=A192951.
If v(n)=     3n-2, then u1=A192746, u2=A192952.
If v(n)=     2n-1, then u1=A111314, u2=A192953.
If v(n)=      n^2, then u1=A192954, u2=A192955.
If v(n)=   -1+n^2, then u1=A192956, u2=A192957.
If v(n)=    1+n^2, then u1=A192953, u2=A192389.
If v(n)=   -2+n^2, then u1=A192958, u2=A192959.
If v(n)=    2+n^2, then u1=A192960, u2=A192961.
If v(n)=    n+n^2, then u1=A192962, u2=A192963.
If v(n)=   -n+n^2, then u1=A192964, u2=A192965.
If v(n)= n(n+1)/2, then u1=A030119, u2=A192966.
If v(n)= n(n-1)/2, then u1=A192967, u2=A192968.
If v(n)= n(n+3)/2, then u1=A192969, u2=A192970.
If v(n)=     2n^2, then u1=A192971, u2=A192972.
If v(n)=   1+2n^2, then u1=A192973, u2=A192974.
If v(n)=  -1+2n^2, then u1=A192975, u2=A192976.
If v(n)=  1+n+n^2, then u1=A027181, u2=A192978.
If v(n)=  1-n+n^2, then u1=A192979, u2=A192980.
If v(n)=  (n+1)^2, then u1=A001891, u2=A053808.
If v(n)=  (n-1)^2, then u1=A192981, u2=A192982.

Vincenzo Librandi, Table of n, a(n) for n = 0..400
Index entries for linear recurrences with constant coefficients, signature (3, -2, -1, 1).

Cf. A000045, A192232, A192744.

F:=Fibonacci;; List([0..40], n-> F(n+4)+2*F(n+2)-(3*n+5)); # G. C. Greubel, Jul 12 2019

I:=[0, 1, 3, 9]; [n le 4 select I[n] else 3*Self(n-1)-2*Self(n-2)-1*Self(n-3)+Self(n-4): n in [1..40]]; // Vincenzo Librandi, Nov 16 2011

F:=Fibonacci; [F(n+4)+2*F(n+2)-(3*n+5): n in [0..40]]; // G. C. Greubel, Jul 12 2019

(* First program *)
q = x^2; s = x + 1; z = 40;
p[0, x]:= 1;
p[n_, x_]:= x*p[n-1, x] + 3n - 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}] (* A171516 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}] (* A192951 *)
(* Additional programs *)
LinearRecurrence[{3,-2,-1,1},{0,1,3,9},40] (* Vincenzo Librandi, Nov 16 2011 *)
With[{F=Fibonacci}, Table[F[n+4]+2*F[n+2]-(3*n+5), {n,0,40}]] (* G. C. Greubel, Jul 12 2019 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,-1,-2,3]^n*[0;1;3;9])[1,1] \\ Charles R Greathouse IV, Mar 22 2016

vector(40, n, n--; f=fibonacci; f(n+4)+2*f(n+2)-(3*n+5)) \\ G. C. Greubel, Jul 12 2019

f=fibonacci; [f(n+4)+2*f(n+2)-(3*n+5) for n in (0..40)] # G. C. Greubel, Jul 12 2019

a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4).
From Bruno Berselli, Nov 16 2011: (Start)
G.f.: x*(1+2*x^2)/((1-x)^2*(1 - x - x^2)).
a(n) = ((25+13*t)*(1+t)^n + (25-13*t)*(1-t)^n)/(10*2^n) - 3*n - 5 = A000285(n+2) - 3*n - 5  where t=sqrt(5). (End)
a(n) = Fibonacci(n+4) + 2*Fibonacci(n+2) - (3*n+5). - G. C. Greubel, Jul 12 2019

A193010 Decimal expansion of the constant term of the reduction of e^x by x^2->x+1.

Original entry on oeis.org

1, 7, 8, 3, 9, 2, 2, 9, 9, 6, 3, 1, 2, 8, 7, 8, 7, 6, 7, 8, 4, 6, 2, 3, 6, 9, 1, 6, 0, 9, 0, 1, 7, 0, 9, 7, 2, 5, 1, 0, 2, 9, 8, 6, 0, 6, 3, 3, 8, 4, 1, 2, 1, 7, 8, 7, 0, 7, 0, 0, 0, 7, 3, 6, 6, 8, 9, 5, 2, 5, 9, 7, 4, 0, 0, 2, 0, 3, 0, 2, 5, 3, 5, 4, 8, 2, 6, 1, 5, 6, 5, 0, 5, 6, 7, 1, 9, 4, 5, 2

Offset: 1

Clark Kimberling, Jul 14 2011

Suppose that q and s are polynomials and degree(q)>degree(s).  The reduction of a polynomial p by q->s is introduced at A192232.  If p is replaced by a function f having power series
c(0) + c(1)*x + c(2)*x^2 + ... ,
then the reduction, R(f), of f by q->s is here introduced as the limit, if it exists, of the reduction of p(n,x) by q->s, where p(n,x) is the n-th partial sum of f(x):
R(f(x)) = c(0)*R(1) + c(1)*R(x) + c(2)*R(x^2) + ...  If q(x)=x^2 and s(x)=x+1, then
R(f(x)) = c(0) + c(1)*x + c(2)*(x+1) + c(3)*(2x+1) + c(4)(3x+2) + ..., so that
R(f(x)) = Sum_{n>=0} c(n)*(F(n)*x+F(n-1)), where F=A000045 (Fibonacci sequence), so that
R(f(x)) = u0 + x*u1 where u0 = Sum_{n>=0} c(n)*F(n-1), u1 = Sum_{n>=0} c(n)*F(n); the numbers u0 and u1 are given by A193010 and A098689.
Following is a list of reductions by x^2->x+1 of selected functions.  Each sequence A-number refers to the constant represented by the sequence.  Adjustments for offsets are needed in some cases.
e^x......... A193010 + x*A098689
e^(-x)...... A193026 + x*A099935
e^(2x)...... A193027 + x*A193028
e^(x/2)..... A193029 + x*A193030
sin x....... A193011 + x*A193012
cos x....... A193013 + x*A193014
sinh x...... A193015 + x*A193016
cosh x...... A193017 + x*A193025
2^x......... A193031 + x*A193032
2^(-x)...... A193009 + x*A193035
3^x......... A193083 + x*A193084
t^x......... A193075 + x*A193076, t=(1+sqrt(5))/2
t^(-x)...... A193077 + x*A193078, t=(1+sqrt(5))/2
sinh(2x).... A193079 + x*A193080
cosh(2x).... A193081 + x*A193082
(e^x)cos x.. A193083 + x*A193084
(e^x)sin x.. A193085 + x*A193086
(cos x)^2... A193087 + x*A193088
(sin x)^2... A193089 + x*A193088

			1.783922996312878767846236916090170972510...

Cf. A000045, A192232.

f[x_] := Exp[x]; r[n_] := Fibonacci[n];
c[n_] := SeriesCoefficient[Series[f[x], {x, 0, n}], n]
u0 = N[Sum[c[n]*r[n - 1], {n, 0, 200}], 100]
RealDigits[u0, 10]

From Amiram Eldar, Jan 18 2022: (Start)
Equals 1 + Sum_{k>=1} Fibonacci(k-1)/k!.
Equals (sqrt(5)-1) * (2*sqrt(5)*exp(sqrt(5)) + 3*sqrt(5) + 5) / (20 * exp((sqrt(5)-1)/2)). (End)

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

Clark Kimberling, Jul 11 2011

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

			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

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

Cf. A192232, A192744, A192873, A192908 (sums of adjacent terms).

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

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

(* 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 *)

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

((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

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

A003683 a(n) = 2^(n-1)*(2^n - (-1)^n)/3.

Original entry on oeis.org

0, 1, 2, 12, 40, 176, 672, 2752, 10880, 43776, 174592, 699392, 2795520, 11186176, 44736512, 178962432, 715816960, 2863333376, 11453202432, 45813071872, 183251763200, 733008101376, 2932030308352, 11728125427712

Offset: 0

N. J. A. Sloane

a(n) = A001045(n) * A011782(n). - Paul Barry, May 20 2003
The sequence 1,2,12,... is the binomial transform of (1, 1, 9, 9, 81, 81, ...) = 2*3^n/3 + (-3)^n/3. - Paul Barry, Jul 17 2003
Form a graph whose adjacency matrix is the tensor product of that of C_3 and [1,1;1,1]. a(n) counts walks of length n between any pair of adjacent nodes. A054881(n) counts closed walks of length n at a node.
Arises in connection with merit factor of the GRS sequences - see Hoeholdt et al.
2*a(n) = the constant term of the reduction by x^2->x+2 of the polynomial p(n,x) = ((x+d)^n-(x-d)^n)/(2d), where d=sqrt(x+2); see A192382.  For an introduction to reductions of polynomials by substitutions such as x^2->x+2, see A192232. - Clark Kimberling, Jun 30 2011
Apparently a(n+1) is the number of 3D tilings of a 2 X 2 X n room with bricks of 1 X 2 X 2 shape. - R. J. Mathar, Dec 06 2013
The ratio a(n+1)/a(n) converges to 4 as n approaches infinity. - Felix P. Muga II, Mar 10 2014

M. Gardner, Riddles of the Sphinx, New Mathematical Library, M.A.A., 1987, p. 145. Math. Rev. 89i:00015.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
T. Hoeholdt, H. E. Jensen, and J. Justesen, Aperiodic correlations and the merit factor of a class of binary sequences, IEEE Trans. Inform. Theory, 13 (1985), 549-552
R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 7.
F. P. Muga II, Extending the Golden Ratio and the Binet-de Moivre Formula, March 2014; Preprint on ResearchGate.
Eric Weisstein's World of Mathematics, Octahedral Graph
Index entries for linear recurrences with constant coefficients, signature (2,8).

Cf. A001045, A003674, A011782, A054881, A192232, A192382, A238801.

[2^(n-1)*(2^n - (-1)^n)/3: n in [0..30]]; // Vincenzo Librandi, Aug 19 2011

A003683:=n->2^(n-1)*(2^n - (-1)^n)/3; seq(A003683(n), n=0..50); # Wesley Ivan Hurt, Dec 06 2013

Table[2^(n-1) (2^n-(-1)^n)/3,{n,0,30}] (* or *) LinearRecurrence[{2,8},{0,1},30] (* Harvey P. Dale, Sep 15 2013 *)

PARI
```
a(n)=if(n<0,0,2^(n-1)*(2^n-(-1)^n)/3)
```

a(n)=(2^n-(-1)^n)<<(n-1)/3 \\ Charles R Greathouse IV, Apr 17 2012

[lucas_number1(n,2,-8) for n in range(0, 24)] # Zerinvary Lajos, Apr 22 2009

a(n) = A003674(n)/3.
a(n) = 2*a(n-1) + 8*a(n-2), with a(0)=0, a(1)=1. - Barry E. Williams, Jan 04 2000
G.f.: x/((1+2*x)*(1-4*x)).
a(n) = ((1+3)^n-(1-3)^n)/6. - Paul Barry, May 14 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k+1)*9^k. - Paul Barry, May 20 2003
E.g.f.: exp(x)*sinh(3*x)/3. - Paul Barry, Jul 09 2003
a(n+1) = 2^n*A001045(n+1). - R. J. Mathar, Jul 08 2009
a(n+1) = Sum_{k=0..n} A238801(n,k)*3^k. - Philippe Deléham, Mar 07 2014

Erroneous references to spanning trees in K_2 X P_n deleted by Frans Faase, Feb 07 2009

A103435 a(n) = 2^n * Fibonacci(n).

Original entry on oeis.org

0, 2, 4, 16, 48, 160, 512, 1664, 5376, 17408, 56320, 182272, 589824, 1908736, 6176768, 19988480, 64684032, 209321984, 677380096, 2192048128, 7093616640, 22955425792, 74285318144, 240392339456, 777925951488, 2517421260800

Offset: 0

Ralf Stephan, Feb 08 2005

Cardinality of set of bracelets of size at most n that are tiled with two types of colored squares and four types of colored dominoes.
a(n) is also the diagonal element of the matrix A(i,j) whose first row (i=1) and first column (j=1) are the Fibonacci numbers: A(1,k)=A(k,1)=fib(k) and whose generic element is the sum of element in adjacent (preceding) row and column minus the absolute value of their difference. So a(n) = A(n,n) = A(i-1,j)+A(i,j-1)-abs(A(i-1,j)-A(i,j-1)). - Carmine Suriano, May 13 2010
a(n) is the coefficient of x in the reduction by x^2->x+1 of the polynomial p(n,x) given for d=sqrt(x+1) by p(n,x)=((x+d)^n-(x-d)^n)/(2d), for n>=1.  The constant terms under this reduction are the absolute values of terms of A086344.  See A192232 for a discussion of reduction. - Clark Kimberling, Jun 29 2011
The exponential convolution of A000032 and A000045. - Vladimir Reshetnikov, Oct 06 2016

			a(5)=160=A(5,5)=A(4,5)+A(5,4)-abs[A(4,5)+A(5,4)]=80+80-0. - _Carmine Suriano_, May 13 2010
G.f. = 2*x + 4*x^2 + 16*x^3 + 48*x^4 + 160*x^5 + 512*x^6 + 1664*x^7 + ...

Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, identity 236, p. 131.

Tom Edgar, Extending Some Fibonacci-Lucas Relations, The Fibonacci Quarterly, Vol. 54, No. 1 (2016), p. 79.
Harris Kwong, An Alternate Proof of Sury's Fibonacci-Lucas Relation, The American Mathematical Monthly, Vol. 121, No. 6 (2014), p. 514.
Diego Marques, A new Fibonacci-Lucas relation, Amer. Math. Monthly, Vol. 122, No. 7 (2015), p. 683.
Ivica Martinjak and Helmut Prodinger, Complementary Families of the Fibonacci-Lucas Relations, arXiv:1508.04949 [math.CO], 2015-2016.
B. Sury, A polynomial parent to a Fibonacci-Lucas relations, Amer. Math. Monthly, Vol. 121, No. 3 (2014), p. 236.
Charles R. Wall, Problem B-607, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 25, No. 4 (1987), p. 370; Product of Exponential Generating Functions, Solution to Problem B-607 by Bob Prielipp, ibid., Vol. 26, No. 4 (1988), pp. 374-375.
Index entries for linear recurrences with constant coefficients, signature (2,4).

First differences of A014334.
Partial sums of A087131.
Cf. A000032, A000045, A006483, A063727, A085449, A269991.

[2^n *Fibonacci(n): n in [0..50]]; // Vincenzo Librandi, Apr 04 2011

Expand[Table[((1 + Sqrt[5])^n - (1 - Sqrt[5])^n)5/(5 Sqrt[5]), {n, 0, 25}]] (* Zerinvary Lajos, Mar 22 2007 *)
Table[2^n Fibonacci[n],{n,0,40}] (* or *) LinearRecurrence[{2,4},{0,2},40] (* Harvey P. Dale, Oct 14 2020 *)

a(n)=fibonacci(n)<Charles R Greathouse IV, Feb 03 2014

concat(0, Vec(2*x/(1-2*x-4*x^2) + O(x^99))) \\ Altug Alkan, May 11 2016

a(n) = A006483(n) + 1 = 2*A085449(n) = 2*A063727(n-1), n>0.
G.f.: 2*x / (1 - 2*x - 4*x^2).
a(n) = Sum_{i=0..n-1}( 2^i * Lucas(i) ).
a(n) = 2*a(n-1) + 4*a(n-2). - Carmine Suriano, May 13 2010
a(n) = a(-n) * -(-4)^n for all n in Z. - Michael Somos, Sep 20 2014
E.g.f.: 2*sinh(sqrt(5)*x)*exp(x)/sqrt(5). - Ilya Gutkovskiy, May 10 2016
Sum_{n>=1} 1/a(n) = (1/2) * A269991. - Amiram Eldar, Nov 17 2020
a(n) == 2*n (mod 10). - Amiram Eldar, Jan 15 2022
a(n) = Sum_{k=0..n} binomial(n,k) * Fibonacci(k) * Lucas(n-k) (Wall, 1987). - Amiram Eldar, Jan 27 2022

A192616 Constant term in the reduction of the n-th Fibonacci polynomial by x^3->x^2+x+1. See Comments.

Original entry on oeis.org

1, 0, 1, 1, 2, 6, 10, 29, 57, 142, 309, 720, 1625, 3714, 8457, 19259, 43902, 99970, 227830, 518943, 1182401, 2693624, 6136837, 13980960, 31851853, 72565704, 165320833, 376638417, 858066430, 1954869262, 4453630790, 10146374277, 23115721705

Offset: 1

Clark Kimberling, Jul 09 2011

For discussions of polynomial reduction, see A192232 and A192744.

			The first five polynomials p(n,x) and their reductions:
F1(x)=1 -> 1
F2(x)=x -> x
F3(x)=x^2+1 -> x^2+1
F4(x)=x^3+2x -> x^2+3x+1
F5(x)=x^4+3x^2+1 -> 4x^2+2x+2, so that
A192616=(1,0,1,1,2,...), A192617=(0,1,0,3,2,...), A192651=(0,0,1,1,5,...)

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

Cf. A192744, A192232, A192617, A192651.

q = x^3; s = x^2 + x + 1; z = 40;
p[n_, x_] := Fibonacci[n, x];
Table[Expand[p[n, x]], {n, 1, 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, 1, z}];
u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}]
  (* A192616 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
  (* A192617 *)
u3 = Table[Coefficient[Part[t, n], x, 2], {n, 1, z}]
  (* A192651 *)

a(n) = a(n-1)+4*a(n-2)-a(n-3)-4a(n-4)+a(n-5)+a(n-6).

G.f.: -x*(x^4+x^3-3*x^2-x+1)/(x^6+x^5-4*x^4-x^3+4*x^2+x-1). [Colin Barker, Jul 27 2012]

A051450 Number of positive rational knots with 2n+1 crossings.

Original entry on oeis.org

1, 2, 5, 12, 30, 76, 195, 504, 1309, 3410, 8900, 23256, 60813, 159094, 416325, 1089648, 2852242, 7466468, 19546175, 51170460, 133962621, 350713222, 918170280, 2403786672, 6293172025, 16475700746, 43133883845, 112925875764

Offset: 1

Alexander Stoimenow (stoimeno(AT)math.toronto.edu)

The number of positive rational knots with even crossing number is zero.

a(n) = (1/2)*(coefficient of x in the reduction by x^2->x+1 of the polynomial p(n,x) = 1+x^n+x^(2n)); see A192464. Reductions of polynomials by substitutions such as x^2->x+1 are introduced at A192232. - Clark Kimberling, Jul 01 2011

			a(4) = 12 because we have 12 positive rational knots with 9 crossings: 9_1 to 9_7, 9_9, 9_10, 9_13, 9_18 and 9_23 (in Alexander-Briggs notation).

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (4,-3,-2,1).

Cf. A000045.

[(Fibonacci(2*n)+Fibonacci(n))/2: n in [1..30]]; // Vincenzo Librandi, Nov 01 2014

A051450 := proc(n)
    (combinat[fibonacci](n)+combinat[fibonacci](2*n))/2 ;
end proc:
seq(A051450(n),n=1..10) ; # R. J. Mathar, Nov 02 2021

LinearRecurrence[{4, -3, -2, 1}, {1, 2, 5, 12}, 30] (* Jean-François Alcover, Aug 28 2023 *)

Vec(x*(2*x-1)/((x^2-3*x+1)*(x^2+x-1)) + O(x^100)) \\ Colin Barker, Nov 01 2014

G.f. (version 1): -x + (x/2)*(1/(1-x/(4*(1-x)^2) + x/(4*(1+x)^2)) + 1/(1-x^2/(1-x^4))).
G.f. (version 2): x*(1-2*x)/((1-x-x^2)*(1-3*x+x^2)). - N. J. A. Sloane, Jan 21 2001
Binomial transform of Fibonacci(n)*(1-(-1)^n)/2. Binomial transform of (Fibonacci(n) + Fibonacci(-n))/2. - Paul Barry, Apr 23 2004
Let phi be the golden ratio (1+sqrt(5))/2. Then a(n)= (phi^n - (-phi)^(-n) + (1+phi)^n - (1+phi)^(-n))/(2*sqrt(5)) or a(n) = floor((1 + phi^n + (1+phi)^n)/(2*sqrt(5))). - Herbert Kociemba, May 12 2004
Also, number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| <= 1 for i = 1, 2, ..., n, s(0) = 1, s(n) = 2. a(n) = (2/5)*Sum_{k=1..4} sin(Pi*k/5)*sin(2*Pi*k/5)*(1+2*cos(Pi*k/5))^n. - Herbert Kociemba, Jun 07 2004
a(n) = (Fibonacci(2*n) + Fibonacci(n))/2. - Vladeta Jovovic, Jul 17 2004
Convolution of F(n) and F(2n-1). a(n) = Sum_{k=0..n} F(2k-1)*F(n-k). - Paul Barry, Jul 26 2004
a(n) = 4*a(n-1) - 3*a(n-2) - 2*a(n-3) + a(n-4). - Colin Barker, Nov 01 2014

More terms from James Sellers, Dec 09 1999

A265752 a(n) = A007814(A265399(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Dec 15 2015

nonn

a(n) is the constant term of the reduction by 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 of the encoding).

Completely additive with a(prime(k)) = F(k-2), where F(k) denotes the k-th Fibonacci number, A000045(k) for k >= 0, or A039834(-k) for k <= 0. - Peter Munn, Apr 05 2021, incorporating comment by Antti Karttunen, Dec 15 2015

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

Cf. A007814, A192232, A192750, A206296, A265399, A265750, A265753.

Cf. also A000040, A000045/A039834.

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

(define (A265752 n) (A007814 (A265399 n)))

a(n) = A007814(A265399(n)).
Other identities. For all n >= 1:
a(A000040(n+1)) = A000045(n-1). [Generalized by Peter Munn, Apr 05 2021]
a(A206296(n)) = A192232(n).
a(A265750(n)) = A192750(n).

A112576 A Chebyshev-related transform of the Fibonacci numbers.

Original entry on oeis.org

0, 1, 1, 4, 6, 16, 29, 67, 132, 288, 588, 1253, 2597, 5480, 11430, 24020, 50233, 105383, 220632, 462528, 968808, 2030377, 4253641, 8913436, 18675174, 39131464, 81989909, 171795691, 359958780, 754224480, 1580315220, 3311234189

Offset: 0

Paul Barry, Sep 14 2005

Transform of the Fibonacci numbers by the Chebyshev related transform which maps g(x) -> (1/(1-x^2))g(x/(1-x^2)).

G. C. Greubel, Table of n, a(n) for n = 0..1000
D. Huylebrouck, The Meta-Golden Ratio Chi, Proceedings of Bridges 2014: Mathematics, Music, Art, Architecture, Culture.
Index entries for linear recurrences with constant coefficients, signature (1,3,-1,-1).

Cf. A011973, A192232.

a:=[0,1,1,4];; for n in [5..40] do a[n]:=a[n-1]+3*a[n-2]-a[n-3] -a[n-4]; od; a; # G. C. Greubel, Jul 29 2019

R:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x/(1-x-3*x^2+x^3+x^4) )); // G. C. Greubel, Jul 29 2019

(* see A192232 for Mmca code. - M. F. Hasler, Apr 05 2016 *)
LinearRecurrence[{1,3,-1,-1},{0,1,1,4},40] (* Harvey P. Dale, May 09 2025 *)

Vec(x/(1-x-3*x^2+x^3+x^4)+O(x^40)) \\ M. F. Hasler, Apr 05 2016

(x/(1-x-3*x^2+x^3+x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Jul 29 2019

G.f.: x/(1-x-3*x^2+x^3+x^4).
a(n) = Sum_{k=0..floor(n/2)} C(n-k, k)*F(n-2*k).
a(n) = Sum_{k=0..n} C((n+k)/2, k)*(1+(-1)^(n-k))*F(k)/2.
a(n) = (Fibonacci(n+1, (1+sqrt(5))/2) - Fibonacci(n+1, (1-sqrt(5))/2) )/sqrt(5), where Fibonacci(n,x) is the Fibonacci polynomial (see A011973). - G. C. Greubel, Jul 29 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Magma

Mathematica

PARI

PARI

Sage

Formula

A193010 Decimal expansion of the constant term of the reduction of e^x by x^2->x+1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A003683 a(n) = 2^(n-1)*(2^n - (-1)^n)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A103435 a(n) = 2^n * Fibonacci(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs