A116201 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4); a(0)=0, a(1)=1, a(2)=1, a(3)=1.

0, 1, 1, 1, 3, 4, 7, 13, 21, 37, 64, 109, 189, 325, 559, 964, 1659, 2857, 4921, 8473, 14592, 25129, 43273, 74521, 128331, 220996, 380575, 655381, 1128621, 1943581, 3347008, 5763829, 9925797, 17093053, 29435671, 50690692, 87293619, 150326929, 258875569

Offset

0,5

Comments

This is a divisibility sequence; that is, if n divides m then a(n) divides a(m). - T. D. Noe, Dec 22 2008

This is the case P1 = 1, P2 = -3, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014

Also, the inverse radii of a family of spheres defined as follows: the first three spheres have radius of 1 and touch each other and the common plane, while each subsequent sphere touches the three immediately preceding ones and the same plane. - Ivan Neretin, Sep 11 2018

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

A. D. Mednykh, I. A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, arXiv preprint arXiv:1711.00175 [math.CO], 2017. See Section 4.

Wikipedia, Soddy-Gosset theorem.

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

H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume

Index to divisibility sequences

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

Formula

From R. J. Mathar, Mar 31 2008: (Start)

O.g.f: -x*(x-1)*(x+1)/(1 - x - x^2 - x^3 + x^4).

a(n) = A135431(n) - A135431(n-1). (End)

From Peter Bala, Mar 31 2014: (Start)

a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (1 + sqrt(13))/4 and beta = (1 - sqrt(13))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.

a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 3/4; 1, 1/2].

a(n) = U(n-1,(sqrt(3) + i)/4)*U(n-1,(sqrt(3) - i)/4), where U(n,x) denotes the Chebyshev polynomial of the second kind.

See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)

a(n) = a(-n) = A116732(n+2) - A116732(n), 0 = a(n) - 2*a(n+1) + 2*a(n+4) - a(n+5) for all n in Z. - Michael Somos, Feb 26 2019

Example

G.f. = x + x^2 + x^3 + 3*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + 21*x^8 + ... - Michael Somos, Feb 26 2019

Maple

a[0]:=0: a[1]:=1: a[2]:=1: a[3]:=1: for n from 4 to 35 do a[n]:= a[n-1]+a[n-2]+a[n-3]-a[n-4] end do: seq(a[n], n=0..35); # Emeric Deutsch, Apr 12 2008

Mathematica

a = {0, 1, 1, 1, 3}; Do[AppendTo[a, a[[ -1]]+a[[ -2]]+a[[ -3]]-a[[ -4]]], {80}]; a (* Stefan Steinerberger, Mar 24 2008 *)
CoefficientList[Series[(- x^3 + x)/(x^4 - x^3 - x^2 - x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Apr 02 2014 *)
a[ n_] := 1 - SeriesCoefficient[ (1 - 2 x) / (1 - 2 x + 2 x^4 - x^5), {x, 0, Abs@n}]; (* Michael Somos, Feb 26 2019 *)
LinearRecurrence[{1, 1, 1, -1}, {0, 1, 1, 1}, 50] (* Harvey P. Dale, Mar 26 2019 *)

Prog

(PARI) {a(n) = n=abs(n); 1 - polcoeff( (1 - 2*x) / (1 - 2*x + 2*x^4 - x^5) + x * O(x^n), n)}; /* Michael Somos, Feb 26 2019 */

Crossrefs

Cf. A100047, A116732, A135431.

Sequence in context: A125118 A310008 A299024 * A280224 A282718 A092406

Adjacent sequences: A116198 A116199 A116200 * A116202 A116203 A116204

Keyword

nonn,easy

Author

R. K. Guy, Mar 23 2008

Status

approved