login
A103770
A weighted tribonacci sequence, (1,3,9).
2
1, 1, 4, 16, 37, 121, 376, 1072, 3289, 9889, 29404, 88672, 265885, 796537, 2392240, 7174816, 21520369, 64574977, 193709428, 581117680, 1743420757, 5230158649, 15690480040, 47071742800, 141214610761, 423644159521, 1270933677004
OFFSET
0,3
COMMENTS
The weighted tribonacci (1,r,r^2) with g.f. 1/(1 - x - r*x^2 - r^2*x^3) has general term Sum_{k=0..n} T(n-k,k)r^k.
Correspondence: a(n) = b(n+2)*3^n, where b(n) is the sequence of the arithmetic means of the previous three terms defined by b(n) = (1/3)*(b(n-1) + b(n-2) + b(n-3)) with initial values b(0)=0, b(1)=0, b(2)=1; the g.f. for b(n) is B(x) := x^2/(1-(x^1+x^2+x^3)/3), so the g.f. A(x) for a(n) satisfies A(x) = B(3*x)/(3*x)^2. Because b(n) converges to the limit lim_{x->1} (1-x)*B(x) = (1/6)*(b(0) + 2*b(1) + 3*b(2)) = 1/2, it follows that a(n)/3^n also converges to 1/2. This correspondence is valid in general (with necessary changes) for weighted sequences of order (1, p, p^2, p^3, p^4, ..., p^(p-1)) with integer p > 0. Forming such sequences c(n) := c(n-1) + p^1*c(n-2) + ... + p^(p-1)*c(n-p) the limit of c(n)/p^n is 2/(p+1) (see also A001045). - Hieronymus Fischer, Feb 04 2006
a(n)/3^n equals the probability that n will occur as a partial sum in a randomly-generated infinite sequence of 1s, 2s and 3s. The limiting ratio is 1/2. - Bob Selcoe, Jul 05 2013
Number of compositions of n into one sort of 1's, three sorts of 2's, and nine sorts of 3's. - Joerg Arndt, Jul 06 2013
Using the Markov Chain {{0, 1, 0}, {0, 0, 1}, {1/3, 1/3, 1/3}} and raising it to the n-th power can generate this sequence when looking at the element in the third row and third column and reading the numerator. - Robert P. P. McKone, May 25 2021
FORMULA
G.f.: 1/(1 - x - 3*x^2 - 9*x^3).
a(n) = Sum_{k=0..n} T(n-k, k)*3^k, T(n, k) = trinomial coefficients (A027907).
a(n) = Sum_{k=0..n} 3^(n-k) * (Sum_{i=0..floor((n-k)/2)} C(n-k-i, i)*C(k, n-k-i)). - Paul Barry, Apr 26 2005
a(n)/3^n converges to 1/2. - Hieronymus Fischer, Feb 02 2006
a(n) = a(n-1) + 3*a(n-2) + 9*a(n-3), n >= 3; a(0)=1, a(1)=1, a(2)=4. - Hieronymus Fischer, Feb 04 2006
a(n) = 3^n + b(n) + b(n-1), with b(n) = (-1)^A121262(n+1)*A088137(n+1). - Ralf Stephan, May 20 2007
MATHEMATICA
LinearRecurrence[{1, 3, 9}, {1, 1, 4}, {1, 27}] (* Robert P. P. McKone, May 25 2021 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Feb 15 2005
STATUS
approved