login
a(n) = a(n-1) + 2*a(n-2) - a(n-3), with a(0) = a(1) = 0, a(2) = 1.
(Formerly M2358)
41

%I M2358 #196 May 27 2023 11:31:33

%S 0,0,1,1,3,4,9,14,28,47,89,155,286,507,924,1652,2993,5373,9707,17460,

%T 31501,56714,102256,184183,331981,598091,1077870,1942071,3499720,

%U 6305992,11363361,20475625,36896355,66484244,119801329,215873462,388991876,700937471

%N a(n) = a(n-1) + 2*a(n-2) - a(n-3), with a(0) = a(1) = 0, a(2) = 1.

%C a(n+1) = S(n) for n>=1, where S(n) is the number of 01-words of length n, having first letter 1, in which all runlengths of 1's are odd. Example: S(4) counts 1000, 1001, 1010, 1110. See A077865. - _Clark Kimberling_, Jun 26 2004

%C For n>=1, number of compositions of n into floor(j/2) kinds of j's (see g.f.). - _Joerg Arndt_, Jul 06 2011

%C Counts walks of length n between the first and second nodes of P_3, to which a loop has been added at the end. Let A be the adjacency matrix of the graph P_3 with a loop added at the end. A is a 'reverse Jordan matrix' [0,0,1; 0,1,1; 1,1,0]. a(n) is obtained by taking the (1,2) element of A^n. - _Paul Barry_, Jul 16 2004

%C Interleaves A094790 and A094789. - _Paul Barry_, Oct 30 2004

%C a(n) appears in the formula for the nonnegative powers of rho:= 2*cos(Pi/7), the ratio of the smaller diagonal in the heptagon to the side length s=2*sin(Pi/7), when expressed in the basis <1,rho,sigma>, with sigma:=rho^2-1, the ratio of the larger heptagon diagonal to the side length, as follows. rho^n = C(n)*1 + C(n+1)*rho + a(n)*sigma, n>=0, with C(n) = A052547(n-2). See the Steinbach reference, and a comment under A052547. - _Wolfdieter Lang_, Nov 25 2010

%C If with the above notations the power basis <1,rho,rho^2> of Q(rho) is used, nonnegative powers of rho are given by rho^n = -a(n-1)*1 + A052547(n-1)*rho + a(n)*rho^2. For negative powers see A006054. - _Wolfdieter Lang_, May 06 2011

%C -a(n-1) also appears in the formula for the nonpositive powers of sigma (see the above comment for the definition, and the Steinbach basis <1,rho,sigma>) as follows: sigma^(-n) = A(n)*1 -a(n+1)*rho -A(n-1)*sigma, with A(n) = A052547(n), A(-1):=0. - _Wolfdieter Lang_, Nov 25 2010

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. Witula, E. Hetmaniok and D. Slota, Sums of the powers of any order roots taken from the roots of a given polynomial, Proceedings of the 15th International Conference on Fibonacci Numbers and Their Applications (2012).

%H Vincenzo Librandi, <a href="/A006053/b006053.txt">Table of n, a(n) for n = 0..200</a>

%H Robin Chapman and Nicholas C. Singer, <a href="http://www.jstor.org/stable/4145281">Eigenvalues of a bidiagonal matrix</a>, Amer. Math. Monthly, 111 (2004), p. 441

%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson: A Bijection of Corridor Paths</a>, arXiv:2006.06516 [math.CO], 2020.

%H Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, <a href="https://arxiv.org/abs/2210.12411">On a variant of Flory model</a>, arXiv:2210.12411 [math.CO], 2022.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=433">Encyclopedia of Combinatorial Structures 433</a>

%H László Németh and Dragan Stevanović, <a href="https://www.researchgate.net/publication/370765824_Graph_solution_of_system_of_recurrence_equations">Graph solution of system of recurrence equations</a>, Research Gate, 2023. See Table 2 at p. 6.

%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H R. Sachdeva and A. K. Agarwal, <a href="https://doi.org/10.1016/j.disc.2016.09.009">Combinatorics of certain restricted n-color composition functions</a>, Discrete Mathematics, 340, (2017), 361-372.

%H Genki Shibukawa, <a href="https://arxiv.org/abs/1907.00334">New identities for some symmetric polynomials and their applications</a>, arXiv:1907.00334 [math.CA], 2019.

%H P. Steinbach, <a href="http://www.jstor.org/stable/2691048">Golden fields: a case for the heptagon</a>, Math. Mag. 70 (1997), no. 1, 22-31.

%H Kai Wang, <a href="https://www.researchgate.net/publication/337943524_Fibonacci_Numbers_And_Trigonometric_Functions_Outline">Fibonacci Numbers And Trigonometric Functions Outline</a>, (2019).

%H Roman Witula, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Witula/witula17.html">Ramanujan Type Trigonometric Formulas: The General Form for the Argument 2Pi/7</a>, J. Integer Seq., 12 (2009), Article 09.8.5.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1).

%F G.f.: x^2/(1 - x - 2*x^2 + x^3). - _Emeric Deutsch_, Dec 14 2004

