A239285 a(n) = (15^n - (-2)^n)/17.

0, 1, 13, 199, 2977, 44671, 670033, 10050559, 150758257, 2261374111, 33920611153, 508809168319, 7632137522737, 114482062845151, 1717230942669073, 25758464140052479, 386376962100754417, 5795654431511381791, 86934816472670595793, 1304022247090059199039

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

Crossrefs

Cf. A001024, A122803.

Programs

Magma

[(15^n -(-2)^n)/17: n in [0..30]]; // 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 *)

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

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.

a(n) = (1/17)*(A001024(n) - A122803(n)), n >= 0.

a(0)=0, a(n) = Sum_{k=0..n-1} A001024(k)*A122803(n-1-k) for n > 0.

E.g.f.: (exp(15*x) - exp(-2*x))/17. - G. C. Greubel, May 26 2018