%I #142 May 27 2024 12:23:22
%S 0,1,1,8,27,125,512,2197,9261,39304,166375,704969,2985984,12649337,
%T 53582633,226981000,961504803,4073003173,17253512704,73087061741,
%U 309601747125,1311494070536,5555577996431,23533806109393,99690802348032,422297015640625
%N Third power of Fibonacci numbers (A000045).
%C Divisibility sequence; that is, if n divides m, then a(n) divides a(m).
%C In general, cubing the terms of a Horadam sequence with signature (c,d) will result in a fourth-order recurrence with signature (c^3+2*c*d, c^4*d+3*(c*d)^2+2*d^3, -(c*d)^3-2*c*d^4, -d^6). - _Gary Detlefs_, Nov 12 2021
%C a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using (1/3,2/3)-fences and third-squares (1/3 X 1 pieces, always placed so that the shorter sides are horizontal). A (w,g)-fence is a tile composed of two w X 1 pieces separated by a gap of width g. a(n+1) also equals the number of tilings of an n-board using (1/6,1/3)-fences and (1/6,5/6)-fences. - _Michael A. Allen_, Jan 11 2022
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 1, p. 85, (exercise 1.2.8. Nr. 30) and p. 492 (solution).
%H Vincenzo Librandi, <a href="/A056570/b056570.txt">Table of n, a(n) for n = 0..173</a>
%H Feryal Alayont and Evan Henning, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Alayont/ala4.html">Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
%H Mohammad K. Azarian, <a href="http://www.m-hikari.com/ijcms/ijcms-2012/37-40-2012/azarianIJCMS37-40-2012.pdf">Fibonacci Identities as Binomial Sums</a>, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 1871-1876.
%H Mohammad K. Azarian, <a href="http://www.m-hikari.com/ijcms/ijcms-2012/41-44-2012/azarianIJCMS41-44-2012.pdf">Fibonacci Identities as Binomial Sums II</a>, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 42, 2012, pp. 2053-2059.
%H A. Brousseau, <a href="http://www.fq.math.ca/Scanned/6-1/brousseau3.pdf">A sequence of power formulas</a>, Fib. Quart., 6 (1968), 81-83.
%H Andrej Dujella, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00341-0">A bijective proof of Riordan's theorem on powers of Fibonacci numbers</a>, Discrete Math. 199 (1999), no. 1-3, 217--220. MR1675924 (99k:05016).
%H Kenneth Edwards and Michael A. Allen, <a href="https://www.fq.math.ca/Papers1/58-5/edwards.pdf">A new combinatorial interpretation of the Fibonacci numbers cubed</a>, Fib. Q. 58:5 (2020) 128-134.
%H D. Foata and G.-N. Han, <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub71.html">Nombres de Fibonacci et polynomes orthogonaux</a>
%H Mariana Nagy, Simon R. Cowell and Valeriu Beiu, <a href="https://arxiv.org/abs/1902.05944">Survey of Cubic Fibonacci Identities - When Cuboids Carry Weight</a>, arXiv:1902.05944 [math.HO], 2019.
%H Hilary I. Okagbue, Muminu O. Adamu, Sheila A. Bishop and Abiodun A. Opanuga, <a href="https://www.ripublication.com/ijaer16/ijaerv11n6_150.pdf">Digit and Iterative Digit Sum of Fibonacci numbers, their identities and powers</a>, International Journal of Applied Engineering Research ISSN 0973-4562 Volume 11, Number 6 (2016) pp 4623-4627.
%H J. Riordan, <a href="http://dx.doi.org/10.1215/S0012-7094-62-02902-2">Generating functions for powers of Fibonacci numbers</a>, Duke. Math. J. 29 (1962) 5-12.
%H E. L. Roettger and H. C. Williams, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Roettger/roettger12.html">Appearance of Primes in Fourth-Order Odd Divisibility Sequences</a>, J. Int. Seq., Vol. 24 (2021), Article 21.7.5.
%H H. C. Williams and R. K. Guy, <a href="http://www.emis.de/journals/INTEGERS/papers/p33/p33.Abstract.html">Odd and even linear divisibility sequences of order 4</a>, INTEGERS, 2015, #A33.
%H <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,6,-3,-1).
%F a(n) = A000045(n)^3.
%F G.f.: x*p(3, x)/q(3, x) with p(3, x) = Sum_{m=0..2} A056588(2, m)*x^m = 1 -2*x -x^2 and q(3, x) = Sum_{m=0..4} A055870(4, m)*x^m = 1 -3*x -6*x^2 +3*x^3 +x^4 = (1+x-x^2)*(1-4*x-x^2) (factorization deduced from Riordan result).
%F Recursion (cf. Knuth's exercise): 1*a(n) -3*a(n-1) -6*a(n-2) +3*a(n-3) +1*a(n-4) = 0, n >= 4, a(0)=0, a(1)=a(2)=1, a(3)=2^3. See 5th row of signed Fibonomial triangle for coefficients: A055870(4, m), m=0..4
%F a(n) = (Fibonacci(3n) - 3(-1)^n*Fibonacci(n))/5. - _Ralf Stephan_, May 14 2004
%F a(n) and a(n+1) are found as rightmost and leftmost terms (respectively) in M^n * [1 0 0 0] where M = the 4 X 4 upper triangular Pascal's triangle matrix [1 3 3 1 / 1 2 1 0 / 1 1 0 0 / 1 0 0 0]. E.g., Ma(4) = 27, a(5) = 125. M^4 * [1 0 0 0] = [125 75 45 27]; where 75 = A066259(4) and 45 = A066258(3). The characteristic polynomial of M = x^4 - 3x^3 - 6x^2 + 3x + 1. a(n)/a(n-1) of the sequence and companions tend to 2+sqrt(5) = 4.2360679..., an eigenvalue of M and a root of the polynomial. - _Gary W. Adamson_, Oct 31 2004
%F From _R. J. Mathar_, Oct 16 2006: (Start)
%F Sum_{j=0..n} binomial(n,j)*a(j) = (2^n*A001906(n) + 3*A000045(n))/5.
%F Sum_{j=0..n} (-1)^j*binomial(n,j)*a(j) = ((-2)^n*A000045(n) - 3*A001906(n))/5. (End)
%F G.f.: x*(1-2*x-x^2)/((1+x-x^2)*(1-4*x-x^2)). - _Colin Barker_, Feb 28 2012
%F a(n) = F(n-2)*F(n+1)^2 + F(n-1)*(-1)^n. - _J. M. Bergot_, Mar 17 2016
%F a(n) = ((-3*(1/2*(-1-sqrt(5)))^n-(2-sqrt(5))^n+3*(1/2*(-1+sqrt(5)))^n+(2+sqrt(5))^n)) / (5*sqrt(5)). - _Colin Barker_, Jun 04 2016
%F a(n) = F(n-1)*F(n)*F(n+1) + F(n)*(-1)^(n-1). - _Tony Foster III_, Apr 11 2018
%F 5*a(n) = L(2*n-1)*F(n+2) - L(2*n+1)*F(n-2) - 7*(-1)^n*F(n), where L(n) = A000032(n). - _Peter Bala_, Nov 12 2019
%F F(n+1)*F(n)*F(n-1) = 2*Sum_{j=1..n-1} P(j)*a(n-j) for n>0, where Pell number P(n) = A000129(n). - _Michael A. Allen_, Jan 11 2022
%e a(4) = 27 because the fourth Fibonacci number is 3 and 3^3 = 27.
%e a(5) = 125 because the fifth Fibonacci number is 5 and 5^3 = 125.
%p A056570 := proc(n) combinat[fibonacci](n)^3 ; end proc:
%p seq(A056570(n),n=0..20) ;
%t Table[Fibonacci[n]^3, {n, 0, 30}] (* _Vladimir Joseph Stephan Orlovsky_, Jul 21 2008 *)
%o (Magma) [Fibonacci(n)^3: n in [0..30]]; // _Vincenzo Librandi_, Jun 04 2011
%o (PARI) a(n)=fibonacci(n)^3 \\ _Charles R Greathouse IV_, Sep 24 2015
%o (PARI) concat(0, Vec(x*(1-2*x-x^2)/((1+x-x^2)*(1-4*x-x^2)) + O(x^30))) \\ _Colin Barker_, Jun 04 2016
%o (Sage) [fibonacci(n)^3 for n in (0..30)] # _G. C. Greubel_, Feb 20 2019
%Y Cf. A000045, A007598, A056588, A055870, A066259, A066258.
%Y Cf. A346513 (first differences), A005968 (partial sums).
%Y Third row of array A103323.
%K nonn,easy
%O 0,4
%A _Wolfdieter Lang_, Jul 10 2000