login
a(n) = Fibonacci(3*n + 1).
41

%I #172 May 24 2024 16:27:09

%S 1,3,13,55,233,987,4181,17711,75025,317811,1346269,5702887,24157817,

%T 102334155,433494437,1836311903,7778742049,32951280099,139583862445,

%U 591286729879,2504730781961,10610209857723,44945570212853,190392490709135,806515533049393,3416454622906707

%N a(n) = Fibonacci(3*n + 1).

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C The o.g.f. of {F(m*n + 1)}_{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

%H Indranil Ghosh, <a href="/A033887/b033887.txt">Table of n, a(n) for n = 0..1592</a>

%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, 7(38) (2012), 1871-1876.

%H Paul Barry and A. Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry2/barry94r.html">The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences</a>, J. Int. Seq. 13 (2010), #10.8.2, Example 13.

%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 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 Edyta Hetmaniok, Bożena Piątek, and Roman Wituła, <a href="https://doi.org/10.1515/math-2017-0047">Binomials Transformation Formulae of Scaled Fibonacci Numbers</a>, Open Mathematics, 15(1) (2017), 477-485.

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>.

%H Roman Witula, <a href="https://doi.org/10.1515/dema-2013-0436">Binomials transformation formulae of scaled Lucas numbers</a>, Demonstratio Mathematica, 46(1) (2013), 15-27.

%H Roman 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) = A001076(n) + A001077(n) = A001076(n+1) - A001076(n).

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

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

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

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

%F 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

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

%F a(n) = A167808(3*n+1). - _Reinhard Zumkeller_, Nov 12 2009

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

%F 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

%F a(n) = Sum_{i=0..n} C(n,n-i)*A063727(i). - _Seiichi Kirikami_, Mar 06 2012

%F a(n) = Sum_{k=0..n} A122070(n,k) = Sum_{k=0..n} A185384(n,k). - _Philippe Deléham_, Mar 13 2012

%F a(n) = A000045(A016777(n)). - _Michel Marcus_, Dec 10 2015

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

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

%F 2*a(n) = Fibonacci(3*n) + Lucas(3*n). - _Bruno Berselli_, Oct 13 2017

%F 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

%F 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

%F E.g.f.: exp(2*x)*(5*cosh(sqrt(5)*x) + sqrt(5)*sinh(sqrt(5)*x))/5. - _Stefano Spezia_, May 24 2024

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

%t Fibonacci[Range[1,5!,3]] (* _Vladimir Joseph Stephan Orlovsky_, May 18 2010 *)

%o (Magma) [Fibonacci(3*n+1): n in [0..100]]; // _Vincenzo Librandi_, Apr 17 2011

%o (PARI) a(n)=fibonacci(3*n+1) \\ _Charles R Greathouse IV_, Feb 03 2014

%o (PARI) Vec((1-x)/(1-4*x-x^2) + O(x^100)) \\ _Altug Alkan_, Dec 10 2015

%Y Cf. A000032, A000045, A104934, A005054, A063727 (inverse binomial transform), A082761 (binomial transform), A001076, A001077.

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

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_