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
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).
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
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) = 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
Comments