login
a(n) = 7*a(n-1) - 5*a(n-2) + a(n-3), with initial values a(0) = a(1) = 1, a(2)=4.
2

%I #38 Sep 08 2022 08:45:58

%S 1,1,4,24,149,927,5768,35890,223317,1389537,8646064,53798080,

%T 334745777,2082876103,12960201916,80641778674,501774317241,

%U 3122171529233,19426970897100,120879712950776,752145307699165,4680045560037375,29120472094716576

%N a(n) = 7*a(n-1) - 5*a(n-2) + a(n-3), with initial values a(0) = a(1) = 1, a(2)=4.

%C Old definition was "Constant term in the reduction of (x^2+x+1)^n by x^3 -> x^2+x+1." For discussions of polynomial reduction, see A192232 and A192744.

%C From _Bob Selcoe_, Jun 10 2014: (Start)

%C a(n) is the trinomial transform of tribonacci numbers. (i.e., A027907(n) transform of A000073(n+2)).

%C Let the m-nacci numbers be denoted by M"(n). Examples: Fibonacci numbers are 2"(n); tribonacci numbers are 3"(n); 137-nacci numbers are 137"(n). Then the m-nomial transform of M" is M"(m*n), where M"(0)=1 and M"(n)=0 when n<0. Therefore a(n) = 3"(3n). (End)

%H G. C. Greubel, <a href="/A192806/b192806.txt">Table of n, a(n) for n = 0..1000</a>

%H László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Nemeth/nemeth6.html">The trinomial transform triangle</a>, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also <a href="https://arxiv.org/abs/1807.07109">arXiv:1807.07109</a> [math.NT], 2018.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-5,1).

%F G.f.: (1 - 6*x + 2*x^2)/(1 - 7*x + 5*x^2 - x^3). - _R. J. Mathar_, May 06 2014

%F a(n) = A000073(3n+2), n>0. - _Bob Selcoe_, Jun 10 2014

%e G.f. = 1 + x + 4*x^2 + 24*x^3 + 149*x^4 + 927*x^5 + 5768*x^6 + ...

%t q = x^3; s = x^2 + x + 1; z = 40;

%t p[n_, x_] := (x^2 + x + 1)^n;

%t Table[Expand[p[n, x]], {n, 0, 7}]

%t reduce[{p1_, q_, s_, x_}] :=

%t FixedPoint[(s PolynomialQuotient @@ #1 +

%t PolynomialRemainder @@ #1 &)[{#1, q, x}] &, p1]

%t t = Table[reduce[{p[n, x], q, s, x}], {n, 0, z}];

%t u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}] (* A192806 *)

%t u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}] (* A192807 *)

%t u3 = Table[Coefficient[Part[t, n], x, 2], {n, 1, z}] (* A099464 *)

%t LinearRecurrence[{7,-5,1}, {1,1,4}, 50] (* _G. C. Greubel_, Jan 02 2019 *)

%o (PARI) {a(n) = polcoeff( lift( (1 + x + x^2)^n * Mod(1, x^3 - x^2 - x - 1)), 0)}; /* _Michael Somos_, Jun 17 2014 */

%o (PARI) my(x='x+O('x^30)); Vec((1-6*x+2*x^2)/(1-7*x+5*x^2-x^3)) \\ _G. C. Greubel_, Jan 02 2019

%o (Magma) m:=30; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!( (1-6*x+2*x^2)/(1-7*x+5*x^2-x^3) )); // _G. C. Greubel_, Jan 02 2019

%o (Sage) ((1-6*x+2*x^2)/(1-7*x+5*x^2-x^3)).series(x,20).coefficients(x, sparse=False) # _G. C. Greubel_, Jan 02 2019

%o (GAP) a:=[1,1,4];; for n in [4..25] do a[n]:=7*a[n-1]-5*a[n-2]+a[n-3]; od; Print(a); # _Muniru A Asiru_, Jan 02 2019

%Y Cf. A192744, A192232, A192807, A000073, A027907.

%K nonn,easy

%O 0,3

%A _Clark Kimberling_, Jul 10 2011

%E Edited by _N. J. A. Sloane_, Jun 03 2018