login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001353 a(n) = 4*a(n-1) - a(n-2) with a(0) = 0, a(1) = 1.
(Formerly M3499 N1420)
123
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

3*a(n)^2 + 1 is a perfect 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) = 4a(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

If M is any term of the sequence, the next one is 2M + sqrt(3M^2 + 1). - Lekraj Beedassy, Feb 18 2002

n such that 3*n^2=floor(sqrt(3)*n*ceil(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 (2n-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*A011835(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 generates many brilliant (A078972) numbers for a(p) with prime p: a(2) = 4 = 2 * 2 a(3) = 15 = 3 * 5 a(5) = 209 = 11 * 19 a(7) = 2911 = 41 * 71 a(19) = 21252634831 = 110771 * 191861 a(37) = 419245718107612602961 = 15558008491 * 26947261171. Is this a prime-free sequence? If not, what is its first prime? - Jonathan Vos Post, Feb 08 2005

Numbers such that there is an m with t(n+m)=3t(m), where t(n) are the triangular numbers A000217. For instance t(35)=3t(20)=630, so 35-20=15 is in the sequence. - Floor van Lamoen (fvlamoen(AT)hotmail.com), Oct 13 2005

a(n) = number of unique 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:

.__.............__ ...........__.............__

|..|..|........|__...|.......|.....|........|...__|

|...__|........|...__|.......|..|__|........|...__|. - Dennis P. Walsh, Oct 04 2006

[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

From Gary W. Adamson, Jun 21 2009: (Start)

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 one's in the super and subdiagonals and (4,4,4,...) as the main diagonal. [Corrected by Johannes Boot, Sep 04 2011]

A001835 and A001353 = right and next to right borders of triangle A125077. (End)

Number of units of a(n) belongs to a periodic sequence: 0, 1, 4, 5, 6, 9. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), 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

REFERENCES

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) - From N. J. A. Sloane, May 30 2012

M. N. Deshpande, One Interesting Family of Diophantine Triplets, International Journal of Mathematical Education In Science and Technology, Vol. 33 (No. 2, Mar-Apr), 2002.

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.

Y.-H. Guo, n-Colour even self-inverse compositions, Proc. Indian Acad. Sci. (Math. Sci.), 120 (2010), 27-33.

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

T. D. Noe, Table of n, a(n) for n=0..200

W. K. Alt, Enumeration of Domino Tilings on the Projective Grid Graph, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013.

Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607.

E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242.

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamilton cycles in product graphs

F. Faase, Results from the counting program

D. Fortin, B-spline Toeplitz Inverse Under Corner Perturbations, International Journal of Pure and Applied Mathematics, Volume 77, No. 1, 2012, 107-118. - From N. J. A. Sloane, Oct 22 2012

Andrew Granville and Zhi-Wei Sun, Values of Bernoulli polynomials, Pacific J. Math. 172 (1996), 117-137, at p. 119.

T. N. E. Greville, Table for third-degree spline interpolations with equally spaced arguments, Math. Comp., 24 (1970), 179-183.

B. Hopkins, Spotted tilings and n-color compositions, INTEGERS 12B (2012/2013), #A6.

A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case a=0,b=1; p=4, q=-1.

W. D. Hoskins, Table for third-degree spline interpolation using equi-spaced knots, Math. Comp., 25 (1971), 797-801.

Tanya Khovanova, Recursive Sequences

Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.

Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.

W. Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419; Eq.(44), lhs, m=6.

Hojoo Lee, Problems in elementary number theory Problem I 18.

E. Keith Lloyd, The Standard Deviation of 1, 2,..., n: Pell's Equation and Rational Triangles, Math. Gaz. vol 81 (1997), 231-243.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

P. Raff, Analysis of the Number of Spanning Trees of K_2 x P_n. Contains sequence, recurrence, generating function, and more. [From Paul Raff, Mar 06 2009]

D. P. Walsh, Counting n x 2 Simple Rectangular Mazes

F. V. Waugh and M. W. Maxfield, Side-and-diagonal numbers, Math. Mag., 40 (1967), 74-83.

Eric Weisstein's World of Mathematics, Ladder Graph

Eric Weisstein's World of Mathematics, Spanning Tree

Index entries for sequences related to linear recurrences with constant coefficients, signature (4,-1)

Index entries for sequences related to Chebyshev polynomials.

FORMULA

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

a(n)=((2+sqrt(3))^n-(2-sqrt(3))^n)/(2*sqrt(3)).

a(-n) = -a(n). - Michael Somos, Sep 19 2008

Limit as n-> infinity of a(n)/a(n-1) = 2 + sqrt(3). - Gregory V. Richardson, Oct 06 2002

Binomial transform of A002605.

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-2k)}. - Paul Barry, Oct 25 2004

a(n)=sum{k=0..n-1, binomial(n+k, 2k+1)2^k}. - Paul Barry, Nov 30 2004

a(n)=3*a(n-1)+3*a(n-2)-a(n-3); a(0)=0, a(1)=1, a(2)=4. - Lekraj Beedassy, Jul 13 2006

a(n) = 2*a(n-1)+sqrt(3*a(n-1)^2+1). a(n) = -A106707(n). - R. J. Mathar, Jul 07 2006

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 (bhmd95(AT)yahoo.fr), 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) = -i*sin(n*arccos(2))/sqrt(3). - Eric W. Weisstein, Jul 16 2011

a(n) = sinh(n*arccosh(2))/sqrt(3). - 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

a(n) = sqrt(A098301(n))=sqrt([A055793 / 3]), base 3 analog of A031150. - M. F. Hasler, Jan 16 2012

a(n+1) = Sum_{k, 0<=k<=n} A101950(n,k)*3^k. - Philippe Deléham, Feb 10 2012

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+1) = (A001834(n) + A001835(n))/2; a(n+1)+a(n) = A001834(n); a(n+1)-a(n) = A001835(n). - Richard R. Forberg, Sep 04 2013

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

