%I #16 Oct 17 2016 00:50:53
%S 2,4,8,16,30,58,112,216,416,802,1546,2980,5744,11072,21342,41138,
%T 79296,152848,294624,567906,1094674,2110052,4067256,7839888,15111870,
%U 29129066,56148080,108228904,208617920,402123970,775118874,1494089668,2879950432
%N Number of ways to toss a coin n times and not get a run of five.
%H G. C. Greubel, <a href="/A135492/b135492.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1).
%F a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4).
%F a(n) = 2*A000078(n+3).
%F G.f.: -2*x*(x+1)*(1+x^2)/(x^4+x^3+x^2+x-1). - _Colin Barker_, Jun 12 2012
%t a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]; a[1] = 2; a[2] = 4; a[3] = 8; a[4] = 16; Array[a, 33] (* _Robert G. Wilson v_, Feb 10 2008 *)
%t LinearRecurrence[{1, 1, 1, 1}, {2, 4, 8, 16}, 25] (* _G. C. Greubel_, Oct 15 2016 *)
%o (PARI) a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,1,1]^(n-1)*[2;4;8;16])[1,1] \\ _Charles R Greathouse IV_, Oct 17 2016
%Y Cf. A135491, A135493.
%K nonn,easy
%O 1,1
%A James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008
%E Corrected and extended by _Robert G. Wilson v_, Feb 10 2008