login
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.
8
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
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.
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
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
KEYWORD
nonn,easy
AUTHOR
R. K. Guy, Mar 23 2008
STATUS
approved