%I M3359 #29 Sep 08 2022 08:44:35
%S 1,1,4,9,16,31,64,129,256,511,1024,2049,4096,8191,16384,32769,65536,
%T 131071,262144,524289,1048576,2097151,4194304,8388609,16777216,
%U 33554431,67108864,134217729,268435456,536870911
%N If n mod 4 = 0 then 2^(n-1)+1 elif n mod 4 = 2 then 2^(n-1)-1 else 2^(n-1).
%D M. E. Larsen, Summa Summarum, A. K. Peters, Wellesley, MA, 2007; see p. 37. [From _N. J. A. Sloane_, Jan 29 2009]
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A007679/b007679.txt">Table of n, a(n) for n = 1..1000</a>
%H I. Nemes et al., <a href="https://www.jstor.org/stable/2975078">How to do Monthly problems with your computer</a>, Amer. Math. Monthly, 104 (1997), 505-519.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,2).
%F a(n) = 2^(n-1) + cos(n*Pi/2).
%F a(n) = sum(2^k*C(n-k, 2k)*n/(n-k), k=0..floor(n/3)).
%F a(n) = A007909(n) + A007910(n).
%F a(n) = ((-i)^n+i^n+2^n)/2, where i=sqrt(-1). a(n) = 2*a(n-1)-a(n-2)+2*a(n-3). G.f.: x*(1-x+3*x^2)/((1-2*x)*(1+x^2)). [_Colin Barker_, May 08 2012]
%p f:=n->2^(n-1)+cos(Pi*n/2);
%t CoefficientList[Series[(1-x+3*x^2)/((1-2*x)*(1+x^2)),{x,0,30}],x] (* _Vincenzo Librandi_, May 09 2012 *)
%t Table[Which[Mod[n,4]==0,2^(n-1)+1,Mod[n,4]==2,2^(n-1)-1,True,2^(n-1)], {n,30}] (* or *) LinearRecurrence[{2,-1,2},{1,1,4},30] (* _Harvey P. Dale_, May 01 2018 *)
%o (Magma) I:=[1, 1, 4]; [n le 3 select I[n] else 2*Self(n-1)-Self(n-2)+2*Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, May 09 2012
%K nonn,easy
%O 1,3
%A _N. J. A. Sloane_, _R. K. Guy_, Simon Plouffe.