cp's OEIS Frontend

A215885 a(n) = 3*a(n-1) - a(n-3), with a(0) = 3, a(1) = 3, and a(2) = 9.

%I A215885 #96 Aug 07 2025 04:38:33
%S A215885 3,3,9,24,69,198,570,1641,4725,13605,39174,112797,324786,935184,
%T A215885 2692755,7753479,22325253,64283004,185095533,532961346,1534601034,
%U A215885 4418707569,12723161361,36634883049,105485941578,303734663373,874569107070,2518221379632,7250929475523
%N A215885 a(n) = 3*a(n-1) - a(n-3), with a(0) = 3, a(1) = 3, and a(2) = 9.
%C A215885 The Berndt-type sequence number 5a for the argument 2Pi/9 defined by the first relation from the section "Formula". We see that a(n) is equal to the sum of the n-th negative powers of the c(j) := 2*cos(2*Pi*j/9), j=1,2,4 (the A215664(n) is equal to the respective n-th positive powers, further both sequences can be obtained from the two-sided recurrence relation: X(n+3) = 3*X(n+1) - X(n), n in Z, with X(-1) = X(0) = 3, and X(1) = 0).
%C A215885 From the last formula in Witula's comments to A215664 it follows that 2*(-1)^n*a(n) = A215664(n)^2 - A215664(2*n).
%C A215885 The following decomposition holds true: (X - c(1)^(-n))*(X - c(2)^(-n))*(X - c(4)^(-n)) = X^3 - a(n)*X^2 - (-1)^n*A215664(n)*X - (-1)^n.
%C A215885 For n >= 1, a(n) is the number of cyclic (0,1,2)-compositions of n that avoid the pattern 110 provided the positions of the parts of the composition on the circle are fixed. (Similar comments hold for the pattern 012 and for the pattern 001.) - _Petros Hadjicostas_, Sep 13 2017
%C A215885 See the Maple program by Edlin and Zeilberger for counting the q-ary cyclic compositions of n that avoid one or more patterns provided the positions of the parts of the composition are fixed on the circle. The program is located at D. Zeilberger's personal website (see links). For the sequence here, q=3 and the pattern is A=110. - _Petros Hadjicostas_, Sep 13 2017
%H A215885 Michael De Vlieger, <a href="/A215885/b215885.txt">Table of n, a(n) for n = 0..1999</a>
%H A215885 A. E. Edlin and D. Zeilberger, <a href="https://doi.org/10.1006/aama.2000.0696">The Goulden-Jackson cluster method for cyclic words</a>, Adv. Appl. Math. 25 (2000), 228-232.
%H A215885 A. E. Edlin and D. Zeilberger, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/CGJ">Maple program</a>; <a href="/A215885/a215885.txt">Local copy</a>
%H A215885 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 A215885 Roman Witula, <a href="https://doi.org/10.1515/dema-2013-0418">Ramanujan Type Trigonometric Formulae</a>, Demonstratio Math. 45 (2012), 779-796.
%H A215885 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-1).
%F A215885 a(n) = 3*A147704(n).
%F A215885 a(n) = c(1)^(-n) + c(2)^(-n) + c(4)^(-n) = (-c(1)*c(2))^n + (-c(1)*c(4))^n + (-c(2)*c(4))^n, where c(j) := 2*cos(2*Pi*j/9).
%F A215885 G.f.: Sum_{n>=0} a(n)*x^n = 3-3*x*(x^2-1)/(1-3*x+x^3) = 3*(1-2*x)/(1-3*x+x^3).
%F A215885 G.f. of Edlin and Zeilberger (2000): 1+Sum_{n>=1} a(n)*x^n = 1-3*x*(x^2-1)/(1-3*x+x^3) = (1-2*x^3)/(1-3*x+x^3). - _Petros Hadjicostas_, Sep 13 2017
%F A215885 a(n) = ceiling(r^n) for n >= 1, where r = 1/A130880 is the largest root of x^3 - 3*x^2 + 1. - _Tamas Lengyel_, Feb 20 2022
%e A215885 For n=3, we have a(3) = 3^3 - 3 = 24 ternary cyclic compositions of n=3 (with fixed positions on the circle for the parts) that avoid 110 because we have to exclude 110, 101, and 011. - _Petros Hadjicostas_, Sep 13 2017
%t A215885 LinearRecurrence[{3,0,-1}, {3,3,9}, 50]
%o A215885 (PARI) my(x='x+O('x^30)); Vec(3*(1-2*x)/(1-3*x+x^3)) \\ _Altug Alkan_, Sep 13 2017
%Y A215885 Cf. A130880, A147704, A215664, A215665, A215666, A274018.
%K A215885 nonn,easy
%O A215885 0,1
%A A215885 _Roman Witula_, Aug 25 2012