A203976 a(n) = 3*a(n-2) - a(n-4), a(0)=0, a(1)=1, a(2)=5, a(3)=4.

0, 1, 5, 4, 15, 11, 40, 29, 105, 76, 275, 199, 720, 521, 1885, 1364, 4935, 3571, 12920, 9349, 33825, 24476, 88555, 64079, 231840, 167761, 606965, 439204, 1589055, 1149851, 4160200, 3010349, 10891545, 7881196, 28514435, 20633239, 74651760, 54018521, 195440845

Offset: 0

Author

Michael Somos, Jan 08 2012

Keywords

• nonn
• easy

Comments

a(n+1) = p(n+2) where p(x) is the unique degree-n polynomial such that p(k) = Lucas(k) for k = 1, ..., n+1.

This is a divisibility sequence; that is, if n divides m, then a(n) divides a(m).

a(n) = row sums of triangle A226377(n), based on differences among Lucas Numbers. - Richard R. Forberg, Aug 01 2013

A strong divisibility sequence, i.e., gcd(a(n),a(m)) = a(gcd(n,m)) for all natural numbers n and m. The sequence of convergents of the 2-periodic continued fraction [0; 1, -5, 1, -5, ...] = 1/(1 - 1/(5 - 1/(1 - 1/(5 - ...)))) = 1/2*(5 - sqrt(5)) begins [0/1, 1/1, 5/4, 4/3, 15/11, 11/8, 40/29,...]. The present sequence is the sequence of numerators; the sequence of denominators [1, 1, 4, 3, 11, 8, 29,...] is A005013. - Peter Bala, May 19 2014

It appears that the first homology group of the branched n-th cyclic covering of the group of figure-eight knot is the direct sum of cyclic groups of orders a(n) and A005013(n), so the order of that group is the product of these numbers, i. e. A004146(n); see the table on p. 156 of the paper by Fox. - Andrey Zabolotskiy, Mar 16 2023

Examples

			a(3) = 4 since p(x) = (-x^2 + 7*x - 4) / 2 interpolates p(1) = 1, p(2) = 3, p(3) = 4, and p(4) = 4.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• R. H. Fox, A quick trip through knot theory, pages 120-167 in: Topology of 3-manifolds and related topics (Proceedings of The University of Georgia Institute, 1961), Prentice-Hall, 1962.
• Index to divisibility sequences
• Index entries for linear recurrences with constant coefficients, signature (0,3,0,-1).

Crossrefs

Cf. A000032, A000045, A201157 (bisection), A002878 (bisection). A005013.

Programs

Haskell

a203976 n = a203976_list !! n
a203976_list = 0 : 1 : 5 : 4 : zipWith (-)
   (map (* 3) $ drop 2 a203976_list) a203976_list
-- Reinhard Zumkeller, Jan 10 2012

Magma

I:=[0,1,5,4]; [n le 4 select I[n] else 3*Self(n-2)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Mar 29 2016

Mathematica

LinearRecurrence[{0,3,0,-1},{0,1,5,4},40] (* Harvey P. Dale, Apr 06 2013 *)

PARI

{a(n) = if( n%2, fibonacci(n+1) + fibonacci(n-1), 5 * fibonacci(n))}

PARI

{a(n) = if( n<0, -a(-n), polcoeff( x * (1 + 5*x + x^2) / (1 - 3*x^2 + x^4) + x * O(x^n), n))}

PARI

{a(n) = if( n<0, -a(-n), subst( polinterpolate( vector( n, k, fibonacci(k-1) + fibonacci(k+1) )), x, n + 1))}

Formula

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

G.f.: x * (1 + 5*x + x^2) / ( (x^2+x-1)*(x^2-x-1) ).

a(2*n) = 5 * A000045(2*n) (Fibonacci). a(2*n+1) = A000032(2*n+1) (Lucas).

a(A004277(n)) = A054888(n+1). - Reinhard Zumkeller, Jan 11 2012

a(n) = A000032(n+1) - A061084(n). - R. J. Mathar, Jun 23 2013

a(2n) = a(2n-1) + a(2n+1), for n>0. - Richard R. Forberg, Aug 01 2013

a(n) = (2^(-1-n)*((-5-sqrt(5)+(-1)^n*(-5+sqrt(5)))*((-1+sqrt(5))^n-(1+sqrt(5))^n)))/sqrt(5). - Colin Barker, Mar 28 2016

E.g.f.: exp(-phi*x)*(exp(x) - 1)*(phi*exp(sqrt(5)*x) - 1/phi), where phi = (1 + sqrt(5))/2. - G. C. Greubel, Mar 28 2016