A239294 a(n) = (15^n - (-3)^n)/18.

0, 1, 12, 189, 2808, 42201, 632772, 9492309, 142382448, 2135743281, 32036129532, 480542002029, 7208129853288, 108121948330761, 1621829223367092, 24327438355289349, 364911575314991328, 5473673629767916641, 82105104446389609452

Offset: 0

Author

Felix P. Muga II, Mar 14 2014

Keywords

• nonn
• easy

Comments

Let k and t be positive integers and consider a(n) = k*a(n-1)+t*a(n-2) for n>=2, with a(0)=0, a(1)=1.

The roots of its characteristic equation are r1 = (k+sqrt(k^2+4t))/2 and r2=(k-sqrt(k^2+4t))/2. Hence, the solution to the recurrence relation is the sequence {a(n)} where a(n) = alpha1*r1^n + alpha2*r2^n. It can be shown that alpha1 = 1/sqrt(k^2+4t) and alpha2 = -alpha1. It can be shown also that |r2/r1|< 1. Thus, a(n+1)/a(n) converges to r1 as n approaches infinity.

Note that limit a(n+1)/a(n) = 15 with k=12 and t=45. Thus, we use this as the name of the sequence.

If n > 25, then |a(n+1)/a(n) - 15| < 10^(-16).

a(n+2) is the number of strings of length n containing the 12-ary digits 0,1,...,9,A,B or any of the 45 two-consecutive digits C0,C1,...,C9,CA,...,CZ,Ca,...,Ci where A corresponds to 10, B to 11, ..., Z to 35, a to 36, ..., i to 44.

Links

• Index entries for linear recurrences with constant coefficients, signature (12,45).

Programs

Mathematica

Table[(15^n-(-3)^n)/18,{n,0,20}] (* or *) LinearRecurrence[{12,45},{0,1},20] (* Harvey P. Dale, Apr 29 2019 *)

PARI

a(n) = (15^n - (-3)^n)/18; \\ Michel Marcus, Mar 16 2014

Formula

G.f.: x/((1-15*x)*(1+3*x)).

a(n) = 12*a(n-1)+45*a(n-2), for n>=2, a(0)=0, a(1)=1.

a(n) = (1/18)*(A001024(n) - (-1)^n * A000244(n)).

a(n) = A000244(n-1) * Sum_{k=0...n-1} (A000351(k) * A033999(n-1-k)).