A015518 - OEIS

%I #254 May 11 2024 09:34:12

%S 0,1,2,7,20,61,182,547,1640,4921,14762,44287,132860,398581,1195742,

%T 3587227,10761680,32285041,96855122,290565367,871696100,2615088301,

%U 7845264902,23535794707,70607384120,211822152361,635466457082

%N a(n) = 2*a(n-1) + 3*a(n-2), with a(0)=0, a(1)=1.

%C Number of walks of length n between any two distinct vertices of the complete graph K_4. - _Paul Barry_ and _Emeric Deutsch_, Apr 01 2004

%C For n >= 1, a(n) is the number of integers k, 1 <= k <= 3^(n-1), whose ternary representation ends in an even number of zeros (see A007417). - _Philippe Deléham_, Mar 31 2004

%C Form the digraph with matrix A=[0,1,1,1;1,0,1,1;1,1,0,1;1,0,1,1]. A015518(n) corresponds to the (1,3) term of A^n. - _Paul Barry_, Oct 02 2004

%C The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the denominators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is 2. - _Cino Hilliard_, Sep 25 2005

%C (A046717(n))^2 + (2*a(n))^2 = A046717(2n). E.g., A046717(3) = 13, 2*a(3) = 14, A046717(6) = 365. 13^2 + 14^2 = 365. - _Gary W. Adamson_, Jun 17 2006

%C For n >= 2, number of ordered partitions of n-1 into parts of sizes 1 and 2 where there are two types of 1 (singletons) and three types of 2 (twins). For example, the number of possible configurations of families of n-1 male (M) and female (F) offspring considering only single births and twins, where the birth order of M/F/pair-of-twins is considered and there are three types of twins; namely, both F, both M, or one F and one M - where birth order within a pair of twins itself is disregarded. In particular, for a(3)=7, two children could be either: (1) F, then M; (2) M, then F; (3) F,F; (4) M,M; (5) F,F twins; (6) M,M twins; or (7) M,F twins (emphasizing that birth order is irrelevant here when both/all children are the same gender and when two children are within the same pair of twins). - _Rick L. Shepherd_, Sep 18 2004

%C a(n) is prime for n = {2, 3, 5, 7, 13, 23, 43, 281, 359, ...}, where only a(2) = 2 corresponds to a prime of the form (3^k - 1)/4. All prime terms, except a(2) = 2, are the primes of the form (3^k + 1)/4. Numbers k such that (3^k + 1)/4 is prime are listed in A007658. Note that all prime terms have prime indices. Prime terms are listed in A111010. - _Alexander Adamchuk_, Nov 19 2006

%C Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-2, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=charpoly(A,1). - _Milan Janjic_, Jan 26 2010

%C Select an odd size subset S from {1,2,...,n}, then select an even size subset from S. - _Geoffrey Critzer_, Mar 02 2010

%C a(n) is the number of ternary sequences of length n where the numbers of (0's, 1's) are (even, odd) respectively, and, by symmetry, the number of such sequences where those numbers are (odd, even) respectively. A122983 covers (even, even), and A081251 covers (odd, odd). - _Toby Gottfried_, Apr 18 2010

%C An elephant sequence, see A175654. For the corner squares just one A[5] vector, with decimal value 341, leads to this sequence (without the leading 0). For the central square this vector leads to the companion sequence A046717 (without the first leading 1). - _Johannes W. Meijer_, Aug 15 2010

%C Let R be the commutative algebra resulting from adjoining the elements of the Klein four-group to the integers (equivalently, K = Z[x,y,z]/{x*y - z, y*z - x, x*z - y, x^2 - 1, y^2 - 1, z^2 - 1}). Then a(n) is equal to the coefficients of x, y, and z in the expansion of (x + y + z)^n. - Joseph E. Cooper III (easonrevant(AT)gmail.com), Nov 06 2010

%C Pisano period lengths:  1, 2, 2, 4, 4, 2, 6, 8, 2, 4, 10, 4, 6, 6, 4, 16, 16, 2, 18, 4, ... - _R. J. Mathar_, Aug 10 2012

