A004253 a(n) = 5*a(n-1) - a(n-2), with a(1)=1, a(2)=4.

1, 4, 19, 91, 436, 2089, 10009, 47956, 229771, 1100899, 5274724, 25272721, 121088881, 580171684, 2779769539, 13318676011, 63813610516, 305749376569, 1464933272329, 7018916985076, 33629651653051, 161129341280179, 772017054747844, 3698955932459041, 17722762607547361

Offset: 1

Author

Frans J. Faase, Per H. Lundow

Keywords

• nonn
• easy

Comments

Number of domino tilings in K_3 X P_2n (or in S_4 X P_2n).

Number of perfect matchings in graph C_{3} X P_{2n}.

Number of perfect matchings in S_4 X P_2n.

In general, Sum_{k=0..n} binomial(2*n-k, k)*j^(n-k) = (-1)^n * U(2*n, i*sqrt(j)/2), i=sqrt(-1). - Paul Barry, Mar 13 2005

a(n) = L(n,5), where L is defined as in A108299; see also A030221 for L(n,-5). - Reinhard Zumkeller, Jun 01 2005

Number of 01-avoiding words of length n on alphabet {0,1,2,3,4} which do not end in 0 (e.g., at n=2, we have 02, 03, 04, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44). - Tanya Khovanova, Jan 10 2007

(sqrt(21)+5)/2 = 4.7912878... = exp(arccosh(5/2)) = 4 + 3/4 + 3/(4*19) + 3/(19*91) + 3/(91*436) + ... - Gary W. Adamson, Dec 18 2007

a(n+1) is the number of compositions of n when there are 4 types of 1 and 3 types of other natural numbers. - Milan Janjic, Aug 13 2010

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

Right-shifted Binomial Transform of the left-shifted A030195. - R. J. Mathar, Oct 15 2012

Values of x (or y) in the solutions to x^2 - 5xy + y^2 + 3 = 0. - Colin Barker, Feb 04 2014

From Wolfdieter Lang, Oct 15 2020: (Start)

All positive solutions of the Diophantine equation x^2 + y^2 - 5*x*y = -3 (see the preceding comment) are given by [x(n) = S(n, 5) - S(n-1, 5), y(n) = x(n-1)], for n =-oo..+oo, with the Chebyshev S-polynomials (A049310), with S(-1, 0) = 0, and S(-|n|, x) = - S(|n|-2, x), for |n| >= 2.

This binary indefinite quadratic form has discriminant D = +21. There is only this family representing -3 properly with x and y positive, and there are no improper solutions.

See the formula for a(n) = x(n-1), for n >= 1, in terms of S-polynomials below.

This comment is inspired by a paper by Robert K. Moniot (private communication). See his Oct 04 2020 comment in A027941 related to the case of x^2 + y^2 - 3*x*y = -1 (special Markov solutions). (End)

From Wolfdieter Lang, Feb 08 2021: (Start)

All proper and improper solutions of the generalized Pell equation X^2 - 21*Y^2 = +4 are given, up to a combined sign change in X and Y, in terms of x(n) = a(n+1) from the preceding comment by X(n) = x(n) + x(n-1) = S(n-1, 5) - S(n-2, 5) and Y(n) = (x(n) - x(n-1))/3 = S(n-1, 5), for all integer numbers n. For positive integers X(n) = A003501(n) and Y(n) = A004254(n). X(-n) = X(n) and Y(-n) = - Y(n), for n >= 1.

The two conjugated proper families of solutions are given by [X(3*n+1), Y(3*n+1)] and [X(3*n+2), Y(3*n+2)], and the one improper family by [X(3*n), Y(3*n)], for all integer n. This follows from the mentioned paper by Robert K. Moniot. (End)

Equivalent definition: a(n) = ceiling(a(n-1)^2 / a(n-2)), with a(1)=1, a(2)=4, a(3)=19. The problem for USA Olympiad (see Andreescu and Gelca reference) asks to prove that a(n)-1 is always a multiple of 3. - Bernard Schott, Apr 13 2022

References

