A081186 4th binomial transform of (1,0,1,0,1,...), A059841.

1, 4, 17, 76, 353, 1684, 8177, 40156, 198593, 986404, 4912337, 24502636, 122336033, 611148724, 3054149297, 15265963516, 76315468673, 381534296644, 1907542343057, 9537324294796, 47685459212513, 238423809278164, 1192108586037617, 5960511549128476

Offset: 0

Author

Paul Barry, Mar 11 2003

Keywords

• nonn
• easy

Comments

Binomial transform of A007582.

a(n) is a companion to A005059(n): a(n) + A005059(n) = 5^n; e.g. a(4) = A005059(4) = 353 + 272 = 625 = 5^4. - Gary W. Adamson, Jun 30 2006

Number of words of length n from an alphabet of 5 letters in which a chosen letter appears an even number of times. - James Mahoney, Feb 03 2012 [See a comment in A007582, also for crossrefs. for the 1- to 11-letter word cases. - Wolfdieter Lang, Jul 17 2017]

The sequence of fractions x(n) = a(n+1)/a(n) satisfies a simple recurrence x(n+1) = 108 - (815 - 1500 / x(n-1)) / x(n) known as Muller's recurrence. It is used for the demonstration of an unexpected failure of floating-point computations. - Andrey Zabolotskiy, Sep 17 2019

Examples

			Say the alphabet is {a,b,c,d,e} and we want to know how many words of length one and two contain c an even number of times. a(1) = 4, which we can see by the four words {(a),(b),(d),(e)} and a(2) = 17, which we can see by the seventeen words {(a,a), (a,b), (a,d), (a,e), (b,a), (b,b), (b,d), (b,e), (c,c), (d,a), (d,b), (d,d), (d,e), (e,a), (e,b), (e,d), (e,e)}. - _James Mahoney_, Feb 03 2012
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Christian Hill, Muller's Recurrence, 2017.
• Index entries for linear recurrences with constant coefficients, signature (8,-15).

Crossrefs

Cf. A005059, A007582.

Programs

GAP

List([0..25], n-> (3^n + 5^n)/2); # G. C. Greubel, Dec 26 2019

Magma

[3^n/2+5^n/2: n in [0..25]]; // Vincenzo Librandi, Aug 07 2013

Maple

seq( (3^n + 5^n)/2, n=0..30); # G. C. Greubel, Dec 26 2019

Mathematica

CoefficientList[Series[(1-4x)/((1-3x)(1-5x)), {x,0,25}], x] (* Vincenzo Librandi, Aug 07 2013 *)
LinearRecurrence[{8,-15},{1,4},30] (* Harvey P. Dale, Apr 13 2019 *)

PARI

vector(31, n,(3^(n-1) + 5^(n-1))/2 ) \\ G. C. Greubel, Dec 26 2019

Sage

[(3^n + 5^n)/2 for n in (0..25)] # G. C. Greubel, Dec 26 2019

Formula

a(n) = 8*a(n-1) - 15*a(n-2) with n>1, a(0)=1, a(1)=4.

G.f.: (1-4*x)/((1-3*x)*(1-5*x)).

a(n) = (3^n + 5^n)/2.

a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k)*4^(n-2*k).

E.g.f.: exp(4*x) * cosh(x). - Paul Barry, Oct 06 2004