A083884 a(n) = (3^(2*n) + 1) / 2.

1, 5, 41, 365, 3281, 29525, 265721, 2391485, 21523361, 193710245, 1743392201, 15690529805, 141214768241, 1270932914165, 11438396227481, 102945566047325, 926510094425921, 8338590849833285, 75047317648499561, 675425858836496045, 6078832729528464401

Offset: 0

Author

Paul Barry, May 09 2003

Keywords

• easy
• nonn

Comments

Number of compositions of even natural numbers into n parts <= 8. - Adi Dani, May 28 2011

a(n) for n >= 1 gives the number of line segments in the n-th iteration of the Peano curve given by plotting (A163528, A163529) or by (Siromoney 1982) when parallel line segments that are connected end-to-end are counted as a single line segment. - Jason V. Morgan, Oct 08 2021

Examples

			From _Adi Dani_, May 28 2011: (Start)
a(2)=41: there are 41 compositions of even natural numbers into 2 parts <=8:
(0,0);
(0,2),(2,0),(1,1);
(0,4),(4,0),(1,3),(3,1),(2,2);
(0,6),(6,0),(1,5),(5,1),(2,4),(4,2),(3,3);
(0,8),(8,0),(1,7),(7,1),(2,6),(6,2),(3,5),(5,3),(4,4);
(2,8),(8,2),(3,7),(7,3),(4,6),(6,4),(5,5);
(4,8),(8,4),(5,7),(7,5),(6,6);
(6,8),(8,6),(7,7);
(8,8).  (End)
		

References

• Siromoney, R., & Subramanian, K.G. (1982). Space-filling curves and infinite graphs. Graph-Grammars and Their Application to Computer Science.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Roberto Amato, A note on Pythagorean Triples, arXiv:1912.05925 [math.HO], 2019. See Example 2.1 p. 4.
• Index entries for linear recurrences with constant coefficients, signature (10,-9).

Crossrefs

Cf. A000364, A002438, A007853, A083885, A086645.

Programs

Magma

[(3^(2*n) + 1) / 2: n in [0..20]]; // Vincenzo Librandi, Jun 16 2011

Mathematica

f[n_] := (3^(2n)+1)/2; Table[f@i, {i,0,20}] (* Michael De Vlieger, Jan 28 2015 *)

PARI

a(n)=(3^(2*n)+1)/2 \\ Charles R Greathouse IV, Sep 24 2015

Formula

a(0) = 1, a(n) = 9*a(n-1) - 4.

a(n) = Sum_{k=0..n} binomial(2*n, 2*k)*4^k.

a(n) = A002438(n) / A000364(n); A000364(n) : Euler numbers.

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

a(n) = (3^n + 1^n + (-1)^n + (-3)^n)/4.

E.g.f.: exp(3*x) + exp(x) + exp(-x) + exp(-3*x).

Each term expresses a Pythagorean relationship, along with (a(n)-1) and a power of 3, n>0, such that sqrt((a(n))^2 - (a(n)-1)^2) = 3^n. E.g., 365^2 - 364^2 - 3^3 = 27 (the Pythagorean triangle (365, 364, 27)). - Gary W. Adamson, Jun 25 2006

a(n) = 10*a(n-1) - 9*a(n-2). - Wesley Ivan Hurt, Apr 21 2021

Extensions

Additional comments from Philippe Deléham, Jul 10 2005