A103770 A weighted tribonacci sequence, (1,3,9).

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

Author

Paul Barry, Feb 15 2005

Keywords

• easy
• nonn

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

Links

• Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 19.
• Index entries for linear recurrences with constant coefficients, signature (1,3,9).

Crossrefs

Cf. A000073, A102001.

Cf. A071675, A027907.

Cf. A121262, A088137.

Programs

Mathematica

LinearRecurrence[{1, 3, 9}, {1, 1, 4}, {1, 27}] (* 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