A026597 Expansion of (1+x)/(1-x-4*x^2).

1, 2, 6, 14, 38, 94, 246, 622, 1606, 4094, 10518, 26894, 68966, 176542, 452406, 1158574, 2968198, 7602494, 19475286, 49885262, 127786406, 327327454, 838473078, 2147782894, 5501675206, 14092806782, 36099507606, 92470734734

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

This sequence can generated by the following formula: a(n) = a(n-1) + 4*a(n-2) when n > 2; a[1] = 1, a[2] = 2. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 21 2004

An elephant sequence, see A175654 and A175655. For the corner squares just one A[5] vector, with decimal value 325, leads to the sequence given above. For the central square this vector leads to a companion sequence that is 4 times this very same sequence with n >= -1. - Johannes W. Meijer, Aug 15 2010

Equals INVERTi transform of A180168. - Gary W. Adamson, Aug 14 2010

Start with a single cell at coordinates (0, 0), then iteratively subdivide the grid into 2 X 2 cells and remove the cells that have one '1' in their modulo 3 coordinates. a(n) is the number of cells after n iterations. Cell configuration converges to a fractal with approximate dimension 1.357. - Peter Karpov, Apr 20 2017

Also, the number of walks of length n starting at vertex 1 in the graph with 4 vertices and edges {{0,1}, {0,2}, {0,3}, {1,2}, {2,3}}. - Sean A. Irvine, Jun 02 2025

Links

• Nathaniel Johnston, Table of n, a(n) for n = 0..500
• Sean A. Irvine, Walks on Graphs.
• Peter Karpov, InvMem, Item 26
• Peter Karpov, Illustration of initial terms (n = 1..8)
• Index entries for linear recurrences with constant coefficients, signature (1,4).

Crossrefs

Cf. A006131, A006138, A007482, A026581, A026584, A122950, A175654, A175655, A180168.

Programs

Magma

[n le 2 select n else Self(n-1) + 4*Self(n-2): n in [1..41]]; // G. C. Greubel, Dec 08 2021

Mathematica

LinearRecurrence[{1,4},{1,2},40] (* Harvey P. Dale, Nov 28 2011 *)

Sage

[(2*i)^n*( chebyshev_U(n, -i/4) - (i/2)*chebyshev_U(n-1, -i/4) ) for n in (0..40)] # G. C. Greubel, Dec 08 2021

Formula

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

a(n) = T(n,0) + T(n,1) + ... + T(n,2*n), T given by A026584.

a(n) = Sum_{k=0..n} binomial(floor((2*n-k-1)/2), n-k)*2^k. - Paul Barry, Feb 11 2005

a(n) = A006131(n) + A006131(n-1), n >= 1. - R. J. Mathar, Oct 20 2006

a(n) = Sum_{k=0..n} binomial(floor((2*n-k)/2),n-k)*4^floor(k/2). - Paul Barry, Feb 02 2007

Inverse binomial transform of A007482: (1, 3, 11, 39, 139, 495, ...). - Gary W. Adamson, Dec 04 2007

a(n) = Sum_{k=0..n+1} A122950(n+1,k)*3^(n+1-k). - Philippe Deléham, Jan 04 2008

a(n) = (1/2 + 3*sqrt(17)/34)*(1/2 + sqrt(17)/2)^n + (1/2 - 3*sqrt(17)/34)*(1/2 - sqrt(17)/2)^n. - Antonio Alberto Olivares, Jun 07 2011

a(n) = (2*i)^n*( chebyshevU(n, -i/4) - (i/2)*chebyshevU(n-1, -i/4) ). - G. C. Greubel, Dec 08 2021

E.g.f.: exp(x/2)*(17*cosh(sqrt(17)*x/2) + 3*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, Jan 31 2023

Extensions

Better name from Ralf Stephan, Jul 14 2013