A001353 := proc(n) option remember; if n <= 1 then 1+3*n else 4*A001353(n-1)-A001353(n-2); fi; end;

A001353:=z/(1-4*z+z**2); [Simon Plouffe in his 1992 dissertation.]

MATHEMATICA

a[n_] := (MatrixPower[{{1, 2}, {1, 3}}, n].{{1}, {1}})[[2, 1]]; Table[ a[n], {n, 0, 23}] (* Robert G. Wilson v, Jan 13 2005 *)

Table[GegenbauerC[n-1, 1, 2]], {n, 0, 23}] (* Zerinvary Lajos, Jul 14 2009 *)

Table[-((I Sin[n ArcCos[2]])/Sqrt[3]), {n, 0, 23}] // FunctionExpand (* Eric W. Weisstein, Jul 16 2011 *)

Table[Sinh[n ArcCosh[2]]/Sqrt[3], {n, 0, 23}] // FunctionExpand (* Eric W. Weisstein, Jul 16 2011 *)

Table[ChebyshevU[-1 + n, 2], {n, 0, 23}] (* 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, 23}] (* Alonso del Arte, Jul 19 2011 *)

LinearRecurrence[{4, -1}, {0, 1}, 50] (* 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) = subst( polchebyshev(n-1, 2), x, 2)}; /* Michael Somos, Sep 19 2008 */

(Sage) [lucas_number1(n, 4, 1) for n in xrange(0, 25)] # Zerinvary Lajos, Apr 22 2009

(Haskell)

a001353 n = a001353_list !! n

a001353_list =

   0 : 1 : zipWith (-) (map (4 *) $ tail a001353_list) a001353_list

-- Reinhard Zumkeller, Aug 14 2011

CROSSREFS

a(n) = sqrt((A001075(n)^2-1)/3).

Cf. A003500, A001835, A001075, A001571, A001834, A002531, A005246, A016064, A082840, A079935, A078972.

A bisection of A002530.

Cf. A125077. - Gary W. Adamson, Jun 21 2009

Cf. A001542, A001835.

A row of A116469.

Sequence in context: A191606 A221859 A010905 * A106707 A125905 A195503

Adjacent sequences:  A001350 A001351 A001352 * A001354 A001355 A001356

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 24 05:31 EDT 2014. Contains 240953 sequences.