A063782 a(0) = 1, a(1) = 3; for n > 1, a(n) = 2*a(n-1) + 4*a(n-2).

1, 3, 10, 32, 104, 336, 1088, 3520, 11392, 36864, 119296, 386048, 1249280, 4042752, 13082624, 42336256, 137003008, 443351040, 1434714112, 4642832384, 15024521216, 48620371968, 157338828800, 509159145472, 1647673606144

Offset: 0

Author

Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Aug 17 2001

Keywords

• nonn
• easy

Comments

Ratio of successive terms approaches sqrt(5) + 1.

From Sean A. Irvine, Jun 06 2025: (Start)

Also, number of walks of length n starting at vertex 1 in the following graph:

1---2

|\ /|

| 0 |

|/ \|

4---3. (End)

Examples

			As the INVERT transform of A006138, (1, 2, 5, 11, 26, 59, ...); a(4) = 104 = (26, 11, 5, 2, 1) dot (1, 1, 3, 10, 32) = (26 + 11 + 15 + 20 + 32).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Harry J. Smith)
• Sean A. Irvine, Walks on Graphs.
• Index entries for linear recurrences with constant coefficients, signature (2,4).

Crossrefs

Cf. A006138. Row sums of A215244.

Cf. A000045, A049310, A087206, A319053.

Programs

Maple

a := proc(n) option remember: if n=0 then RETURN(1) fi: if n=1 then RETURN(2) fi: 2*a(n-1) + 4*a(n-2); end: for n from 1 to 50 do printf(`%d,`,a(n)+a(n-1)) od:
f:=n-> simplify(expand((1/2)*(1+sqrt(5))^n + (1/5)*(1+sqrt(5))^n*sqrt(5) - (1/5)*sqrt(5)*(1-sqrt(5))^n + (1/2)*(1 -sqrt(5))^n )); # N. J. A. Sloane, Aug 10 2012

Mathematica

a[n_]:=(MatrixPower[{{1,5},{1,1}},n].{{2},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2010 *)
LinearRecurrence[{2, 4}, {1, 3}, 100] (* G. C. Greubel, Feb 18 2017 *)

PARI

{ for (n=0, 200, if (n>1, a=2*a1 + 4*a2; a2=a1; a1=a, if (n, a=a1=2, a=a2=1)); if (n, write("b063782.txt", n, " ", a + a2)) ) } \\ Harry J. Smith, Aug 31 2009

Formula

For n >= 1, a(n) = 2^(n-1)*Fibonacci(n+3). - Vladeta Jovovic, Oct 25 2003

G.f.: (1 + x)/(1 - 2*x - 4*x^2). - R. J. Mathar, Feb 06 2010

Equals INVERT transform of A006138 and INVERTi transform of A179606. - Gary W. Adamson, Aug 14 2010

a(n) = (1/2)*(1+sqrt(5))^n + (1/5)*(1+sqrt(5))^n*sqrt(5) - (1/5)*sqrt(5)*(1-sqrt(5))^n + (1/2)*(1-sqrt(5))^n. - Alexander R. Povolotsky, Aug 15 2010

It follows that a(n) is the nearest integer to (and is increasingly close to) (1/2 + 1/sqrt(5))*(1+sqrt(5))^n. - N. J. A. Sloane, Aug 10 2012

a(n) = A063727(n) + A063727(n-1).

a(n) = M^n(1, 1), with the matrix M= [[3, 1], [1, -1]]. Proof by Cayley-Hamilton, using S(n, -I) = (-I)^n*F(n+1), and S = A049310 and F = A000045. Motivated by A319053. - Wolfdieter Lang, Oct 08 2018

Extensions

More terms from James Sellers, Sep 25 2001

Edited (new offset, new initial term, etc.) by N. J. A. Sloane, Aug 19 2010