%F a(n) = c^(n-2) - a(n-1)*(c-1) + (1/c)*a(n-2) for n > 3 where c = 2*cos(Pi/7). Example: a(7) = 14 = c^5 - 9*(c-1) + 4/c = 18.997607... - 7.21743962... + 2.219832528... - _Gary W. Adamson_, Jan 24 2010

%F G.f.: -1 + 1/(1 - Sum_{j>=1} floor(j/2)*x^j). - _Joerg Arndt_, Jul 06 2011

%F a(n+2) = A094790(n/2+1)*(1+(-1)^n)/2 + A094789((n+1)/2)*(1-(-1)^n)/2. - _Paul Barry_, Oct 30 2004

%F First differences of A028495. - _Floor van Lamoen_, Nov 02 2005

%F a(n) = A187065(2*n+1); a(n+1) = A187066(2*n+1) = A187067(2*n). - _L. Edson Jeffery_, Mar 16 2011

%F a(n) = 2^n*(c(1)^(n-1)*(c(1)+c(2)) + c(3)^(n-1)*(c(3)+c(6)) + c(5)^(n-1)*(c(5)+c(4)) )/7, with c(j):=cos(Pi*j/7). - _Herbert Kociemba_, Dec 18 2011

%F a(n+1)*(-1)^n*49^(1/3) = (c(1)/c(4))^(1/3)*(2*c(1))^n + (c(2)/c(1))^(1/3)*(2*c(2))^n + (c(4)/c(2))^(1/3)*(2c(4))^n = (c(2)/c(1))^(1/3)*(2*c(1))^(n+1) + (c(4)/c(2))^(1/3)*(c(2))^(n+1) + (c(1)/c(4))^(1/3)*(2*c(4))^(n+1), where c(j) := cos(2Pi*j/7); for the proof, see Witula et al.'s papers. - _Roman Witula_, Jul 21 2012

%F The previous formula connects the sequence a(n) with A214683, A215076, A215100, A120757. We may call a(n) the Ramanujan-type sequence number 2 for the argument 2*Pi/7. - _Roman Witula_, Aug 02 2012

%F a(n) = -A006054(1-n) for all n in Z. - _Michael Somos_, Nov 30 2014

%F G.f.: x^2 / (1 - x / (1 - 2*x / (1 + 5*x / (2 - x / (5 - 2*x))))). - _Michael Somos_, Jan 20 2017

%F a(n) ~ r*c^n, where r=0.241717... is one of the roots of 49*x^3-7*x+1, and c=2*cos(Pi/7) (as in _Gary W. Adamson_'s formula). - _Daniel Checa_, Nov 04 2022

%F a(2n-1) = 2*a(n+1)*a(n) - a(n)^2 - a(n-1)^2. - _Richard Peterson_, May 25 2023

%e G.f. = x^2 + x^3 + 3*x^4 + 4*x^5 + 9*x^6 + 14*x^7 + 28*x^8 + 47*x^9 + ...

%e Regarding the description "number of compositions of n into floor(j/2) kinds of j's," the a(6)=9 compositions of 6 are (2a, 2a, 2a), (3a, 3a), (2a, 4a), (2a, 4b), (4a, 2a), (4b, 2a), (6a), (6b), (6c). - _Bridget Tenner_, Feb 25 2022

%p a[0]:=0: a[1]:=0: a[2]:=1: for n from 3 to 40 do a[n]:=a[n-1]+2*a[n-2]-a[n-3] od:seq(a[n], n=0..40); # _Emeric Deutsch_

%p A006053:=z**2/(1-z-2*z**2+z**3); # conjectured by _Simon Plouffe_ in his 1992 dissertation

%t LinearRecurrence[{1,2,-1}, {0,0,1}, 50] (* _Vladimir Joseph Stephan Orlovsky_, May 25 2011 *)

%o (Magma) [ n eq 1 select 0 else n eq 2 select 0 else n eq 3 select 1 else Self(n-1) +2*Self(n-2) -Self(n-3): n in [1..40] ]: // _Vincenzo Librandi_, Aug 19 2011

%o (Haskell)

%o a006053 n = a006053_list !! n

%o a006053_list = 0 : 0 : 1 : zipWith (+) (drop 2 a006053_list)

%o (zipWith (-) (map (2 *) $ tail a006053_list) a006053_list)

%o -- _Reinhard Zumkeller_, Oct 14 2011

%o (PARI) {a(n) = if( n<0, n = -1-n; polcoeff( -1 / (1 - 2*x - x^2 + x^3) + x * O(x^n), n), polcoeff( x^2 / (1 - x - 2*x^2 + x^3) + x * O(x^n), n))}; /* _Michael Somos_, Nov 30 2014 */

%o (SageMath)

%o @CachedFunction

%o def a(n): # a = A006053

%o if (n<3): return (n//2)

%o else: return a(n-1) + 2*a(n-2) - a(n-3)

%o [a(n) for n in range(41)] # _G. C. Greubel_, Feb 12 2023

%Y Cf. A006054, A052547, A077865, A094789, A094790, A096975, A096976.

%Y Cf. A120757, A187065, A187066, A187067, A214683, A215076, A215100.

%K nonn,easy

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _Emeric Deutsch_, Dec 14 2004

%E Typo in definition fixed by _Reinhard Zumkeller_, Oct 14 2011