• Titu Andreescu and Rǎzvan Gelca, Putnam and Beyond, New York, Springer, 2007, problem 311, pp. 104 and 466-467 (proposed for the USA Mathematical Olympiad by G. Heuer).
• F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
• F. A. Haight, On a generalization of Pythagoras' theorem, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971.
• 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 = 1..200
• 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 Hamiltonian cycles in product graphs
• F. Faase, Results from the counting program
• Alex Fink, Richard K. Guy, and Mark Krusemeyer, Partitions with parts occurring at most thrice, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.
• Frank A. Haight, Letter to N. J. A. Sloane, Sep 06 1976
• Frank A. Haight, On a generalization of Pythagoras' theorem, pp. 73-77 of J. C. Butcher, editor, A Spectrum of Mathematics. Auckland University Press, 1971. [Annotated scanned copy]
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 422
• Tanya Khovanova, Recursive Sequences
• Lisa Lokteva, Constructing Rational Homology 3-Spheres That Bound Rational Homology 4-Balls, arXiv:2208.14850 [math.GT], 2022.
• Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
• Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
• J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962, 2014
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
• James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2
• F. M. van Lamoen, Square wreaths around hexagons, Forum Geometricorum, 6 (2006) 311-325.
• Index entries for sequences related to dominoes
• Index entries for linear recurrences with constant coefficients, signature (5,-1).

Crossrefs

Cf. A003501, A004254, A030221, A049310, A004254 (partial sums), A290902 (first differences).

Row 5 of array A094954.

Cf. similar sequences listed in A238379.

Programs

GAP

a:=[1,4];; for n in [3..30] do a[n]:=5*a[n-1]-a[n-2]; od; a; # G. C. Greubel, Oct 23 2019

Magma

[ n eq 1 select 1 else n eq 2 select 4 else 5*Self(n-1)-Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011

Maple

a[0]:=1: a[1]:=1: for n from 2 to 26 do a[n]:=5*a[n-1]-a[n-2] od: seq(a[n], n=1..22); # Zerinvary Lajos, Jul 26 2006

Mathematica

LinearRecurrence[{5, -1}, {1, 4}, 22] (* Jean-François Alcover, Sep 27 2017 *)

PARI

Vec((1-x)/(1-5*x+x^2)+O(x^30)) \\ Charles R Greathouse IV, Jul 01 2013

Sage

[lucas_number1(n,5,1)-lucas_number1(n-1,5,1) for n in range(1, 23)] # Zerinvary Lajos, Nov 10 2009

Formula

G.f.: x*(1 - x) / (1 - 5*x + x^2). Simon Plouffe in his 1992 dissertation.[offset 0]

For n>1, a(n) = A005386(n) + A005386(n-1). - Floor van Lamoen, Dec 13 2006

a(n) ~ (1/2 + 1/14*sqrt(21))*(1/2*(5 + sqrt(21)))^n. - Joe Keane (jgk(AT)jgk.org), May 16 2002[offset 0]

Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i), then q(n, 3)=a(n). - Benoit Cloitre, Nov 10 2002 [offset 0]

For n>0, a(n)*a(n+3) = 15 + a(n+1)*a(n+2). - Ralf Stephan, May 29 2004

a(n) = Sum_{k=0..n} binomial(n+k, 2k)*3^k. - Paul Barry, Jul 26 2004[offset 0]

a(n) = (-1)^n*U(2n, i*sqrt(3)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - Paul Barry, Mar 13 2005[offset 0]

[a(n), A004254(n)] = the 2 X 2 matrix [1,3; 1,4]^n * [1,0]. - Gary W. Adamson, Mar 19 2008

a(n) = ((sqrt(21)-3)*((5+sqrt(21))/2)^n + (sqrt(21)+3)*((5-sqrt(21))/2)^n)/2/sqrt(21). - Seiichi Kirikami, Sep 06 2011

a(n) = S(n-1, 5) - S(n-2, 5) = (-1)^n*S(2*n, i*sqrt(3)), n >= 1, with the Chebyshev S polynomials (A049310), and S(n-1, 5) = A004254(n), for n >= 0. See a Paul Barry formula (offset corrected). - Wolfdieter Lang, Oct 15 2020

From Peter Bala, Feb 10 2024: (Start)

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

a(n) = A004254(n) + A004254(1-n).

For n, j, k in Z, a(n)*a(n+j+k) - a(n+j)*a(n+k) = 3*A004254(j)*A004254(k). The case j = 1, k = 2 is given above.

a(n)^2 + a(n+1)^2 - 5*a(n)*a(n+1) = - 3.

More generally, a(n)^2 + a(n+k)^2 - (A004254(k+1) - A004254(k-1))*a(n)*a(n+k) = -3*A004254(k)^2. (End)

Sum_{n >= 2} 1/(a(n) - 1/a(n)) = 1/3 (telescoping series: for n >= 2, 3/(a(n) - 1/a(n)) = 1/A004254(n-1) - 1/A004254(n)). - Peter Bala, May 21 2025

E.g.f.: exp(5*x/2)*(7*cosh(sqrt(21)*x/2) - sqrt(21)*sinh(sqrt(21)*x/2))/7 - 1. - Stefano Spezia, Jul 02 2025

Extensions

Additional comments from James Sellers and N. J. A. Sloane, May 03 2002

More terms from Ray Chandler, Nov 17 2003