login
Sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 1".
23

%I #58 Apr 20 2023 02:11:07

%S 0,1,2,3,4,6,12,28,64,136,272,528,1024,2016,4032,8128,16384,32896,

%T 65792,131328,262144,523776,1047552,2096128,4194304,8390656,16781312,

%U 33558528,67108864,134209536,268419072,536854528,1073741824

%N Sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 1".

%C Number of strings over Z_2 of length n with trace 1 and subtrace 0.

%C Same as number of strings over GF(2) of length n with trace 1 and subtrace 0.

%C From _Gary W. Adamson_, Mar 13 2009: (Start)

%C M^n * [1,0,0,0] = [A038503(n), A000749(n), A038505(n), a(n)]; where

%C M = a 4x4 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 {h_1(x), h_2(x), h_3(x), h_4(x)} of order 4. For the definitions of {h_i(x)} and the difference analog {H_i (n)} see [Erdelyi] and the Shevelev link respectively. - _Vladimir Shevelev_, Jul 31 2017

%D A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Chapter XVIII.

%H Vincenzo Librandi, <a href="/A038504/b038504.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) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3), n > 3. - _Paul Curtz_, Mar 01 2008

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

%F From _Paul Barry_, Jul 25 2004: (Start)

%F Binomial transform of x/(1-x^4).

%F G.f.: x*(1-x)^2/((1-x)^4 - x^4) = x/(1-2*x) - x^3/((1-x)^4 - x^4).

%F a(n) = Sum_{k=0..floor(n/4)} binomial(n, 4*k+1).

%F a(n) = Sum_{k=0..n} binomial(n, k)*(sin(Pi*k/2)/2 + (1 - (-1)^k)/4).

%F a(n) = 2^(n-2) + 2^((n-2)/2)*sin(Pi*n/4) - 0^n/4. (End)

%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 (1, 2, 3, 4, 6, ...) is the binomial transform of (1, 1, 0, 0, 1, 1, ...). - _Gary W. Adamson_, May 15 2007

%F From _Vladimir Shevelev_, Jul 31 2017: (Start)

%F For n >= 1, {H_i(n)} are linearly dependent sequences: a(n) = H_2(n) = H_1(n) + H_3(n) - H_4(n);

%F a(n+m) = a(n)*H_1(m) + H_1(n)*a(m) + H_4(n)*H_3(m) + H_3(n)*H_4(m), where H_1 = A038503, H_3 = A038505, H_4 = A000749.

%F For proofs, see Shevelev's link, Theorems 2, 3. (End)

%F a(n) = (1/4)*(2^((n+1)/2)*ChebyshevU(n-1, 1/sqrt(2)) + 2^n - [n=0]). - _G. C. Greubel_, Apr 20 2023

%e a(2;1,0) = 3 since the two binary strings of trace 1, subtrace 0 and length 2 are { 10, 01 }.

%t CoefficientList[Series[x(1-x)^2/((1-2x)(1-2x+2x^2)),{x,0,40}],x] (* _Vincenzo Librandi_, Jun 22 2012 *)

%t LinearRecurrence[{4,-6,4},{0,1,2,3},40] (* _Harvey P. Dale_, Aug 23 2017 *)

%o (Magma) [0] cat [n le 3 select n else 4*Self(n-1) -6*Self(n-2) + 4*Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, Jun 22 2012

%o (SageMath)

%o @CachedFunction

%o def a(n): # a = A038504

%o if (n<4): return n

%o else: return 4*a(n-1) - 6*a(n-2) + 4*a(n-3)

%o [a(n) for n in range(51)] # _G. C. Greubel_, Apr 20 2023

%Y Cf. A000749, A038503, A038504, A038505, A099855.

%K easy,nonn

%O 0,3

%A _Frank Ruskey_