%C The ratio a(n+1)/a(n) converges to 3 as n approaches infinity. - _Felix P. Muga II_, Mar 09 2014

%C This is a divisibility sequence, also the values of Chebyshev polynomials, and also the number of ways of packing a 2 X n-1 rectangle with dominoes and unit squares. - _R. K. Guy_, Dec 16 2016

%C For n>0, gcd(a(n),a(n+1))=1. - _Kengbo Lu_, Jul 02 2020

%D John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.

%H Vincenzo Librandi, <a href="/A015518/b015518.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 K. Böhmová, C. Dalfó, and C. Huemer, <a href="http://hdl.handle.net/2117/80848">On cyclic Kautz digraphs</a>, Reasearch Report, 2015.

%H G. Bowlin and M. G. Brin, <a href="http://arxiv.org/abs/1301.3984">Coloring Planar Graphs via Colored Paths in the Associahedra</a>, arXiv preprint arXiv:1301.3984 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 12 2013

%H AJ Bu and Doron Zeilberger, <a href="https://arxiv.org/abs/2305.09030">Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas</a>, arXiv:2305.09030 [math.CO], 2023.

%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 Sergio Falcón, <a href="https://www.rgnpublications.com/journals/index.php/cma/article/viewFile/1221/950">Binomial Transform of the Generalized k-Fibonacci Numbers</a>, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.

%H Dale Gerdemann, <a href="https://www.youtube.com/watch?v=i6gDh_ZB3vo">Fractal generated from (2,3) recursion</a>, YouTube Video, Dec 05 2014.

%H R. J. Mathar, <a href="/A102518/a102518.pdf">Counting Walks on Finite Graphs</a>, Nov 2020, Section 2.

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

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,3).

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%F G.f.: x/((1+x)*(1-3*x)).

%F a(n) = (3^n - (-1)^n)/4 = floor(3^n/4 + 1/2).

%F a(n) = 3^(n-1) - a(n-1). - _Emeric Deutsch_, Apr 01 2004

%F E.g.f.: (exp(3*x) - exp(-x))/4. Second inverse binomial transform of (5^n-1)/4, A003463. Inverse binomial transform for powers of 4, A000302 (when preceded by 0). - _Paul Barry_, Mar 28 2003

%F a(n) = Sum_{k=0..floor(n/2)} C(n, 2k+1)*2^(2k). - _Paul Barry_, May 14 2003

%F a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*4^(k-1). - _Paul Barry_, Apr 02 2003

%F a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*2^(n-2*k)*3^k. - _Paul Barry_, Jul 13 2004

%F a(n) = U(n-1, i/sqrt(3))(-i*sqrt(3))^(n-1), i^2=-1. - _Paul Barry_, Nov 17 2003

%F G.f.: x*(1+x)^2/(1 - 6*x^2 - 8*x^3 - 3*x^4) = x(1+x)^2/characteristic polynomial(x^4*adj(K_4)(1/x)). - _Paul Barry_, Feb 03 2004

%F a(n) = sum_{k=0..3^(n-1)} A014578(k) = -(-1)^n*A014983(n) = A051068(3^(n-1)), for n > 0. - _Philippe Deléham_, Mar 31 2004

%F E.g.f.: exp(x)*sinh(2*x)/2. - _Paul Barry_, Oct 02 2004

%F a(2*n+1) = A054880(n) + 1. - _M. F. Hasler_, Mar 20 2008

%F 2*a(n) + (-1)^n = A046717(n). - _M. F. Hasler_, Mar 20 2008

%F a(n) = ((1+sqrt(4))^n - (1-sqrt(4))^n)/4. - Al Hakanson (hawkuu(AT)gmail.com), Dec 31 2008

%F a(n) = abs(A014983(n)). - _Zerinvary Lajos_, May 28 2009

%F a(n) = round(3^n/4). - _Mircea Merca_, Dec 28 2010

%F a(n) = Sum_{k=1,3,5,...} binomial(n,k)*2^(k-1). - _Geoffrey Critzer_, Mar 02 2010

