A120612 For n>1, a(n) = 2*a(n-1) + 15*a(n-2); a(0)=1, a(1)=1.

1, 1, 17, 49, 353, 1441, 8177, 37969, 198593, 966721, 4912337, 24325489, 122336033, 609554401, 3054149297, 15251614609, 76315468673, 381405156481, 1907542343057, 9536162033329, 47685459212513, 238413348924961, 1192108586037617, 5960417405949649

Offset: 0

Author

Gary W. Adamson, Jun 17 2006

Keywords

• nonn
• easy

Comments

Characteristic polynomial of matrix M = x^2 - 2x - 15. a(n)/a(n-1) tends to 5, largest eigenvalue of M and a root of the characteristic polynomial.

Binomial transform of [1, 0, 16, 0, 256, 0, 4096, 0, 65536, 0, ...]=: powers of 16 (A001025) with interpolated zeros. - Philippe Deléham, Dec 02 2008

a(n) is the number of compositions of n when there are 1 type of 1 and 16 types of other natural numbers. - Milan Janjic, Aug 13 2010

Examples

			a(4) = 353 = 2*49 + 15*17 = 2*a(3) + 15*a(2).
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Index entries for linear recurrences with constant coefficients, signature (2,15).

Crossrefs

Cf. A005059, A081186, A059841.

Programs

Mathematica

Table[(5^n+(-1)^n*3^n)/2,{n,1,30}] (* Alexander Adamchuk, Aug 31 2006 *)
a[n_] := (5^n + (-3)^n)/2; Array[a, 24, 0] (* Or *)
CoefficientList[Series[(1 + 15 x)/(1 - 2 x - 15 x^2), {x, 0, 23}], x] (* Or *)
LinearRecurrence[{2, 15}, {1, 1}, 25] (* Or *)
Table[ MatrixPower[{{1, 2}, {8, 1}}, n][[1, 1]], {n, 0, 30}]  (* Robert G. Wilson v, Sep 18 2013 *)

PARI

a(n)=([1,4; 4,1]^n)[1,1] \\ Charles R Greathouse IV, Oct 16 2013

PARI

concat(1, Vec((15*x+1)/(-15*x^2-2*x+1) + O(x^100))) \\ Colin Barker, Mar 12 2014

PARI

a(n) = ( 5^n + (-1)^n * 3^n ) / 2 \\ Charles R Greathouse IV, May 18 2015

Formula

Let M = the 2 X 2 matrix [1,4; 4,1], then a(n) = M^n * [1,0], left term.

From Alexander Adamchuk, Aug 31 2006: (Start)

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

a(2n+1) = A005059(2n+1).

a(2n) = A081186(2n). (End)

a(n) = Sum_{k=0..n} A098158(n,k)*16^(n-k). - Philippe Deléham, Dec 26 2007

If p(1)=1, and p(i)=16, (i > 1), and if A is Hessenberg matrix of order n defined by: A(i,j) = p(j-i+1), (i <= j), A(i,j)=-1, (i = j+1), and A(i,j)=0 otherwise. Then, for n >= 1, a(n)=det A. - Milan Janjic, Apr 29 2010

Extensions

More terms from Alexander Adamchuk, Aug 31 2006

Entry revised by Philippe Deléham, Dec 02 2008

More terms from Colin Barker, Mar 12 2014