A015448 a(0) = 1, a(1) = 1, and a(n) = 4*a(n-1) + a(n-2) for n >= 2.

1, 1, 5, 21, 89, 377, 1597, 6765, 28657, 121393, 514229, 2178309, 9227465, 39088169, 165580141, 701408733, 2971215073, 12586269025, 53316291173, 225851433717, 956722026041, 4052739537881, 17167680177565, 72723460248141, 308061521170129, 1304969544928657, 5527939700884757

Offset: 0

Author

Olivier Gérard

Keywords

• nonn
• easy

Comments

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

For n >= 1, row sums of triangle

m |k=0 1 2 3 4 5 6 7

====+=============================================

0 | 1

1 | 1 4

2 | 1 4 16

3 | 1 8 16 64

4 | 1 8 48 64 256

5 | 1 12 48 256 256 1024

6 | 1 12 96 256 1280 1024 4096

7 | 1 16 96 640 1280 6144 4096 16384

which is triangle for numbers 4^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012

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

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

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

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

Links

• T. D. Noe, Table of n, a(n) for n = 0..200
• Joerg Arndt, Matters Computational (The Fxtbook), pp. 313-315.
• Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 1871-1876 (see Corollary 1 (vi)).
• Gary Detlefs and Wolfdieter Lang, Improved Formula for the Multi-Section of the Linear Three-Term Recurrence Sequence, arXiv:2304.12937 [math.CO], 2023.
• Amelia Gilson, Hadley Killen, Steven J. Miller, Nadia Razek, Joshua M. Siktar, and Liza Sulkin, Zeckendorf's Theorem Using Indices in an Arithmetic Progression, arXiv:2005.10396 [math.NT], 2020.
• Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Math. 15 (2017), 477-485.
• I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
• Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Tanya Khovanova, Recursive Sequences
• Bahar Kuloğlu, Engin Özkan, and Marin Marin, Fibonacci and Lucas Polynomials in n-gon, An. Şt. Univ. Ovidius Constanţa (Romania 2023) Vol. 31, No 2, 127-140.
• Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Math. 46 (2013), 15-27.
• R. Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009) 310-329, MR2555042
• Index entries for linear recurrences with constant coefficients, signature (4,1).

Crossrefs

Cf. A001076, A147722 (INVERT transform), A109499 (INVERTi transform), A154626 (Binomial transform), A086344 (inverse binomial transform), A003946, A049310.

Cf. A000032, A000045, A014445, A014448, A033887, A046854, A055830, A055870, A084326, A167808.

Programs

Magma

[Fibonacci(3*n-1): n in [0..40]]; // Vincenzo Librandi, Jul 04 2015

Maple

with(combinat): a:=n->fibonacci(n,4)-3*fibonacci(n-1,4): seq(a(n), n=1..23); # Zerinvary Lajos, Apr 04 2008

Mathematica

Fibonacci/@(3*Range[0,30]-1) (* Vladimir Joseph Stephan Orlovsky, Mar 01 2010 *)
LinearRecurrence[{4,1},{1,1},30] (* Harvey P. Dale, May 15 2019 *)

Maxima

a[0]:1$
a[1]:1$
a[n]:=4*a[n-1]+a[n-2]$
A015448(n):=a[n]$
makelist(A015448(n),n,0,30); /* Martin Ettl, Nov 03 2012 */

PARI

a(n) = fibonacci(3*n-1); \\ Altug Alkan, Dec 10 2015

Formula

a(n) = Fibonacci(3n-1) = ( (1+sqrt(5))*(2-sqrt(5))^n - (1-sqrt(5))*(2+sqrt(5))^n )/ (2*sqrt(5)).

O.g.f.: (1-3*x)/(1-4*x-x^2). - Len Smiley, Dec 09 2001

a(n) = Sum_{k=0..n} 3^k*A055830(n,k). - Philippe Deléham, Oct 18 2006

a(n) = upper left term in the 2 X 2 matrix [1,2; 2,3]^n. - Gary W. Adamson, Mar 02 2008

[a(n), A001076(n)] = [1,4; 1,3]^n * [1,0]. - Gary W. Adamson, Mar 21 2008

a(n) = A167808(3*n-1) for n > 0. - Reinhard Zumkeller, Nov 12 2009

a(n) = Fibonacci(3n+1) mod Fibonacci(3n), n > 0.

a(n) = (A000032(3*n)-Fibonacci(3*n))/2 = (A014448(n)-A014445(n))/2.

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

a(n) = A001076(n+1) - 3*A001076(n). - R. J. Mathar, Jul 12 2012

From Gary Detlefs and Wolfdieter Lang, Aug 20 2012: (Start)

a(n) = (5*F(n)^3 + 5*F(n-1)^3 + 3*(-1)^n*F(n-2))/2,

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)

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

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

From Gary Detlefs and Wolfdieter Lang, Mar 06 2023: (Start)

a(n) = A001076(n) + A001076(n-1), with A001076(-1) = 1. See the R. J. Mathar formula above.

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)

a(n) = Sum_{k=0..n} A046854(n-1,k)*4^k. - R. J. Mathar, Feb 10 2024

E.g.f.: exp(2*x)*(5*cosh(sqrt(5)*x) - sqrt(5)*sinh(sqrt(5)*x))/5. - Stefano Spezia, Jun 03 2024