%I #59 Feb 12 2022 14:55:34

%S 1,1,10,28,136,496,2080,8128,32896,130816,524800,2096128,8390656,

%T 33550336,134225920,536854528,2147516416,8589869056,34359869440,

%U 137438691328,549756338176,2199022206976,8796095119360,35184367894528,140737496743936,562949936644096,2251799847239680

%N a(n) = 2^(n-1)*( 2^n + (-1)^n ).

%C Binomial transform of expansion of cosh(3*x), the aerated version of A001019, 1,0,9,0,81,0,729,... - _Paul Barry_, Apr 05 2003

%C Alternatively: start with the fraction 1/1, take the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 9 times the bottom to get the new top. The limit of the sequence of fractions used to generate this sequence is sqrt(9). - _Cino Hilliard_, Sep 25 2005

%C This sequence also gives the number of ordered pairs of subsets (A, B) of {1, 2, ..., n} such that |A u B| is even. (Here "u" stands for the set-theoretic union.) The special case n = 13 can be found as in CRUX Problem 3257. - Walther Janous (walther.janous(AT)tirol.com), Mar 01 2008

%C For n > 0, a(n) is term (1,1) in the n-th power of the 2 X 2 matrix [1,3; 3,1]. - _Gary W. Adamson_, Aug 06 2010

%C a(n) is the number of compositions of n when there are 1 type of 1 and 9 types of other natural numbers. - _Milan Janjic_, Aug 13 2010

%C a(n) = ((1+3)^n+(1-3)^n)/2. In general, if b(0),b(1),... is the k-th binomial transform of the sequence ((3^n+(-3)^n)/2), then b(n) = ((k+3)^n+(k-3)^n)/2. More generally, if b(0),b(1),... is the k-th binomial transform of the sequence ((m^n+(-m)^n)/2), then b(n) = ((k+m)^n+(k-m)^n)/2. See A034494, A081340-A081342, A034659. - _Charlie Marion_, Jun 25 2011

%C Pisano period lengths: 1, 1, 1, 1, 4, 1, 6, 1, 1, 4, 5, 1, 12, 6, 4, 1, 8, 1, 9, 4, ... - _R. J. Mathar_, Aug 10 2012

%C Starting with offset 1 the sequence is the INVERT transform of (1, 9, 9, 9, ...). - _Gary W. Adamson_, Aug 06 2016

%D John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, p. 16.

%D M. Gardner, Riddles of Sphinx, M.A.A., 1987, p. 145.

%H Vincenzo Librandi, <a href="/A003665/b003665.txt">Table of n, a(n) for n = 0..1000</a>

%H R. K. Guy, <a href="/A007300/a007300.pdf">s-Additive sequences</a>, Preprint, 1994. (Annotated scanned copy)

%H Bill Sands, <a href="https://cms.math.ca/crux/v33/n5/page297-301.pdf">Problem 3257</a>, Crux Math. 33 (2007), No.5, p. 298.

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

%F From _Paul Barry_, Mar 01 2003: (Start)

%F a(n) = 2*a(n-1) + 8*a(n-2), a(0)=a(1)=1.

%F a(n) = (4^n + (-2)^n)/2.

%F G.f.: (1-x)/((1+2*x)*(1-4*x)). (End)

%F From _Paul Barry_, Apr 05 2003: (Start)

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*9^k.

%F E.g.f. exp(x)*cosh(3*x). (End)

%F a(n) = (A078008(n) + A001045(n+1))*2^(n-1) = A014551(n)*2^(n-1). - _Paul Barry_, Feb 12 2004

%F Given a(0)=1, b(0)=1 then for i=1, 2, ..., a(i)/b(i) = (a(i-1) + 9*b(i-1)) / (a(i-1) + b(i-1)). - _Cino Hilliard_, Sep 25 2005

%F a(n) = Sum_{k=0..n} A098158(n,k)*9^(n-k). - _Philippe Deléham_, Dec 26 2007

%F a(n) = ((1+sqrt(9))^n + (1-sqrt(9))^n)/2. - Al Hakanson (hawkuu(AT)gmail.com), Dec 08 2008

%F If p[1]=1, and p[i]=9, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det(A). - _Milan Janjic_, Apr 29 2010

%F G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(9*k-1)/(x*(9*k+8) - 1/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 28 2013

%p A003665:=n->2^(n-1)*( 2^n + (-1)^n ): seq(A003665(n), n=0..30); # _Wesley Ivan Hurt_, Apr 28 2017

%t CoefficientList[Series[(1+8x)/(1-2x-8x^2), {x,0,30}], x] (* or *)

%t LinearRecurrence[{2,8}, {1,1}, 30] (* _Robert G. Wilson v_, Sep 18 2013 *)

%o (PARI) a(n)=2^(n-1)*( 2^n + (-1)^n );

%o (Magma) [2^(n-1)*( 2^n + (-1)^n ): n in [0..30]]; // _Vincenzo Librandi_, Aug 19 2011

%o (Sage) [2^(n-1)*(2^n +(-1)^n) for n in (0..30)] # _G. C. Greubel_, Aug 02 2019

%o (GAP) List([0..30], n-> 2^(n-1)*(2^n +(-1)^n)); # _G. C. Greubel_, Aug 02 2019

%Y Cf. A001019, A001045, A014551, A078008, A098158.

%Y Cf. A034494, A081340-A081342, A034659.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E Entry revised by _N. J. A. Sloane_, Nov 22 2006