The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A001835 a(n) = 4*a(n-1) - a(n-2), with a(0) = 1, a(1) = 1. (Formerly M2894 N1160) 66

%I M2894 N1160

%S 1,1,3,11,41,153,571,2131,7953,29681,110771,413403,1542841,5757961,

%T 21489003,80198051,299303201,1117014753,4168755811,15558008491,

%U 58063278153,216695104121,808717138331,3018173449203,11263976658481

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

%C See A079935 for another version.

%C Number of ways of packing a 3 X 2*(n-1) rectangle with dominoes. - David Singmaster.

%C Equivalently, number of perfect matchings of the P_3 X P_{2(n-1)} lattice graph. - _Emeric Deutsch_, Dec 28 2004

%C The terms of this sequence are the positive square roots of the indices of the octagonal numbers (A046184) - Nicholas S. Horne (nairon(AT)loa.com), Dec 13 1999

%C Terms are the solutions to: 3*x^2 - 2 is a square. - _Benoit Cloitre_, Apr 07 2002

%C Gives solutions x>0 of the equation floor(x*r*floor(x/r)) == floor(x/r*floor(x*r)) where r = 1 + sqrt(3). - _Benoit Cloitre_, Feb 19 2004

%C a(n) = L(n-1,4), where L is defined as in A108299; see also A001834 for L(n,-4). - _Reinhard Zumkeller_, Jun 01 2005

%C Values x + y, where (x, y) solves for x^2 - 3*y^2 = 1, i.e., a(n) = A001075(n) + A001353(n). - _Lekraj Beedassy_, Jul 21 2006

%C Number of 01-avoiding words of length n on alphabet {0,1,2,3} which do not end in 0. (E.g., for n = 2 we have 02, 03, 11, 12, 13, 21, 22, 23, 31, 32, 33.) - _Tanya Khovanova_, Jan 10 2007

%C sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571) + ... - _Gary W. Adamson_, Dec 18 2007

%C The lower principal convergents to 3^(1/2), beginning with 1/1, 5/3, 19/11, 71/41, comprise a strictly increasing sequence; numerators = A001834, denominators = A001835. - _Clark Kimberling_, Aug 27 2008

%C From _Gary W. Adamson_, Jun 21 2009: (Start)

%C A001835 and A001353 = bisection of denominators of continued fraction [1, 2, 1, 2, 1, 2, ...]; i.e., bisection of A002530.

%C a(n) = determinant of an n*n tridiagonal matrix with 1's in the super- and sub-diagonals and (3, 4, 4, 4, ...) as the main diagonal.

%C Also, the product of the eigenvalues of such matrices: a(n) = Product_{k=1..(n-1)/2)} (4 + 2*cos(2*k*Pi/n).

%C (End)

%C Let M = a triangle with the even-indexed Fibonacci numbers (1, 3, 8, 21, ...) in every column, and the leftmost column shifted up one row. a(n) starting (1, 3, 11, ...) = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - _Gary W. Adamson_, Jul 27 2010

%C a(n+1) is the number of compositions of n when there are 3 types of 1 and 2 types of other natural numbers. - _Milan Janjic_, Aug 13 2010

%C For n >= 2, a(n) equals the permanent of the (2*n-2) X (2*n-2) tridiagonal matrix with sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - _John M. Campbell_, Jul 08 2011

%C Primes in the sequence are apparently those in A096147. - _R. J. Mathar_, May 09 2013

%C Except for the first term, positive values of x (or y) satisfying x^2 - 4xy + y^2 + 2 = 0. - _Colin Barker_, Feb 04 2014

%C Except for the first term, positive values of x (or y) satisfying x^2 - 14xy + y^2 + 32 = 0. - _Colin Barker_, Feb 10 2014

%C The (1,1) element of A^n where A = (1, 1, 1; 1, 2, 1; 1, 1, 2). - _David Neil McGrath_, Jul 23 2014

%C Yong Hao Ng has shown that for any n, a(n) is coprime with any member of A001834 and with any member of A001075. - _René Gy_, Feb 25 2018

%C a(n+1) is the number of spanning trees of the graph T_n, where T_n is a 2 X n grid with an additional vertex v adjacent to (1,1) and (2,1). - _Kevin Long_, May 04 2018

%D R. C. Alperin, A family of nonlinear recurrences and their linear solutions, Fib. Q., 57:4 (2019), 318-321.

%D 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)

%D L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 375.

%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.

%D Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics I, p. 292.

%H T. D. Noe, <a href="/A001835/b001835.txt">Table of n, a(n) for n = 0..200</a>

%H Krassimir T. Atanassov and Anthony G. Shannon, <a href="https://doi.org/10.7546/nntdm.2020.26.3.218-223">On intercalated Fibonacci sequences</a>, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 218-223.

