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

0, 2, 12, 50, 204, 818, 3276, 13106, 52428, 209714, 838860, 3355442, 13421772, 53687090, 214748364, 858993458, 3435973836, 13743895346, 54975581388, 219902325554, 879609302220, 3518437208882, 14073748835532, 56294995342130, 225179981368524, 900719925474098

Offset: 0

Author

Roger L. Bagula, Mar 04 2006

Keywords

• nonn
• easy

Comments

Inverse Z-transform of polynomial in A112627.

a(n) is also the number of corners in the n-th approximation of the Hilbert Curve. The 1st Hilbert Curve approximation has 2 corners. To find a(n) given a(n - 1), look at how the n-th Hilbert Curve approximation is constructed: duplicate the (n-1)-th approximation 4 times and connect the duplicates with 3 line segments. a(n) will always be 4 * a(n - 1) corners from the 4 duplicates plus 4 new corners if n is even or 2 new corners if n is odd. - Mikel Mcdaniel, Jan 10 2019

Links

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

Crossrefs

Cf. A112627.

Programs

Magma

[(4^(n+1)+(-1)^n)/5 - 1: n in [0..25]]; // Vincenzo Librandi, Jan 10 2019

Maple

seq((4^(n+1)+(-1)^n)/5 - 1, n=0..100); # Robert Israel, Mar 09 2016

Mathematica

Table[InverseZTransform[(1 + 2*x)/(1 - x - 16*x^2 + 16*x^3), x, n]*2^( 2*n), {n, 1, 25}]
LinearRecurrence[{4, 1, -4}, {0, 2, 12}, 50] (* G. C. Greubel, Feb 07 2016 *)

PARI

a(n) = (bitneg(0,2*n+2)-1)\5; \\ Kevin Ryde, May 05 2023

Formula

a(n) = InverseZTransform[(1 + 2*x)/(1 - x - 16*x^2 + 16*x^3), x, n] * 2^(2*n).

a(n) = 5*a(n-1)-4*a(n-2) +2*(-1)^n.

a(n) = 4*a(n-1)+a(n-2)-4*a(n-3). - Gary Detlefs Dec 17 2010

a(n) = (4^(n+1)+(-1)^n)/5 - 1. - Robert Israel, Mar 09 2016

a(n) = 4*a(n-1)+3+(-1)^n. - Mikel Mcdaniel, Jan 10 2019

Extensions

Entry revised by N. J. A. Sloane, Dec 18 2010