|
|
A015521
|
|
a(n) = 3*a(n-1) + 4*a(n-2), a(0) = 0, a(1) = 1.
|
|
56
|
|
|
0, 1, 3, 13, 51, 205, 819, 3277, 13107, 52429, 209715, 838861, 3355443, 13421773, 53687091, 214748365, 858993459, 3435973837, 13743895347, 54975581389, 219902325555, 879609302221, 3518437208883, 14073748835533
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Inverse binomial transform of powers of 5 (A000351) preceded by 0. - Paul Barry, Apr 02 2003
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
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
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
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
Sum_{i=0..m} (-1)^(m+i)*4^i, for m >= 0, gives the terms after 0. - Bruno Berselli, Aug 28 2013
The ratio a(n+1)/a(n) converges to 4 as n approaches infinity. - Felix P. Muga II, Mar 09 2014
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
For n > 0, gcd(a(n), a(n+1)) = 1. - Kengbo Lu, Jul 27 2020
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (4^n - (-1)^n)/5.
E.g.f.: (exp(4*x) - exp(-x))/5. (End)
a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*5^(k-1). - Paul Barry, May 13 2003
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
a(n) = 4^(n-1) - a(n-1).
G.f.: x/(1-3*x - 4*x^2). (End)
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*3^(n-2k)*4^k. - Paul Barry, Jul 29 2004
a(n) = 4*a(n-1) - (-1)^n, n > 0, a(0)=0. - Paul Barry, Aug 25 2004
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
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
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.
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.
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.
a(n) = 3^(n-1) + 4*Sum_{k=0..n-2} 3^(n-k-2)*a(k).
a(m+n) = a(m)*a(n+1) + 4*a(m-1)*a(n).
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)
|
|
EXAMPLE
|
G.f. = x + 3*x^2 + 13*x^3 + 51*x^4 + 205*x^5 + 819*x^6 + 3277*x^7 + 13107*x^8 + ...
|
|
MAPLE
|
|
|
MATHEMATICA
|
LinearRecurrence[{3, 4}, {0, 1}, 30] (* Harvey P. Dale, Jun 26 2012 *)
CoefficientList[Series[x/((1 - 4 x) (1 + x)), {x, 0, 50}], x] (* Vincenzo Librandi, Mar 26 2014 *)
|
|
PROG
|
(Sage) [lucas_number1(n, 3, -4) for n in range(0, 24)] # Zerinvary Lajos, Apr 22 2009
(PARI) a(n) = 4^n/5-(-1)^n/5; \\ Altug Alkan, Jan 08 2016
(PARI) first(n) = Vec(x/(1 - 3*x - 4*x^2) + O(x^n), -n) \\ Iain Fox, Dec 30 2017
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|