OFFSET
0,3
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=13 and t=30.
If n > 20, then |a(n+1)/a(n) - 15| < 10^(-16).
Let b(n) be the number of strings of length n containing the 13-ary digits: 0,...,9,A,B,C or the 30 two-consecutive digits D0,D1,...,D9,DA,...,DT where A corresponds to 10, ..., T corresponds to 29. Then b(0)=1=a(2) and b(1)=13=a(3). The strings q_1q_2...q_n of length n can be partitioned into 2 groups A and B where A contains the strings where q_1=0,1,...,9,A,B,C and B contains the strings where q_1=D. Thus, |A|=13*b(n-1) and |B|=30*b(n-2). Hence, b(n) = 13*b(n-1) + 30*b(n-2) for n>1. Since b(0)=a(2) and b(1)=a(3), we can show that b(n) = a(n+2).
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..849
Index entries for linear recurrences with constant coefficients, signature (13,30).
FORMULA
G.f.: x/(1 - 13*x - 30*x^2).
a(n) = 13*a(n-1) + 30*a(n-2) for n >= 2, a(0)=0, a(1)=1.
E.g.f.: (exp(15*x) - exp(-2*x))/17. - G. C. Greubel, May 26 2018
MATHEMATICA
CoefficientList[Series[x/(1-13*x-30*x^2), {x, 0, 50}], x] (* or *) Table[
(15^n - (-2)^n)/17, {n, 0, 30}] (* or *) LinearRecurrence[{13, 30}, {0, 1}, 30] (* G. C. Greubel, May 26 2018 *)
PROG
(PARI) a(n) = (15^n-(-2)^n)/17; \\ Michel Marcus, Mar 16 2014
(PARI) x='x+O('x^30); concat([0], Vec()) \\ G. C. Greubel, May 26 2018
(Magma) [(15^n -(-2)^n)/17: n in [0..30]]; // G. C. Greubel, May 26 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Felix P. Muga II, Mar 14 2014
STATUS
approved