%H Steve Butler, Paul Horn, and Eric Tressler, <a href="http://www.fq.math.ca/Papers1/48-2/Butler_Horn_Tressler.pdf">Intersecting Domino Tilings</a>, Fibonacci Quart. 48 (2010), no. 2, 114-120.

%H Niccolò Castronuovo, <a href="https://arxiv.org/abs/2102.02739">On the number of fixed points of the map gamma</a>, arXiv:2102.02739 [math.NT], 2021. Mentions this sequence.

%H A. Consilvio et al., <a href="http://www.maa.org/pubs/FOCUSJun-Jul12_tanton.html">Tilings, ordered partitions, and weird languages</a>, MAA FOCUS, June/July 2012, 16-17.

%H J. B. Cosgrave and K. Dilcher, <a href="http://johnbcosgrave.com/publications.php">A role for generalized Fermat numbers</a>, Math. Comp., to appear 2016; (See paper #10).

%H J. B. Cosgrave and K. Dilcher, <a href="https://doi.org/10.1090/mcom/3111">A role for generalized Fermat numbers</a>, Math. Comp. 86 (2017), 899-933.

%H L. Euler, <a href="http://www.mathematik.uni-bielefeld.de/~sieben/euler/euler_2.djvu">Vollstaendige Anleitung zur Algebra, Zweiter Teil</a>.

%H F. Faase, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.2790">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H Alex Fink, Richard K. Guy, and Mark Krusemeyer, <a href="https://doi.org/10.11575/cdm.v3i2.61940">Partitions with parts occurring at most thrice</a>, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.

%H H. Hosoya and A. Motoyama, <a href="http://dx.doi.org/10.1063/1.526778">An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices</a>, J. Math. Physics 26 (1985) 157-167 (Table V).

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=409">Encyclopedia of Combinatorial Structures 409</a>

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H Clark Kimberling, <a href="http://dx.doi.org/10.1007/s000170050020">Best lower and upper approximates to irrational numbers</a>, Elemente der Mathematik, 52 (1997) 122-126.

%H David Klarner and Jordan Pollack, <a href="http://dx.doi.org/10.1016/0012-365X(80)90098-9">Domino tilings of rectangles with fixed width</a>, Disc. Math. 32 (1980) 45-52.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings</a>, arXiv:1311.6135 [math.CO], 2013, Table 2.

%H R. J. Mathar, <a href="https://arxiv.org/abs/1406.7788">Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices</a>, arXiv:1406.7788 (2014), eq. (4).

%H Valcho Milchev and Tsvetelina Karamfilova, <a href="https://arxiv.org/abs/1707.09741">Domino tiling in grid - new dependence</a>, arXiv:1707.09741 [math.HO], 2017.

%H Yong Hao Ng, <a href="https://math.stackexchange.com/a/2664328/130022">A partition in three classes of the set of all prime numbers?</a>, Math StackExchange.

%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arxiv.org/abs/1403.5962">Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions</a>, arXiv preprint arXiv:1403.5962 [math.CO], 2014.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Jaime Rangel-Mondragon, <a href="https://web.archive.org/web/20190411024906/http://www.mathematica-journal.com/issue/v9i3/polyominoes.html">Polyominoes and Related Families</a>, The Mathematica Journal, 9:3 (2005), 609-640.

%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.

%H David Singmaster, <a href="/A005178/a005178.pdf">Letter to N. J. A. Sloane</a>, Oct 3 1982.

%H Thotsaporn ”Aek” Thanatipanonda, <a href="https://www.fq.math.ca/Papers1/57-5/thanatipanonda.pdf">Statistics of Domino Tilings on a Rectangular Board</a>, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.

%H Herman Tulleken, <a href="https://www.researchgate.net/publication/333296614_Polyominoes">Polyominoes 2.2: How they fit together</a>, (2019).

%H F. V. Waugh and M. W. Maxfield, <a href="http://www.jstor.org/stable/2688511">Side-and-diagonal numbers</a>, Math. Mag., 40 (1967), 74-83.

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

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

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

%F G.f.: (1 - 3*x)/(1 - 4*x + x^2). - _Simon Plouffe_ in his 1992 dissertation

%F a(1-n) = a(n).

%F a(n) = ((3 + sqrt(3))^(2*n - 1) + (3 - sqrt(3))^(2*n - 1))/6^n. - _Dean Hickerson_, Dec 01 2002

%F a(n) = (8 + a(n-1)*a(n-2))/a(n-3). - _Michael Somos_, Aug 01, 2001

%F a(n+1) = Sum_{k=0..n} (2^k * binomial(n + k, n - k), n >= 0. - _Len Smiley_, Dec 09 2001

%F Lim_{n->infinity} a(n)/a(n-1) = 2 + sqrt(3). - _Gregory V. Richardson_, Oct 10 2002

%F a(n) = 2*A061278(n-1) + 1 for n > 0. - Bruce Corrigan (scentman(AT)myfamily.com), Nov 04 2002

%F Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n - i, i); then q(n, 2) = a(n+1). - _Benoit Cloitre_, Nov 10 2002

%F a(n+1) = Sum_{k=0..n} ((-1)^k)*((2*n+1)/(2*n + 1 - k))*binomial(2*n + 1 - k, k)*6^(n - k) (from standard T(n,x)/x, n >= 1, Chebyshev sum formula). The Smiley and Cloitre sum representation is that of the S(2*n, i*sqrt(2))*(-1)^n Chebyshev polynomial. - _Wolfdieter Lang_, Nov 29 2002

%F a(n) = S(n-1, 4) - S(n-2, 4) = T(2*n-1, sqrt(3/2))/sqrt(3/2) = S(2*(n-1), i*sqrt(2))*(-1)^(n - 1), with S(n, x) := U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first, kind. See A049310 and A053120. S(-1, x) = 0, S(-2, x) = -1, S(n, 4) = A001353(n+1), T(-1, x) = x.

%F a(n+1) = sqrt((A001834(n)^2 + 2)/3), n >= 0 (see Cloitre comment).

%F Sequence satisfies -2 = f(a(n), a(n+1)) where f(u, v) = u^2 + v^2 - 4*u*v. - _Michael Somos_, Sep 19 2008

%F a(n) = (1/6)*(3*(2 - sqrt(3))^n + sqrt(3)*(2 - sqrt(3))^n + 3*(2 + sqrt(3))^n - sqrt(3)*(2 + sqrt(3))^n) (Mathematica's solution to the recurrence relation). - Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009

%F If p[1] = 3, p[i] = 2, (i > 1), and if A is 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+1) = det A. - _Milan Janjic_, Apr 29 2010

%F a(n) = (a(n-1)^2 + 2)/a(n-2). - _Irene Sermon_, Oct 28 2013

%F a(n) = A001353(n+1) - 3*A001353(n). - _R. J. Mathar_, Oct 30 2015

%F a(n) = a(n-1) + 2*A001353(n-1). - _Kevin Long_, May 04 2018

%F From _Franck Maminirina Ramaharo_, Nov 11 2018: (Start)

%F a(n) = (-1)^n*(A125905(n) + 3*A125905(n-1)), n > 0.

%F E.g.f.: exp^(2*x)*(3*cosh(sqrt(3)*x) - sqrt(3)*sinh(sqrt(3)*x))/3. (End)

%p f:=n->((3+sqrt(3))^(2*n-1)+(3-sqrt(3))^(2*n-1))/6^n; [seq(simplify(expand(f(n))),n=0..20)]; # _N. J. A. Sloane_, Nov 10 2009

%t CoefficientList[Series[(1-3x)/(1-4x+x^2), {x, 0, 24}], x] (* _Jean-François Alcover_, Jul 25 2011, after g.f. *)

%t LinearRecurrence[{4,-1},{1,1},30] (* _Harvey P. Dale_, Jun 08 2013 *)

%t Table[Round@Fibonacci[2n-1, Sqrt[2]], {n, 0, 20}] (* _Vladimir Reshetnikov_, Sep 15 2016 *)

%t Table[(3*ChebyshevT[n, 2] - ChebyshevU[n, 2])/2, {n, 0, 20}] (* _G. C. Greubel_, Dec 23 2019 *)

%o (PARI) {a(n) = real( (2 + quadgen(12))^n * (1 - 1 / quadgen(12)) )} /* _Michael Somos_, Sep 19 2008 */

%o (PARI) {a(n) = subst( (polchebyshev(n) + polchebyshev(n-1)) / 3, x, 2)} /* _Michael Somos_, Sep 19 2008 */

%o (Sage) [lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in range(25)] # _Zerinvary Lajos_, Apr 29 2009

%o (Sage) [(3*chebyshev_T(n,2) - chebyshev_U(n,2))/2 for n in (0..20)] # _G. C. Greubel_, Dec 23 2019

%o a001835 n = a001835_list !! n

%o a001835_list =

%o 1 : 1 : zipWith (-) (map (4 *) \$ tail a001835_list) a001835_list

%o -- _Reinhard Zumkeller_, Aug 14 2011

%o (MAGMA) [n le 2 select 1 else 4*Self(n-1)-Self(n-2): n in [1..25]]; // _Vincenzo Librandi_, Sep 16 2016

%o (GAP) a:=[1,1];; for n in [3..20] do a[n]:=4*a[n-1]-a[n-2]; od; a; # _G. C. Greubel_, Dec 23 2019

%Y Row 3 of array A099390.

%Y Essentially the same as A079935.

%Y First differences of A001353.

%Y Partial sums of A052530.

%Y Pairwise sums of A006253.

%Y Bisection of A002530, A005246 and A048788.

%Y First column of array A103997.

%Y Cf. A001519, A003699, A082841, A101265, A125077, A001353, A001542.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

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

Last modified April 21 15:55 EDT 2021. Contains 343156 sequences. (Running on oeis4.)