|
%I #156 Jun 28 2023 17:42:09
%S 0,1,3,13,51,205,819,3277,13107,52429,209715,838861,3355443,13421773,
%T 53687091,214748365,858993459,3435973837,13743895347,54975581389,
%U 219902325555,879609302221,3518437208883,14073748835533
%N a(n) = 3*a(n-1) + 4*a(n-2), a(0) = 0, a(1) = 1.
%C Inverse binomial transform of powers of 5 (A000351) preceded by 0. - _Paul Barry_, Apr 02 2003
%C Number of walks of length n between any two distinct vertices of the complete graph K_5. Example: a(2)=3 because the walks of length 2 between the vertices A and B of the complete graph ABCDE are: ACB, ADB, AEB. - _Emeric Deutsch_, Apr 01 2004
%C The terms of the sequence are the number of segments (sides) per iteration of the space-filling Peano-Hilbert curve. - _Giorgio Balzarotti_, Mar 16 2006
%C General form: k=4^n-k. Also: A001045, A078008, A097073, A115341, A015518, A054878. - _Vladimir Joseph Stephan Orlovsky_, Dec 11 2008
%C A further inverse binomial transform generates A015441. - _Paul Curtz_, Nov 01 2009
%C For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 3's along the central diagonal, and 2's along the subdiagonal and the superdiagonal. - _John M. Campbell_, Jul 19 2011
%C Pisano period lengths: 1, 1, 2, 2, 10, 2, 6, 2, 6, 10, 10, 2, 6, 6, 10, 2, 4, 6, 18, 10, ... - _R. J. Mathar_, Aug 10 2012
%C Sum_{i=0..m} (-1)^(m+i)*4^i, for m >= 0, gives the terms after 0. - _Bruno Berselli_, Aug 28 2013
%C The ratio a(n+1)/a(n) converges to 4 as n approaches infinity. - _Felix P. Muga II_, Mar 09 2014
%C This is the Lucas sequence U(P=3,Q=-4), and hence for n>=0, a(n+2)/a(n+1) equals the continued fraction 3 + 4/(3 + 4/(3 + 4/(3 + ... + 4/3))) with n 4's. - _Greg Dresden_, Oct 07 2019
%C For n > 0, gcd(a(n), a(n+1)) = 1. - _Kengbo Lu_, Jul 27 2020
%H Vincenzo Librandi, <a href="/A015521/b015521.txt">Table of n, a(n) for n = 0..1000</a>
%H A. Abdurrahman, <a href="https://arxiv.org/abs/1909.10889">CM Method and Expansion of Numbers</a>, arXiv:1909.10889 [math.NT], 2019.
%H Jean-Paul Allouche, Jeffrey Shallit, Zhixiong Wen, Wen Wu, and Jiemeng Zhang, <a href="https://arxiv.org/abs/1911.01687">Sum-free sets generated by the period-k-folding sequences and some Sturmian sequences</a>, arXiv:1911.01687 [math.CO], 2019.
%H J. Borowska and L. Lacinska, <a href="https://doi.org/10.17512/jamcm.2014.4.03">Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix</a>, J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for permanent of tridiagonal Toeplitz matrices a=3, b=2.
%H Ji Young Choi, <a href="https://www.emis.de/journals/JIS/VOL21/Choi/choi10.html">A Generalization of Collatz Functions and Jacobsthal Numbers</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
%H E. M. García-Caballero, S. G. Moreno, and M. P. Prophet, <a href="http://dx.doi.org/10.1016/j.amc.2014.09.018">A complete view of Viète-like infinite products with Fibonacci and Lucas numbers</a>, Applied Mathematics and Computation 247 (2014) 703-711.
%H Dale Gerdemann, <a href="https://www.youtube.com/watch?v=g7uzUfUPWoo">Fractal generated from (3,4) recursion A015521</a>, YouTube Video, Dec 4, 2014.
%H F. P. Muga II, <a href="https://www.researchgate.net/publication/267327689_Extending_the_Golden_Ratio_and_the_Binet-de_Moivre_Formula">Extending the Golden Ratio and the Binet-de Moivre Formula</a>, March 2014; Preprint on ResearchGate.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,4).
%F From _Paul Barry_, Apr 02 2003: (Start)
%F a(n) = (4^n - (-1)^n)/5.
%F E.g.f.: (exp(4*x) - exp(-x))/5. (End)
%F a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*5^(k-1). - _Paul Barry_, May 13 2003
%F a(2*n) = 4*a(2*n-1) - 1, a(2*n+1) = 4*a(2*n) + 1. In general this is true for all sequences of the type a(n) + a(n+1) = q^(n): i.e., a(2*n) = q*a(2n-1) - 1 and a(2*n+1) = q*a(2*n) + 1. - _Amarnath Murthy_, Jul 15 2003
%F From _Emeric Deutsch_, Apr 01 2004: (Start)
%F a(n) = 4^(n-1) - a(n-1).
%F G.f.: x/(1-3*x - 4*x^2). (End)
%F a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*3^(n-2k)*4^k. - _Paul Barry_, Jul 29 2004
%F a(n) = 4*a(n-1) - (-1)^n, n > 0, a(0)=0. - _Paul Barry_, Aug 25 2004
%F a(n) = Sum_{k=0..n} A155161(n,k)*2^(n-k), n >= 1. - _Philippe Deléham_, Jan 27 2009
%F a(n) = round(4^n/5). - _Mircea Merca_, Dec 28 2010
%F The logarithmic generating function 1/5*log((1+x)/(1-4*x)) = x + 3*x^2/2 + 13*x^3/3 + 51*x^4/4 + ... has compositional inverse 5/(4+exp(-5*x)) - 1, the e.g.f. for a signed version of A213127. - _Peter Bala_, Jun 24 2012
%F a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-5)^k = (4^n - (-1)^n)/5 = (-1)^(n-1)*Sum_{k=0..n-1} (-4)^k. Equals (-1)^(n-1)*Phi(n,-4), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - _Tom Copeland_, Apr 14 2014
%F a(n+1) = 2^(2*n) - a(n), a(0) = 0. - _Ben Paul Thurston_, Dec 25 2015
%F a(n) = A247281(n)/5. - _Altug Alkan_, Jan 08 2016
%F From _Kengbo Lu_, Jul 27 2020: (Start)
%F a(n) = 3*Sum_{k=0..n-1} a(k) + 1 if n odd; a(n) = 3*Sum_{k=0..n-1} a(k) if n even.
%F a(n) = A030195(n) + Sum_{k=0..n-2} a(k)*A030195(n-k-1).
%F a(n) = A085449(n) + Sum_{k=0..n-1} a(k)*A085449(n-k).
%F a(n) = F(n) + 2*Sum_{k=0..n-1} a(k)*F(n-k) + 3*Sum_{k=0..n-2} a(k)*F(n-k-1), where F(n) denotes the Fibonacci numbers.
%F a(n) = F(n) + Sum_{k=0..n-1} a(k)*(L(n-k) + F(n-k+1)), where F(n) denotes the Fibonacci numbers and L(n) denotes the Lucas numbers.
%F a(n) = 3^(n-1) + 4*Sum_{k=0..n-2} 3^(n-k-2)*a(k).
%F a(m+n) = a(m)*a(n+1) + 4*a(m-1)*a(n).
%F a(2*n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)*3^(2n-2i-2j-1)*4^(i+j). (End)
%e G.f. = x + 3*x^2 + 13*x^3 + 51*x^4 + 205*x^5 + 819*x^6 + 3277*x^7 + 13107*x^8 + ...
%p seq(round(4^n/5),n=0..25) # _Mircea Merca_, Dec 28 2010
%t k=0;lst={k};Do[k=4^n-k;AppendTo[lst, k], {n, 0, 5!}];lst (* _Vladimir Joseph Stephan Orlovsky_, Dec 11 2008 *)
%t LinearRecurrence[{3,4}, {0,1}, 30] (* _Harvey P. Dale_, Jun 26 2012 *)
%t CoefficientList[Series[x/((1 - 4 x) (1 + x)), {x, 0, 50}], x] (* _Vincenzo Librandi_, Mar 26 2014 *)
%o (Sage) [lucas_number1(n,3,-4) for n in range(0, 24)] # _Zerinvary Lajos_, Apr 22 2009
%o (Magma) [Floor(4^n/5-(-1)^n/5): n in [0..30]]; // _Vincenzo Librandi_, Jun 24 2011
%o (PARI) a(n) = 4^n/5-(-1)^n/5; \\ _Altug Alkan_, Jan 08 2016
%o (PARI) first(n) = Vec(x/(1 - 3*x - 4*x^2) + O(x^n), -n) \\ _Iain Fox_, Dec 30 2017
%o (Python)
%o def A015521(n): return ((1<<(n<<1))|1)//5 # _Chai Wah Wu_, Jun 28 2023
%Y Cf. A001045, A015518, A054878, A078008, A097073, A109200, A115341, A201455, A213127, A247281.
%K nonn,easy
%O 0,3
%A _Olivier Gérard_
| 