login
Expansion of 2*x*(6 + 30*x - 13*x^2 - 70*x^3)/((1-x)*(1+2*x)*(1 - 4*x - 3*x^2 + 10*x^3)).
3

%I #53 Sep 08 2022 08:45:26

%S 0,12,96,370,1654,6660,28020,115190,478786,1979288,8203968,33961066,

%T 140672814,582515628,2412508492,9990776222,41375626970,171349445760,

%U 709617513368,2938760897682,12170404119878,50401719145492

%N Expansion of 2*x*(6 + 30*x - 13*x^2 - 70*x^3)/((1-x)*(1+2*x)*(1 - 4*x - 3*x^2 + 10*x^3)).

%C From _Petros Hadjicostas_, Nov 21 2019: (Start)

%C We may factor the characteristic polynomial of the 9 X 9 matrix M shown below as follows: 80 - 144*x - 56*x^2 + 184*x^3 + 9*x^4 - 89*x^5 - 2*x^6 + 18*x^7 + x^8 - x^9 = (x^3 - 4*x^2 - 3*x + 10)*(x+2)^3*(1-x)^3. The minimal polynomial of matrix M, however, is (up to a sign) equal to f(x) = x^5 - 3*x^4 - 9*x^3 + 15*x^2 + 16*x - 20 = (x-1)*(x+2)*(x^3 - 4*x^2 - 3*x + 10). This means M^5 - 3*M^4 - 9*M^3 + 15*M^2 + 16*M - 20*I_9 = 0 (where I_9 is the 9 X 9 identity matrix).

%C Post-multiplying the last equation by the 9 X 1 matrix v(n-5) (see below) and using the fact that M^k * v(n-k) = v(n) for k >= 0, we get v(n) - 3*v(n-1) - 9*v(n-2) + 15*v(n-3) + 16*v(n-4) - 20*v(n-5) = 0. Since a(n) is the (1,1)th element of v(n), we immediately get the recurrence in the formula section.

%C The generating function of the sequence (a(n): n >= 0) is a rational function with denominator x^5 * f(1/x) = x^5 * (1/x - 1) * (1/x + 2) * (1/x^3 - 4/x^2 - 3/x + 10) = (1-x)*(1+2*x) * (1 - 4*x - 3*x^2 + 10*x^3), which is the one reported by Maksym Voznyy below. The numerator of the g.f. can be determined using the initial conditions from a(0) to a(5). (End)

%D F. R. K. Chung and R. L. Graham, Erdos on Graphs, AK Peters Ltd., MA, 1998.

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

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,9,-15,-16,20).

%F Define the 9 X 9 matrix M = {[0,1,1,1,0,0,1,0,0], [1,0,1,0,1,0,0,1,0], [1,1,0, 0,0,1,0,0,1], [1,0,0,0,1,1,1,0,0], [0,1,0,1,0,1,0,1,0], [0,0,1,1,1,1,0,0,1], [1,0,0,1,0,0,0,1,1], [0,1,0,0,1,0,1,0,1], [0,0,1,0,0,1,1,1,0]}, and the sequence (v(n): n >= 1) of 9 X 1 matrices (column vectors) by v(1) = (Fibonacci(n), n = 0..8) and v(n) = M*v(n-1). Then a(n) is the (1,1)th element of the column vector v(n).

%F G.f.: 2*x*(6 + 30*x - 13*x^2 - 70*x^3)/((1-x)*(1+2*x)*(1 - 4*x - 3*x^2 + 10*x^3)). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 28 2009

%F From _Petros Hadjicostas_, Nov 21 2019: (Start)

%F a(n) = 3*a(n-1) + 9*a(n-2) - 15*a(n-3) - 16*a(n-4) + 20*a(n-5) for n >= 5.

%F a(n) = 2*a(n-1) + 11*a(n-2) - 4*a(n-3) - 20*a(n-4) - 94 for n >= 4.

%F a(n) = 4*a(n-1) + 3*a(n-2) - 10*a(n-3) - (2/3)*(47 + 28*(-2)^(n-3)) for n >= 3. (End)

%p with(LinearAlgebra); with(combinat);

%p M:= Matrix([[0,1,1,1,0,0,1,0,0], [1,0,1,0,1,0,0,1,0], [1,1,0,0,0,1,0,0,1], [1, 0,0,0,1,1,1,0,0], [0,1,0,1,0,1,0,1,0], [0,0,1,1,1,1,0,0,1], [1,0,0,1,0,0,0,1, 1], [0,1,0,0,1,0,1,0,1], [0,0,1,0,0,1,1,1,0]]);

%p f:=fibonacci;

%p v:= proc(n) option remember;

%p if n = 0 then Matrix([[f(0)],[f(1)],[f(2)],[f(3)],[f(4)],[f(5)],[f(6)],[f(7)],[f(8)]]); elif n >= 1 then

%p MatrixMatrixMultiply(M, v(n-1)); end if;

%p end proc;

%p seq(v(n)[1, 1], n = 0..40); # _Petros Hadjicostas_, Nov 21 2019

%t (* First program *)

%t M = {{0,1,1,1,0,0,1,0,0}, {1,0,1,0,1,0,0,1,0}, {1,1,0,0,0,1,0,0,1}, {1,0,0,0,1, 1,1,0,0}, {0,1,0,1,0,1,0,1,0}, {0,0,1,1,1,1,0,0,1}, {1,0,0,1,0,0,0,1,1}, {0,1, 0,0,1,0,1,0,1}, {0,0,1,0,0,1,1,1,0}};

%t v[1] = Table[Fibonacci[n], {n, 0, 8}];

%t v[n_]:= v[n]= M.v[n-1];

%t Table[Floor[v[n][[1]]], {n,40}]

%t (* Second program *)

%t CoefficientList[Series[2*x*(6+30*x-13*x^2-70*x^3)/((1-x)*(1+2*x)*(1-4*x-3*x^2 + 10*x^3)), {x,0,30}], x] (* _G. C. Greubel_, Dec 08 2019 *)

%t LinearRecurrence[{3,9,-15,-16,20},{0,12,96,370,1654},30] (* _Harvey P. Dale_, Jul 12 2022 *)

%o (PARI) my(x='x+O('x^30)); concat([0], Vec(2*x*(6+30*x-13*x^2-70*x^3)/((1-x)*(1+2*x)*(1-4*x-3*x^2 + 10*x^3)))) \\ _G. C. Greubel_, Dec 08 2019

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 30); [0] cat Coefficients(R!( 2*x*(6+30*x-13*x^2-70*x^3)/((1-x)*(1+2*x)*(1-4*x-3*x^2 + 10*x^3)) )); // _G. C. Greubel_, Dec 08 2019

%o (Sage)

%o def A120658_list(prec):

%o P.<x> = PowerSeriesRing(ZZ, prec)

%o return P( 2*x*(6+30*x-13*x^2-70*x^3)/((1-x)*(1+2*x)*(1-4*x-3*x^2 + 10*x^3)) ).list()

%o A120658_list(30) # _G. C. Greubel_, Dec 08 2019

%K nonn,easy,less

%O 0,2

%A _Roger L. Bagula_, Aug 10 2006

%E New name using g.f. by Maksym Voznyy, _Joerg Arndt_, Nov 22 2019