%F From _Sergei N. Gladkovskii_, Jul 19 2012: (Start)

%F G.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + 1/G(k+1)))))); (continued fraction).

%F E.g.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - (2*k+1)/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + (2*k+2)/G(k+1)))))); (continued fraction).  (End)

%F G.f.: G(0)*x/(2*(1-x)), where G(k) = 1 + 1/(1 - x*(4*k-1)/(x*(4*k+3) - 1/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 26 2013

%F a(n+1) = Sum_{k = 0..n} A238801(n,k)*2^k. - _Philippe Deléham_, Mar 07 2014

%F a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-4)^k = (-1)^(n-1)*Sum_{k=0..n-1} (-3)^k. Equals (-1)^(n-1)*Phi(n,-3), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - _Tom Copeland_, Apr 14 2014

%F a(n) = 2*A006342(n-1) - n mod 2 if n > 0, a(0)=0. - _Yuchun Ji_, Nov 30 2018

%F a(n) = 2*A033113(n-2) + n mod 2 if n > 0, a(0)=0. - _Yuchun Ji_, Aug 16 2019

%F a(2*k) = 2*A002452(k), a(2*k+1) = A066443(k). - _Yuchun Ji_, Aug 14 2019

%F a(n+1) = 2*Sum_{k=0..n} a(k) if n odd, and 1 + 2*Sum_{k=0..n} a(k) if n even. - _Kengbo Lu_, May 30 2020

%F a(n) = F(n) + Sum_{k=1..(n-1)} a(k)*L(n-k), for F(n) and L(n) the Fibonacci and Lucas numbers. - _Kengbo Lu_ and _Greg Dresden_, Jun 05 2020

%F From _Kengbo Lu_, Jun 11 2020: (Start)

%F a(n) = A002605(n) + Sum_{k = 1..n-2} a(k)*A002605(n-k-1).

%F a(n) = A006130(n-1) + Sum_{k = 1..n-1} a(k)*A006130(n-k-1). (End)

%F a(2n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)* 2^(2n-2i-2j-1)* 3^(i+j). - _Kengbo Lu_, Jul 02 2020

%F a(n) = 3*a(n-1) - (-1)^n. - _Dimitri Papadopoulos_, Nov 28 2023

%F G.f.: x/((1 + x)*(1 - 3*x)) = Sum_{n >= 0} x^(n+1) * Product_{k = 1..n} (k + 3*x + 1)/(1 + k*x) (a telescoping series). Cf. A007482. - _Peter Bala_, May 08 2024

%t Table[(3^n-(-1)^n)/4,{n,0,30}] (* _Alexander Adamchuk_, Nov 19 2006 *)

%o (PARI) a(n)=round(3^n/4)

%o (Sage) [round(3^n/4) for n in range(0,27)]

%o (Magma) [Round(3^n/4): n in [0..30]]; // _Vincenzo Librandi_, Jun 24 2011

%o (Python) for n in range(0, 20): print(int((3**n-(-1)**n)/4), end=', ') # _Stefano Spezia_, Nov 30 2018

%o (Maxima) a(n):= round(3^n/4)$ /* _Dimitri Papadopoulos_, Nov 28 2023 */

%Y a(n) = A080926(n-1) + 1 = (1/3)*A054878(n+1) = (1/3)*abs(A084567(n+1)).

%Y First differences of A033113 and A039300.

%Y Partial sums of A046717.

%Y The following sequences (and others) belong to the same family: A000129, A001333, A002532, A002533, A002605, A015518, A015519, A026150, A046717, A063727, A083098, A083099, A083100, A084057.

%Y Cf. A046717.

%Y Cf. A007658, A111010.

%Y Cf. A001045, A078008, A097073, A115341. - _Vladimir Joseph Stephan Orlovsky_, Dec 11 2008

%Y Cf. A007482, A059260.

%K nonn,walk,easy

%O 0,3

%A _Olivier Gérard_

%E More terms from _Emeric Deutsch_, Apr 01 2004

%E Edited by _Ralf Stephan_, Aug 30 2004