%I #187 Aug 04 2024 20:18:58
%S 1,1,5,21,89,377,1597,6765,28657,121393,514229,2178309,9227465,
%T 39088169,165580141,701408733,2971215073,12586269025,53316291173,
%U 225851433717,956722026041,4052739537881,17167680177565,72723460248141,308061521170129,1304969544928657,5527939700884757
%N a(0) = 1, a(1) = 1, and a(n) = 4*a(n-1) + a(n-2) for n >= 2.
%C If one deletes the leading 0 in A084326, takes the inverse binomial transform, and adds a(0)=1 in front, one obtains this sequence here. - Al Hakanson (hawkuu(AT)gmail.com), May 02 2009
%C For n >= 1, row sums of triangle
%C m |k=0 1 2 3 4 5 6 7
%C ====+=============================================
%C 0 | 1
%C 1 | 1 4
%C 2 | 1 4 16
%C 3 | 1 8 16 64
%C 4 | 1 8 48 64 256
%C 5 | 1 12 48 256 256 1024
%C 6 | 1 12 96 256 1280 1024 4096
%C 7 | 1 16 96 640 1280 6144 4096 16384
%C which is triangle for numbers 4^k*C(m,k) with duplicated diagonals. - _Vladimir Shevelev_, Apr 12 2012
%C a(n) = a(n;-2) = 3^n*Sum_{k=0..n} binomial(n,k)*F(k+1)*(-2/3)^k, where a(n;d), n=0,1,...,d, denotes the delta-Fibonacci numbers defined in comments to A000045 (see also the papers of Witula et al.). We note that (see A033887) F(3n+1) = 3^n*a(n,2/3) = Sum_{k=0..n} binomial(n,k)*F(k-1)*(-2/3)^k, which implies F(3n+1) + 3^(-n)*a(n) = Sum_{k=0..n} binomial(n,k)*L(k)*(-2/3)^k, where L(k) denotes the k-th Lucas number. - _Roman Witula_, Jul 12 2012
%C a(n+1) is (for n >= 0) the number of length-n strings of 5 letters {0,1,2,3,4} with no two adjacent nonzero letters identical. The general case (strings of L letters) is the sequence with g.f. (1+x)/(1-(L-1)*x-x^2). - _Joerg Arndt_, Oct 11 2012
%C Starting with offset 1 the sequence is the INVERT transform of (1, 4, 4*3, 4*3^2, 4*3^3, ...); i.e., of A003946: (1, 4, 12, 36, 108, ...). - _Gary W. Adamson_, Aug 06 2016
%C a(n+1) equals the number of quinary sequences of length n such that no two consecutive terms differ by 3. - _David Nacin_, May 31 2017
%H T. D. Noe, <a href="/A015448/b015448.txt">Table of n, a(n) for n = 0..200</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 313-315.
%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 (see Corollary 1 (vi)).
%H Gary Detlefs and Wolfdieter Lang, <a href="https://arxiv.org/abs/2304.12937">Improved Formula for the Multi-Section of the Linear Three-Term Recurrence Sequence</a>, arXiv:2304.12937 [math.CO], 2023.
%H Amelia Gilson, Hadley Killen, Steven J. Miller, Nadia Razek, Joshua M. Siktar, and Liza Sulkin, <a href="https://arxiv.org/abs/2005.10396">Zeckendorf's Theorem Using Indices in an Arithmetic Progression</a>, arXiv:2005.10396 [math.NT], 2020.
%H Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, <a href="https://doi.org/10.1515/math-2017-0047">Binomials Transformation Formulae of Scaled Fibonacci Numbers</a>, Open Math. 15 (2017), 477-485.
%H I. M. Gessel and Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5.
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H Bahar Kuloğlu, Engin Özkan, and Marin Marin, <a href="https://doi.org/10.2478/auom-2023-0023">Fibonacci and Lucas Polynomials in n-gon</a>, An. Şt. Univ. Ovidius Constanţa (Romania 2023) Vol. 31, No 2, 127-140.
%H Roman Witula, <a href="https://doi.org/10.1515/dema-2013-0436">Binomials transformation formulae of scaled Lucas numbers</a>, Demonstratio Math. 46 (2013), 15-27.
%H R. Witula and Damian Slota, <a href="http://dx.doi.org/10.2298/AADM0902310W">delta-Fibonacci numbers</a>, Appl. Anal. Discr. Math 3 (2009) 310-329, <a href="http://www.ams.org/mathscinet-getitem?mr=2555042">MR2555042</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,1).
%F a(n) = Fibonacci(3n-1) = ( (1+sqrt(5))*(2-sqrt(5))^n - (1-sqrt(5))*(2+sqrt(5))^n )/ (2*sqrt(5)).
%F O.g.f.: (1-3*x)/(1-4*x-x^2). - _Len Smiley_, Dec 09 2001
%F a(n) = Sum_{k=0..n} 3^k*A055830(n,k). - _Philippe Deléham_, Oct 18 2006
%F a(n) = upper left term in the 2 X 2 matrix [1,2; 2,3]^n. - _Gary W. Adamson_, Mar 02 2008
%F [a(n), A001076(n)] = [1,4; 1,3]^n * [1,0]. - _Gary W. Adamson_, Mar 21 2008
%F a(n) = A167808(3*n-1) for n > 0. - _Reinhard Zumkeller_, Nov 12 2009
%F a(n) = Fibonacci(3n+1) mod Fibonacci(3n), n > 0.
%F a(n) = (A000032(3*n)-Fibonacci(3*n))/2 = (A014448(n)-A014445(n)/2.
%F For n >= 2, a(n) = F_n(4) + F_(n+1)(4), where F_n(x) is a Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i)*x^(n-2*i-1). - _Vladimir Shevelev_, Apr 13 2012
%F a(n) = A001076(n+1) - 3*A001076(n). - _R. J. Mathar_, Jul 12 2012
%F From _Gary Detlefs_ and _Wolfdieter Lang_, Aug 20 2012: (Start)
%F a(n) = (5*F(n)^3 + 5*F(n-1)^3 + 3*(-1)^n*F(n-2))/2,
%F a(n) = (F(n+1)^3 + 2*F(n)^3 - F(n-2)^3)/2, n >= 0, with F(-1) = 1 and F(-2) = -1. Second line from first one with 3*(-1)^n* F(n-2) = F(n-1)^3 - 4*F(n-2)^3 - F(n-3)^3 (in Koshy's book, p. 89, 32. (with a - sign) and 33. For the Koshy reference see A000045) and the F^3 recurrence (see row n=4 of A055870, or Koshy p. 87, 1.). First line from the preceding _R. J. Mathar_ formula with F(3*n) = 5*F(n)^3 + 3*(-1)^n*F(n) (Koshy p. 89, 46.) and the above mentioned formula, Koshy's 32. and 33., with n -> n+2 in order to eliminate F(n+1)^3. (End)
%F For n > 0, a(n) = L(n-1)*L(n)*F(n) + F(n+1)*(-1)^n with L(n)=A000032(n). - _J. M. Bergot_, Dec 10 2015
%F For n > 1, a(n)^2 is the denominator of continued fraction [4,4,...,4, 6, 4,4,...4], which has n-1 4's before, and n-1 4's after, the middle 6. - _Greg Dresden_, Sep 18 2019
%F From _Gary Detlefs_ and _Wolfdieter Lang_, Mar 06 2023: (Start)
%F a(n) = A001076(n) + A001076(n-1), with A001076(-1) = 1. See the _R. J. Mathar_ formula above.
%F a(n+1) = i^n*(S(n-1,-4*i) - i*S(n-2,-4*i)), for n >= 0, with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. From the simplified Fibonacci trisection formula for {F(3*n+2)}_{n>=0}. (End)
%F a(n) = Sum_{k=0..n} A046854(n-1,k)*4^k. - _R. J. Mathar_, Feb 10 2024
%F E.g.f.: exp(2*x)*(5*cosh(sqrt(5)*x) - sqrt(5)*sinh(sqrt(5)*x))/5. - _Stefano Spezia_, Jun 03 2024
%p with(combinat): a:=n->fibonacci(n,4)-3*fibonacci(n-1,4): seq(a(n), n=1..23); # _Zerinvary Lajos_, Apr 04 2008
%t Fibonacci/@(3*Range[0,30]-1) (* _Vladimir Joseph Stephan Orlovsky_, Mar 01 2010 *)
%t LinearRecurrence[{4,1},{1,1},30] (* _Harvey P. Dale_, May 15 2019 *)
%o (Maxima)
%o a[0]:1$
%o a[1]:1$
%o a[n]:=4*a[n-1]+a[n-2]$
%o A015448(n):=a[n]$
%o makelist(A015448(n),n,0,30); /* _Martin Ettl_, Nov 03 2012 */
%o (Magma) [Fibonacci(3*n-1): n in [0..40]]; // _Vincenzo Librandi_, Jul 04 2015
%o (PARI) a(n) = fibonacci(3*n-1); \\ _Altug Alkan_, Dec 10 2015
%Y Cf. A001076, A147722 (INVERT transform), A109499 (INVERTi transform), A154626 (Binomial transform), A086344 (inverse binomial transform), A003946, A049310.
%Y Cf. A000032, A000045, A014445, A014448, A033887, A046854, A055830, A055870, A084326, A167808.
%K nonn,easy
%O 0,3
%A _Olivier Gérard_