A152011 a(0) = 1 and a(n) = (3^n - (-1)^n)/2 for n >= 1.

1, 2, 4, 14, 40, 122, 364, 1094, 3280, 9842, 29524, 88574, 265720, 797162, 2391484, 7174454, 21523360, 64570082, 193710244, 581130734, 1743392200, 5230176602, 15690529804, 47071589414, 141214768240, 423644304722

Offset: 0

Author

Roger L. Bagula and Gary W. Adamson, Nov 19 2008

Keywords

• nonn
• walk
• easy

Comments

Previous name was: A product form based on the Fibonacci product form: f(n) = 2^n*Product_{k=1..floor((n-1)/2)} (1 + 3*cos(k*Pi/n)^2).

Gary W. Adamson found this article, I experimented. Based on the paper Fibonacci identity of: f(n) = Product_{k=1..floor((n-1)/2)} (1 + 4*cos(k*Pi/n)^2). I changed the 4 to a 3 and used 2^n to get rid of the rational terms. The product comes down slow in Mathematica: I tried 30 but no luck.

For n > 0, Select an odd size subset S of {1, 2, ..., n}, then select a subset of S. - Geoffrey Critzer, Mar 03 2010

It appears that if s(n) is a first order rational sequence of the form s(1) = 2, s(n) = (s(n-1) + 2)/(2*s(n-1) + 1), n > 1 then s(n) = a(n)/(a(n) + (-1)^n). - Gary Detlefs, Nov 16 2010

For n >= 1, a(n) counts closed walks of length n + 1 on the vertex of a triangle to which two loops have been added to one of remaining vertices. - David Neil McGrath, Sep 04 2014

Examples

			G.f. = 1 + 2*x + 4*x^2 + 14*x^3 + 40*x^4 + 122*x^5 + 364*x^6 + 1094*x^7 + ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Dhroova Aiylam and Tanya Khovanova, Weighted Mediants and Fractals, arXiv:1711.01475 [math.NT], 2017. See p. 18.
• M. H. Albert and R. Brignall, Enumerating indices of Schubert varieties defined by inclusions, arXiv:1301.3188 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 11 2013
• N. Garnier and O. Ramaré, Fibonacci numbers and trigonometric identities
• N. Garnier and O. Ramaré, Fibonacci numbers and trigonometric identities, Fibonacci Quart. 46/47 (2008/2009), no. 1, 56-61.
• Index entries for linear recurrences with constant coefficients, signature (2,3).

Crossrefs

Cf. A000045.

A152011 = 2*A015518, except for the first term. [From Geoffrey Critzer, Mar 03 2010; corrected by M. F. Hasler, Nov 16 2010]

Programs

Magma

[1] cat [(3^n-(-1)^n)/2: n in [1..30]]; // Vincenzo Librandi, Sep 15 2014

Mathematica

f[n_] = 2^n Product[(1 + 3 Cos[k Pi/n]^2), {k, Floor[(n - 1)/2]}]; Table[FullSimplify[ExpandAll[f[n]]], {n, 0, 15}]
(* Second program: *)
CoefficientList[Series[(1-3x^2)/((1+x)(1-3x)), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 15 2014 *)
Join[{1}, LinearRecurrence[{2, 3}, {2, 4}, 30]] (* Jean-François Alcover, Jan 07 2019 *)

PARI

a(n)=floor(2^n*prod(k=1,floor((n-1)/2),1+3*cos(k*Pi/n)^2)+1/2) \\ Edward Jiang, Sep 08 2014

PARI

a(n)=if(n,(3^n-(-1)^n)/2,1) \\ Charles R Greathouse IV, Sep 15 2014

Sage

def A152011(n) :
    if n == 0 : return 1
    return add(2^(n-k)*binomial(n,k) for k in range(n)[::2])  # Peter Luschny, Jul 30 2012

Formula

a(n) = 2^n * Product_{k = 1..floor((n-1)/2)} (1 + 3 * cos(k * Pi/n)^2).

From Geoffrey Critzer, Mar 03 2010: (Start)

For n > 0, a(n) = Sum_{k = 1, 3, 5, ...} C(n, k)* 2^k.

E.g.f.: 1 + sinh(2*x)*exp(x). (End)

From R. J. Mathar, Mar 11 2010: (Start)

a(n) = (3^n - (-1)^n)/2, n > 0.

G.f.: (1 - 3*x^2)/((1 + x)*(1 - 3*x)). (End)

a(n) = 2*a(n-1) + 3*a(n-2) for n >= 2, a(1) = 2, and a(2) = 4. - David Neil McGrath, Sep 04 2014

a(n) = M^n[1,2] = M^n[2,1] for n>0, where M = [1,2;2,1]. - Rigoberto Florez, May 05 2020

Extensions

Terms a(16)-a(25) from Peter Luschny, Jul 30 2012

New name (using R. J. Mathar's formula) by Joerg Arndt, Sep 09 2014