%I #116 Sep 08 2022 08:44:53
%S 0,0,1,3,6,10,16,28,56,120,256,528,1056,2080,4096,8128,16256,32640,
%T 65536,131328,262656,524800,1048576,2096128,4192256,8386560,16777216,
%U 33558528,67117056,134225920,268435456,536854528,1073709056
%N Sum of every 4th entry of row n in Pascal's triangle, starting at binomial(n,2).
%C Number of strings over Z_2 of length n with trace 0 and subtrace 1.
%C Same as number of strings over GF(2) of length n with trace 0 and subtrace 1.
%C Binomial transform of (0,1,1,0,0,1,1,0,...) gives a(n) for n >= 1. - _Paul Barry_, Jul 07 2003
%C From _Gary W. Adamson_, Mar 13 2009: (Start)
%C M^n * [1,0,0,0] = [A038503(n), A000749(n), a(n), A038504(n)]; where M = a 4 X 4 matrix [1,1,0,0; 0,1,1,0; 0,0,1,1; 1,0,0,1]. Sum of terms = 2^n.
%C Example: M^6 * [1,0,0,0] [16, 20, 16, 12]; sum = 2^6 = 64. (End)
%C {A038503, A038504, A038505, A000749} is the difference analog of the hyperbolic functions of order 4, {h_1(x), h_2(x), h_3(x), h_4(x)}. For a definition of {h_i(x)} and the difference analog {H_i (n)} see [Erdelyi] and the Shevelev link respectively. - _Vladimir Shevelev_, Jun 14 2017
%D A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Chapter XVIII.
%H Peter Luschny, <a href="/A038505/b038505.txt">Table of n, a(n) for n = 0..1000</a>
%H F. Ruskey, <a href="http://combos.org/TSstringZ2">Strings over Z_2 with given trace and subtrace</a>
%H F. Ruskey, <a href="http://combos.org/TSstringF2">Strings over GF(2) with given trace and subtrace</a>
%H Vladimir Shevelev, <a href="https://arxiv.org/abs/1706.01454">Combinatorial identities generated by difference analogs of hyperbolic and trigonometric functions of order n</a>, arXiv:1706.01454 [math.CO], 2017.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4).
%F a(n; t, s) = a(n-1; t, s) + a(n-1; t+1, s+t+1) where t is the trace and s is the subtrace.
%F a(n) = Sum_{k=0..n} binomial(n, 2 + 4*k), n >= 0.
%F a(n) = Sum_{k=0..n} (1/2)*C(n, k)*(-1)^C(k+3, 3) for n >= 1. - _Paul Barry_, Jul 07 2003
%F From _Paul Barry_, Nov 29 2004: (Start)
%F G.f.: x^2*(1-x)/((1-x)^4-x^4) = x^2*(1-x)/((1-2*x)*(1-2*x+2*x^2));
%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*(1-(-1)^k)/2. (End)
%F Conjecture: 2*a(n+2) = A038504(n+2) + A000749(n+2) + 2*A009545(n). - _Creighton Dement_, May 22 2005
%F a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3), n > 3; sequence is identical to its fourth differences. - _Paul Curtz_, Dec 21 2007
%F a(n) = A000749(n+1) - A000749(n). - _Reinhard Zumkeller_, Jul 15 2013
%F a(n+m) = a(n)*H_1(m) + H_2(n)*H_2(m) + H_1(n)*a(m) + H_4(n)*H_4(m),
%F where H_1=A038503, H_2=A038504, H_4=A000749. - _Vladimir Shevelev_, Jun 14 2017
%F From _Peter Luschny_, Jun 15 2017: (Start)
%F a(n) = n! [x^n] (1 + exp(2*x) - 2*exp(x)*cos(x))/4.
%F a(n) = A038503(n+2) - 2*A038503(n+1) + A038503(n).
%F a(n) = 2^(n-2) - A046980(n)*2^(A004525(n-3)) for n >= 1.
%F a(n) = (2^n - (1-i)^n - (1+i)^n) / 4 for n >= 1. Compare V. Shevelevs' formula (1) in A000749. (End)
%F From _Vladimir Shevelev_, Jun 16 2017: (Start)
%F Proof of the conjecture by _Creighton Dement_ (May 22 2005): using the first formula of Theorem 1 in [Shevelev link] for n=4, omega=i=sqrt(-1), i:=1,2,3,4, m:=n>=1, we have
%F a(n) = (1/2)*(2^(n-1)-2^(n/2)*cos(Pi*n/4)), A038504(n) = (1/2)*(2^(n-1)+2^(n/2)* sin(Pi*n/4)), A000749(n) = (1/2)*(2^(n-1)-2^(n/2)*sin(Pi*n/4)). Finally we use the formula by _Paul Barry_: A009545(n) = 2^(n/2)*sin(Pi*n/4) = 2^(n/2)*(-cos(Pi*(n+2)/4)). Now it is easy to obtain the hypothetical formula. (End)
%e a(3; 0, 1) = 3 since the three binary strings of trace 0, subtrace 1 and length 3 are { 011, 101, 110 }.
%p # From _Peter Luschny_, Jun 15 2017: (Start)
%p s := sqrt(2): h := n -> [-2, -s, 0, s, 2, s, 0, -s][1 + (n mod 8)]:
%p a := n -> `if`(n=0, 0, (2^n + 2^(n/2)*h(n))/4): seq(a(n), n=0..32);
%p # Alternatively:
%p egf := (1 + exp(2*x) - 2*exp(x)*cos(x))/4:
%p series(egf, x, 33): seq(n!*coeff(%,x,n), n=0..32); # (End)
%t LinearRecurrence[{4, -6, 4}, {0, 0, 1, 3}, 40] (* _Vincenzo Librandi_, Jun 22 2012 *)
%t Table[If[n==0, 0, 2^(n-2) - 2^(n/2-1) Cos[Pi*n/4]], {n, 0, 32}] (* _Vladimir Reshetnikov_, Sep 16 2016 *)
%o (Magma) I:=[0, 0, 1, 3]; [n le 3 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, Jun 22 2012
%o (Haskell)
%o a038505 n = a038505_list !! n
%o a038505_list = tail $ zipWith (-) (tail a000749_list) a000749_list
%o -- _Reinhard Zumkeller_, Jul 15 2013
%o (Sage)
%o A = lambda n: (2^n - (1-I)^n - (1+I)^n) / 4 if n != 0 else 0
%o print([A(n) for n in (0..32)]) # _Peter Luschny_, Jun 16 2017
%o (GAP) List([0..35],n->Sum([0..n],k->Binomial(n,2+4*k))); # _Muniru A Asiru_, Feb 21 2019
%Y Cf. A000749, A009116, A009545, A038503, A038504.
%K easy,nonn
%O 0,4
%A _Frank Ruskey_
%E Missing 0 prepended by _Vladimir Shevelev_, Jun 14 2017
%E Edited by _Peter Luschny_, Jun 16 2017