Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #36 Oct 12 2022 16:20:51
%S 1,1,9,9,49,81,281,601,1729,4129,11049,27561,71761,182001,469049,
%T 1197049,3073249,7861441,20154441,51600201,132217969,338618769,
%U 867490649,2221965721,5691928321,14579791201,37347504489,95666669289,245056687249,627723364401
%N Length of n-th string generated by a Kolakoski(9,1) rule starting with a(1)=1.
%C Each string is derived from the previous string using the Kolakoski(9,1) rule and the additional condition: "string begins with 1 if previous string ends with 9 and vice versa". The strings are 1 -> 9 -> 111111111 -> 919191919 -> 11111111191111111119... -> ... and each one contains 1,1,9,9,31,... elements.
%H Reinhard Zumkeller, <a href="/A095344/b095344.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,5,4).
%F a(1) = a(2) = 1; for n>1, a(n) = a(n-1) + 4*a(n-2) - 4*(-1)^n.
%F G.f.: x*(1 + x + 4*x^2)/((1 + x)*(1 - x - 4*x^2)). - _Colin Barker_, Mar 25 2012
%F a(n) = 5*a(n-2) + 4*a(n-3). - _Colin Barker_, Mar 25 2012
%F a(n) = 2*(-1)^n + (2^(-1-n)*(-(-7+sqrt(17))*(1+sqrt(17))^n - (1-sqrt(17))^n*(7+sqrt(17))))/sqrt(17). - _Colin Barker_, Apr 20 2016
%F a(n) = 2*(-1)^n - 2^n*(Fibonacci(n+1, 1/2) - 2*Fibonacci(n, 1/2)) = 2*(-1)^n - (2/I)^n*(ChebyshevU(n, I/4) - 2*I*ChebyshevU(n-1, I/4)). - _G. C. Greubel_, Dec 26 2019
%p seq(simplify(2*(-1)^n -(2/I)^n*(ChebyshevU(n, I/4) -2*I*ChebyshevU(n-1, I/4)) ), n = 1..35); # _G. C. Greubel_, Dec 26 2019
%t Table[2*(-1)^n - 2^n*(Fibonacci[n+1, 1/2] - 2*Fibonacci[n, 1/2]), {n,35}] (* _G. C. Greubel_, Dec 26 2019 *)
%t LinearRecurrence[{0,5,4},{1,1,9},40] (* _Harvey P. Dale_, Oct 12 2022 *)
%o (Haskell)
%o a095344 n = a095344_list !! (n-1)
%o a095344_list = tail xs where
%o xs = 1 : 1 : 1 : zipWith (-) (map (* 5) $ zipWith (+) (tail xs) xs) xs
%o -- _Reinhard Zumkeller_, Aug 16 2013
%o (PARI) Vec(x*(1+x+4*x^2)/((1+x)*(1-x-4*x^2)) + O(x^50)) \\ _Colin Barker_, Apr 20 2016
%o (PARI) vector(35, n, round( 2*(-1)^n - (2/I)^n*(polchebyshev(n, 2, I/4) -2*I*polchebyshev(n-1, 2, I/4)) )) \\ _G. C. Greubel_, Dec 26 2019
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 35); Coefficients(R!( x*(1+x+ 4*x^2)/((1+x)*(1-x-4*x^2)) )); // _G. C. Greubel_, Dec 26 2019
%o (Sage)
%o def A095344_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( x*(1+x+4*x^2)/((1+x)*(1-x-4*x^2)) ).list()
%o a=A095344_list(35); a[1:] # _G. C. Greubel_, Dec 26 2019
%o (GAP) a:=[1,1,9];; for n in [4..35] do a[n]:=5*a[n-2]+4*a[n-3]; od; a; # _G. C. Greubel_, Dec 26 2019
%Y Cf. A000002, A066983, A095342, A095343.
%Y Cf. A123270, A090390.
%K nonn,easy
%O 1,3
%A _Benoit Cloitre_, Jun 03 2004