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

0, 1, 1, 5, 7, 20, 35, 83, 161, 355, 720, 1541, 3185, 6733, 14027, 29500, 61663, 129403, 270865, 567911, 1189440, 2492905, 5222449, 10943813, 22928815, 48044900, 100665083, 210927155, 441948689, 926020171, 1940274000, 4065458669, 8518311809

Offset

0,4

Comments

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

Assuming the o.g.f. given below, this sequence is a divisibility sequence, i.e., a(n) divides a(m) whenever n divides m. It is the case P1 = 1, P2 = -1, Q = -1 of the 3-parameter family of 4th-order linear divisibility sequences found by Williams and Guy. Cf. A100047. - Peter Bala, Aug 28 2019

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.

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

Formula

From Colin Barker, May 12 2014: (Start)

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

G.f.: x*(1 + x^2)/(1 - x - 3*x^2 + x^3 + x^4). (End)

From Vladimir Kruchinin, Mar 20 2016: (Start)

G.f.: ((1+x^2)/(1-x^2)) * F(x/(1-x^2)), where F(x) is g.f. of Fibonacci numbers (A000045).

a(n) = n*Sum_{i=0..floor((n-1)/2)} (binomial(n-i-1,i)/(n-2*i))*Fibonacci(n-2*i). (End)

a(n) = Sum_{j=0..n} T(n, j)*Fibonacci(j), where T(n, k) = [x^k] ((x + sqrt(x^2+4))^n + (x - sqrt(x^2+4))^n)/2^n. - G. C. Greubel, Jul 11 2023

Example

The first five polynomials p(n,x) and their reductions are as follows:
  p(0,x) = 2 -> 2
  p(1,x) = x -> x
  p(2,x) = 2 + x^2 -> 3 + x
  p(3,x) = 3*x + x^3 -> 1 + 5*x
  p(4,x) = 2 + 4*x^2 + x^4 -> 8 + 7*x.
From these, read A192421 = (2, 0, 3, 1, 8, ...) and a(n) = (0, 1, 1, 5, 7, ...).

Mathematica

(See A192421.)
LinearRecurrence[{1, 3, -1, -1}, {0, 1, 1, 5}, 40] (* G. C. Greubel, Jul 11 2023 *)

Prog

(Maxima)
a(n):=n*sum((binomial(n-i-1, i))/(n-2*i)*fib(n-2*i), i, 0, (n-1)/2); /* Vladimir Kruchinin, Mar 20 2016 */
(Magma) R<x>:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1+x^2)/(1-x-3*x^2+x^3+x^4) )); // G. C. Greubel, Jul 11 2023
(SageMath)
@CachedFunction
def a(n): # a = A192422
    if (n<4): return (0, 1, 1, 5)[n]
    else: return a(n-1) +3*a(n-2) -a(n-3) -a(n-4)
[a(n) for n in range(41)] # G. C. Greubel, Jul 11 2023

Crossrefs

Cf. A000045, A100047, A192232, A192421.

Sequence in context: A279957 A249047 A258282 * A120035 A198302 A091154

Adjacent sequences: A192419 A192420 A192421 * A192423 A192424 A192425

Keyword

nonn

Author

Clark Kimberling, Jun 30 2011

Status

approved