A024494 a(n) = C(n,1) + C(n,4) + ... + C(n, 3*floor(n/3) + 1).

1, 2, 3, 5, 10, 21, 43, 86, 171, 341, 682, 1365, 2731, 5462, 10923, 21845, 43690, 87381, 174763, 349526, 699051, 1398101, 2796202, 5592405, 11184811, 22369622, 44739243, 89478485, 178956970, 357913941, 715827883, 1431655766, 2863311531, 5726623061, 11453246122

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

M^n * [1,0,0] = [A024493(n), A024495(n), a(n)], where M is a 3 X 3 matrix [1,1,0; 0,1,1; 1,0,1]. Sum of terms = 2^n. Example: M^5 * [1,0,0] = [11, 11, 10], sum = 2^5 = 32. - Gary W. Adamson, Mar 13 2009

Let M be any endomorphism on any vector space such that M^3 = 1 (identity). Then (1+M)^n = A024493(n) + a(n)*M + A024495(n)*M^2. - Stanislav Sykora, Jun 10 2012

References

• D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, 2nd. ed., Problem 38, p. 70.

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-3,2).

Crossrefs

Cf. A010892, A024493, A024495, A057079.

See A131708 for another version.

Programs

Magma

[n le 3 select n else 3*Self(n-1) -3*Self(n-2) +2*Self(n-3): n in [1..40]]; // G. C. Greubel, Jan 23 2023

Mathematica

nn=20;a=1/(1-x);Drop[CoefficientList[Series[a x /(1-x-x^3 a^2),{x,0,nn}],x],1] (* Geoffrey Critzer, Dec 22 2013 *)
LinearRecurrence[{3,-3,2}, {1,2,3}, 40] (* G. C. Greubel, Jan 23 2023 *)

PARI

a(n) = sum(k=0,n\3,binomial(n,3*k+1)) /* Michael Somos, Feb 14 2006 */

PARI

a(n)=if(n<0, 0, ([1,0,1;1,1,0;0,1,1]^n)[2,1]) /* Michael Somos, Feb 14 2006 */

SageMath

def A024494(n): return (1/3)*(2^n -chebyshev_U(n,1/2) +2*chebyshev_U(n-1,1/2))
[A024494(n) for n in range(1,41)] # G. C. Greubel, Jan 23 2023

Formula

3*a(n) = 2^n + 2*cos( (n-2)*Pi/3 ) = 2^n - A057079(n+2).

G.f.: x*(1-x)/((1-2*x)*(1-x+x^2)). - Paul Barry, Feb 11 2004

a(n) = Sum_{k=0..n} 2^k*2*sin(-Pi*(n-k)/3 + Pi/3)/sqrt(3) (offset 0). - Paul Barry, May 18 2004

G.f.: (x*(1-x^2)*(1-x^3)/(1-x^6))/(1-2*x). - Michael Somos, Feb 14 2006

a(n+1) - 2*a(n) = A010892(n+1). - Michael Somos, Feb 14 2006

a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3). - Paul Curtz, Nov 20 2007

Equals binomial transform of (1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, ...). - Gary W. Adamson, Jul 03 2008

Start with x(0)=1, y(0)=0, z(0)=0 and set x(n+1) = x(n) + z(n), y(n+1) = y(n) + x(n), z(n+1) = z(n) + y(n). Then a(n) = y(n). - Stanislav Sykora, Jun 10 2012

E.g.f.: exp(x/2)*(exp(3*x/2) - cos(sqrt(3)*x/2) + sqrt(3)*sin(sqrt(3)*x/2))/3. - Stefano Spezia, Feb 06 2025