|
|
A001353
|
|
a(n) = 4*a(n-1) - a(n-2) with a(0) = 0, a(1) = 1.
(Formerly M3499 N1420)
|
|
183
|
|
|
0, 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, 564719, 2107560, 7865521, 29354524, 109552575, 408855776, 1525870529, 5694626340, 21252634831, 79315912984, 296011017105, 1104728155436, 4122901604639, 15386878263120, 57424611447841, 214311567528244
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
3*a(n)^2 + 1 is a square. Moreover, 3*a(n)^2 + 1 = (2*a(n) - a(n-1))^2.
Consecutive terms give nonnegative solutions to x^2 - 4*x*y + y^2 = 1. - Max Alekseyev, Dec 12 2012
Values y solving the Pellian x^2 - 3*y^2 = 1; corresponding x values given by A001075(n). Moreover, we have a(n) = 2*a(n-1) + A001075(n-1). - Lekraj Beedassy, Jul 13 2006
Number of spanning trees in 2 X n grid: by examining what happens at the right-hand end we see that a(n) = 3*a(n-1) + 2*a(n-2) + 2*a(n-3) + ... + 2*a(1) + 1, where the final 1 corresponds to the tree ==...=| !. Solving this we get a(n) = 4*a(n-1) - a(n-2).
Complexity of 2 X n grid.
A016064 also describes triangles whose sides are consecutive integers and in which an inscribed circle has an integer radius. A001353 is exactly and precisely mapped to the integer radii of such inscribed circles, i.e., for each term of A016064, the corresponding term of A001353 gives the radius of the inscribed circle. - Harvey P. Dale, Dec 28 2000
n such that 3*n^2 = floor(sqrt(3)*n*ceiling(sqrt(3)*n)). - Benoit Cloitre, May 10 2003
For n>0, ratios a(n+1)/a(n) may be obtained as convergents of the continued fraction expansion of 2+sqrt(3): either as successive convergents of [4;-4] or as odd convergents of [3;1, 2]. - Lekraj Beedassy, Sep 19 2003
Ways of packing a 3 X (2*n-1) rectangle with dominoes, after attaching an extra square to the end of one of the sides of length 3. With reference to A001835, therefore: a(n) = a(n-1) + A001835(n-1) and A001835(n) = 3*A001835(n-1) + 2*a(n-1). - Joshua Zucker and the Castilleja School Math Club, Oct 28 2003
a(n+1) is a Chebyshev transform of 4^n, where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)). - Paul Barry, Oct 25 2004
This sequence is prime-free, because a(2n) = a(n) * (a(n+1)-a(n-1)) and a(2n+1) = a(n+1)^2 - a(n)^2 = (a(n+1)+a(n)) * (a(n+1)-a(n)). - Jianing Song, Jul 06 2019
Numbers such that there is an m with t(n+m) = 3*t(m), where t(n) are the triangular numbers A000217. For instance, t(35) = 3*t(20) = 630, so 35 - 20 = 15 is in the sequence. - Floor van Lamoen, Oct 13 2005
a(n) = number of distinct matrix products in (A + B + C + D)^n where commutator [A,B] = 0 but neither A nor B commutes with C or D. - Paul D. Hanna and Max Alekseyev, Feb 01 2006
For n > 1, middle side (or long leg) of primitive Pythagorean triangles having an angle nearing Pi/3 with larger values of sides. [Complete triple (X, Y, Z), X < Y < Z, is given by X = A120892(n), Y = a(n), Z = A120893(n), with recurrence relations X(i+1) = 2*{X(i) - (-1)^i} + a(i); Z(i+1) = 2*{Z(i) + a(i)} - (-1)^i.] - Lekraj Beedassy, Jul 13 2006
Number of 2 X n simple rectangular mazes. A simple rectangular m X n maze is a graph G with vertex set {0, 1, ..., m} X {0, 1, ..., n} that satisfies the following two properties: (i) G consists of two orthogonal trees; (ii) one tree has a path that sequentially connects (0,0),(0,1), ..., (0,n), (1,n), ...,(m-1,n) and the other tree has a path that sequentially connects (1,0), (2,0), ..., (m,0), (m,1), ..., (m,n). For example, a(2) = 4 because there are four 2 X 2 simple rectangular mazes:
__ __ __ __
| | | |__ | | | | __|
| __| | __| | |__| | __|
(End)
[1, 4, 15, 56, 209, ...] is the Hankel transform of [1, 1, 5, 26, 139, 758, ...](see A005573). - Philippe Deléham, Apr 14 2007
The upper principal convergents to 3^(1/2), beginning with 2/1, 7/4, 26/15, 97/56, comprise a strictly decreasing sequence; numerators=A001075, denominators=A001353. - Clark Kimberling, Aug 27 2008
A001353 and A001835 = bisection of continued fraction [1, 2, 1, 2, 1, 2, ...], i.e., of [1, 3, 4, 11, 15, 41, ...].
For n>0, a(n) equals the determinant of an (n-1) X (n-1) tridiagonal matrix with ones in the super and subdiagonals and (4, 4, 4, ...) as the main diagonal. [Corrected by Johannes Boot, Sep 04 2011]
Number of units of a(n) belongs to a periodic sequence: 0, 1, 4, 5, 6, 9. - Mohamed Bouhamida, Sep 04 2009
a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 4's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011
2a(n) is the number of n-color compositions of 2n consisting of only even parts; see Guo in references. - Brian Hopkins, Jul 19 2011
Pisano period lengths: 1, 2, 6, 4, 3, 6, 8, 4, 18, 6, 10, 12, 12, 8, 6, 8, 18, 18, 5, 12, ... - R. J. Mathar, Aug 10 2012
a(n) is defined also by the recurrence a(1)=1; for n>1, a(n+1) = 2*a(n) + sqrt(3*a(n)^2 + 1) where a(n) is an integer for every n. This sequence is generalizable by the sequence b(n,m) of parameter m with the initial condition b(1,m) = 1, and for n > 1 b(n+1,m) = m*b(n,m) + sqrt((m^2 - 1)*b(n,m)^2 + 1) for m = 2, 3, 4, ... where b(n,m) is an integer for every n.
The first corresponding sequences are
....................
We obtain a general sequence of polynomials {b(n,x)} = {1, 2*x, 4*x^2 - 1, 8*x^3 - 4*x, 16*x^4 - 12*x^2 + 1, 32*x^5 - 32*x^3 + 6*x, ... } with x = m where each b(n,x) is a Gegenbauer polynomial defined by the recurrence b(n,x)- 2*x*b(n-1,x) + b(n-2,x) = 0, the same relation as the Chebyshev recurrence, but with the initial conditions b(x,0) = 1 and b(x,1) = 2*x instead b(x,0) = 1 and b(x,1) = x for the Chebyshev's polynomials. (End)
If a(n) denotes the n-th term of the above sequence and we construct a triangle whose sides are a(n) - 1, a(n) + 1 and sqrt(3a(n)^2 + 1), then, for every n the measure of one of the angles of the triangle so constructed will always be 120 degrees. This result of ours was published in Mathematics Spectrum (2012/2013), Vol. 45, No. 3, pp. 126-128. - K. S. Bhanu and Dr. M. N. Deshpande, Professor (Retd), Department of Statistics, Institute of Science, Nagpur (India).
For n >= 1, a(n) equals the number of 01-avoiding words of length n - 1 on alphabet {0, 1, 2, 3}. - Milan Janjic, Jan 25 2015
For n > 0, 10*a(n) is the number of vertices and roots on level n of the {4, 5} mosaic (see L. Németh Table 1 p. 6). - Michel Marcus, Oct 30 2015
(2 + sqrt(3))^n = A001075(n) + a(n)*sqrt(3), n >= 0; integers in the quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 16 2018
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Dec 12 2019
The Cholesky decomposition A = C C* for tridiagonal A with A[i,i] = 4 and A[i+1,i] = A[i,i+1] = -1, as it arises in the discretized 2D Laplace operator (Poisson equation...), has nonzero elements C[i,i] = sqrt(a(i+1)/a(i)) = -1/C[i+1,i], i = 1, 2, 3, ... - M. F. Hasler, Mar 12 2021
The triples (a(n-1), 2a(n), a(n+1)), n=2,3,..., are exactly the triples (a,b,c) of positive integers a < b < c in arithmetic progression such that a*b+1, b*c+1, and c*a+1 are perfect squares. - Bernd Mulansky, Jul 10 2021
|
|
REFERENCES
|
J. Austin and L. Schneider, Generalized Fibonacci sequences in Pythagorean triple preserving sequences, Fib. Q., 58:1 (2020), 340-350.
Bastida, Julio R., Quadratic properties of a linearly recurrent sequence. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 163-166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009)
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 163.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.
J. D. E. Konhauser et al., Which Way Did the Bicycle Go?, MAA 1996, p. 104.
Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x/(1-4*x+x^2).
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(2*sqrt(3)).
E.g.f.: exp(2*x)*sinh(sqrt(3)*x)/sqrt(3).
a(n) = S(n-1, 4) = U(n-1, 2); S(-1, x) := 0, Chebyshev's polynomials of the second kind A049310.
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)(-1)^k*4^(n - 2*k). - Paul Barry, Oct 25 2004
a(n) = Sum_{k=0..n-1} binomial(n+k,2*k+1)*2^k. - Paul Barry, Nov 30 2004
a(n) = 3*(a(n-1) + a(n-2)) - a(n-3), a(n) = 5*(a(n-1) - a(n-2)) + a(n-3). - Mohamed Bouhamida, Sep 20 2006
M^n * [1,0] = [A001075(n), A001353(n)], where M = the 2 X 2 matrix [2,3; 1,2]; e.g., a(4) = 56 since M^4 * [1,0] = [97, 56] = [A001075(4), A001353(4)]. - Gary W. Adamson, Dec 27 2006
Sequence satisfies 1 = f(a(n), a(n+1)) where f(u, v) = u^2 + v^2 - 4*u*v. - Michael Somos, Sep 19 2008
Rational recurrence: a(n) = (17*a(n-1)*a(n-2) - 4*(a(n-1)^2 + a(n-2)^2))/a(n-3) for n > 3. - Jaume Oliver Lafont, Dec 05 2009
If p[i] = Fibonacci(2i) and if A is the 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, May 08 2010
a(n) = C_{n-1}^{(1)}(2), where C_n^{(m)}(x) is the Gegenbauer polynomial. - Eric W. Weisstein, Jul 16 2011
a(n) = b such that Integral_{x=0..Pi/2} (sin(n*x))/(2-cos(x)) dx = c + b*log(2). - Francesco Daddi, Aug 02 2011
1, 4, 15, 56, 209, ... = INVERT(INVERT(1, 2, 3, 4, 5, ...)). - David Callan, Oct 13 2012
Product_{n >= 1} (1 + 1/a(n)) = 1 + sqrt(3). - Peter Bala, Dec 23 2012
Product_{n >= 2} (1 - 1/a(n)) = 1/4*(1 + sqrt(3)). - Peter Bala, Dec 23 2012
a(n) = -(-i)^(n+1)*Fibonacci(n, 4*i), i = sqrt(-1). - G. C. Greubel, Jun 06 2019
a(n)^2 - a(m)^2 = a(n+m) * a(n-m), a(n+2)*a(n-2) = 16*a(n+1)*a(n-1) - 15*a(n)^2, a(n+3)*a(n-2) = 15*a(n+2)*a(n-1) - 14*a(n+1)*a(n) for all integer n, m. - Michael Somos, Dec 12 2019
a(n) = 2^n*Sum_{k >= n} binomial(2*k,2*n-1)*(1/3)^(k+1). Cf. A102591. - Peter Bala, Nov 29 2021
a(n) = Sum_{k > 0} (-1)^((k-1)/2)*binomial(2*n, n+k)*(k|12), where (k|12) is the Kronecker symbol. - Greg Dresden, Oct 11 2022
|
|
EXAMPLE
|
For example, when n = 3:
****
.***
.***
can be packed with dominoes in 4 different ways: 3 in which the top row is tiled with two horizontal dominoes and 1 in which the top row has two vertical and one horizontal domino, as shown below, so a(2) = 4.
---- ---- ---- ||--
.||| .--| .|-- .|||
.||| .--| .|-- .|||
G.f. = x + 4*x^2 + 15*x^3 + 56*x^4 + 209*x^5 + 780*x^6 + 2911*x^7 + 10864*x^8 + ...
|
|
MAPLE
|
seq( simplify(ChebyshevU(n-1, 2)), n=0..20); # G. C. Greubel, Dec 23 2019
|
|
MATHEMATICA
|
a[n_] := (MatrixPower[{{1, 2}, {1, 3}}, n].{{1}, {1}})[[2, 1]]; Table[ a[n], {n, 0, 30}] (* Robert G. Wilson v, Jan 13 2005 *)
Table[GegenbauerC[n-1, 1, 2]], {n, 0, 30}] (* Zerinvary Lajos, Jul 14 2009 *)
Table[-((I Sin[n ArcCos[2]])/Sqrt[3]), {n, 0, 30}] // FunctionExpand (* Eric W. Weisstein, Jul 16 2011 *)
Table[Sinh[n ArcCosh[2]]/Sqrt[3], {n, 0, 30}] // FunctionExpand (* Eric W. Weisstein, Jul 16 2011 *)
a[0]:=0; a[1]:=1; a[n_]:= a[n]= 4a[n-1] - a[n-2]; Table[a[n], {n, 0, 30}] (* Alonso del Arte, Jul 19 2011 *)
LinearRecurrence[{4, -1}, {0, 1}, 30] (* Sture Sjöstedt, Dec 06 2011 *)
|
|
PROG
|
(PARI) M = [ 1, 1, 0; 1, 3, 1; 0, 1, 1]; for(i=0, 30, print1(([1, 0, 0]*M^i)[2], ", ")) \\ Lambert Klasen (Lambert.Klasen(AT)gmx.net), Jan 25 2005
(PARI) {a(n) = real( (2 + quadgen(12))^n / quadgen(12) )}; /* Michael Somos, Sep 19 2008 */
(PARI) {a(n) = polchebyshev(n-1, 2, 2)}; /* Michael Somos, Sep 19 2008 */
(PARI) concat(0, Vec(x/(1-4*x+x^2) + O(x^30))) \\ Altug Alkan, Oct 30 2015
(Sage) [lucas_number1(n, 4, 1) for n in range(30)] # Zerinvary Lajos, Apr 22 2009
(Sage) [chebyshev_U(n-1, 2) for n in (0..20)] # G. C. Greubel, Dec 23 2019
(Haskell)
a001353 n = a001353_list !! n
a001353_list =
0 : 1 : zipWith (-) (map (4 *) $ tail a001353_list) a001353_list
(GAP) a:=[0, 1];; for n in [3..30] do a[n]:=4*a[n-1]-a[n-2]; od; a; # Muniru A Asiru, Feb 16 2018
(Magma) I:=[0, 1]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..30]]; // G. C. Greubel, Jun 06 2019
(Python)
a001353 = [0, 1]
for n in range(30): a001353.append(4*a001353[-1] - a001353[-2])
|
|
CROSSREFS
|
Cf. A001075, A001542, A001571, A001834, A001835, A002531, A003500, A005246, A016064, A079935, A082840.
Chebyshev sequence U(n, m): A000027 (m=1), this sequence (m=2), A001109 (m=3), A001090 (m=4), A004189 (m=5), A004191 (m=6), A007655 (m=7), A077412 (m=8), A049660 (m=9), A075843 (m=10), A077421 (m=11), A077423 (m=12), A097309 (m=13), A097311 (m=14), A097313 (m=15), A029548 (m=16), A029547 (m=17), A144128 (m=18), A078987 (m=19), A097316 (m=33).
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|