A033887 a(n) = Fibonacci(3*n + 1).

1, 3, 13, 55, 233, 987, 4181, 17711, 75025, 317811, 1346269, 5702887, 24157817, 102334155, 433494437, 1836311903, 7778742049, 32951280099, 139583862445, 591286729879, 2504730781961, 10610209857723, 44945570212853, 190392490709135, 806515533049393, 3416454622906707

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Binomial transform of A063727, and second binomial transform of (1,1,5,5,25,25,...), which is A074872 with offset 0. - Paul Barry, Jul 16 2003

Equals INVERT transform of A104934: (1, 2, 8, 28, 100, 356, ...) and INVERTi transform of A005054: (1, 4, 20, 100, 500, ...). - Gary W. Adamson, Jul 22 2010

a(n) is the number of compositions of n when there are 3 types of 1 and 4 types of other natural numbers. - Milan Janjic, Aug 13 2010

F(3*n+1) = 3^n*a(n;2/3), where a(n;d), n = 0, 1, ..., d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also the papers by Witula et al.). - Roman Witula, Jul 12 2012

We note that the remark above by Paul Barry can be easily obtained from the following scaling identity for delta-Fibonacci numbers y^n a(n;x/y) = Sum_{k=0..n} binomial(n,k) (y-1)^(n-k) a(k;x) and the fact that a(n;2)=5^floor(n/2). Indeed, for x=y=2 we get 2^n a(n;1) = Sum_{k=0..n} binomial(n,k) a(k;2) and, by A000045: Sum_{k=0..n} binomial(n,k) 2^k a(k;1) = Sum_{k=0..n} binomial(n,k) F(k+1) 2^k = 3^n a(n;2/3) = F(3n+1). - Roman Witula, Jul 12 2012

Except for the first term, this sequence can be generated by Corollary 1 (iv) of Azarian's paper in the references for this sequence. - Mohammad K. Azarian, Jul 02 2015

Number of 1’s in the substitution system {0 -> 110, 1 -> 11100} at step n from initial string "1" (1 -> 11100 -> 111001110011100110110 -> ...). - Ilya Gutkovskiy, Apr 10 2017

The o.g.f. of {F(m*n + 1)}A000045%20and%20L%20=%20A000032.%20-%20_Wolfdieter%20Lang">{n>=0}, for m = 1, 2, ..., is G(m,x) = (1 - F(m-1)*x) / (1 - L(m)*x + (-1)^m*x^2), with F = A000045 and L = A000032. - _Wolfdieter Lang, Feb 06 2023

Examples

			a(5) = Fibonacci(3*5 + 1) = Fibonacci(16) = 987. - _Indranil Ghosh_, Feb 04 2017
		

Links

• Indranil Ghosh, Table of n, a(n) for n = 0..1592
• Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, 7(38) (2012), 1871-1876.
• Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010), #10.8.2, Example 13.
• Gary Detlefs and Wolfdieter Lang, Improved Formula for the Multi-Section of the Linear Three-Term Recurrence Sequence, arXiv:2304.12937 [math.CO], 2023.
• I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013), #13.4.5.
• Edyta Hetmaniok, Bożena Piątek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Mathematics, 15(1) (2017), 477-485.
• Tanya Khovanova, Recursive Sequences.
• Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Mathematica, 46(1) (2013), 15-27.
• Roman 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. A000032, A000045, A104934, A005054, A063727 (inverse binomial transform), A082761 (binomial transform), A001076, A001077.

Cf. A016777, A049310, A049651, A074872, A122070, A167808, A185384.

Programs

Magma

[Fibonacci(3*n+1): n in [0..100]]; // Vincenzo Librandi, Apr 17 2011

Mathematica

Fibonacci[Range[1,5!,3]] (* Vladimir Joseph Stephan Orlovsky, May 18 2010 *)

PARI

a(n)=fibonacci(3*n+1) \\ Charles R Greathouse IV, Feb 03 2014

PARI

Vec((1-x)/(1-4*x-x^2) + O(x^100)) \\ Altug Alkan, Dec 10 2015

Formula

a(n) = A001076(n) + A001077(n) = A001076(n+1) - A001076(n).

a(n) = 2*A049651(n) + 1.

a(n) = 4*a(n-1) + a(n-2) for n>1, a(0)=1, a(1)=3;

G.f.: (1 - x)/(1 - 4*x - x^2).

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

a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(n,j)*C(n-j,k)*F(n-j+1). - Paul Barry, May 19 2006

First differences of A001076. - Al Hakanson (hawkuu(AT)gmail.com), May 02 2009

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

a(n) = Sum_{k=0..n} C(n,k)*F(n+k+1). - Paul Barry, Apr 19 2010

Let p[1]=3, p[i]=4, (i>1), and A be a Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1] (i <= j), A[i,j]=-1 (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n) = det A. - Milan Janjic, Apr 29 2010

a(n) = Sum_{i=0..n} C(n,n-i)*A063727(i). - Seiichi Kirikami, Mar 06 2012

a(n) = Sum_{k=0..n} A122070(n,k) = Sum_{k=0..n} A185384(n,k). - Philippe Deléham, Mar 13 2012

a(n) = A000045(A016777(n)). - Michel Marcus, Dec 10 2015

a(n) = F(2*n)*L(n+1) + F(n-1)*(-1)^n for n > 0. - J. M. Bergot, Feb 09 2016

a(n) = Sum_{k=0..n} binomial(n,k)*5^floor(k/2)*2^(n-k). - Tony Foster III, Sep 03 2017

2*a(n) = Fibonacci(3*n) + Lucas(3*n). - Bruno Berselli, Oct 13 2017

a(n)^2 is the denominator of continued fraction [4,...,4, 2, 4,...,4], which has n 4's before, and n 4's after, the middle 2. - Greg Dresden and Hexuan Wang, Aug 30 2021

a(n) = i^n*(S(n, -4*i) + i*S(n-1, -4*i)), with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. From the simplified trisection formula. See the first entry above with A001076. - Gary Detlefs and Wolfdieter Lang, Mar 06 2023

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