

A004253


a(n) = 5*a(n1)  a(n2), with a(1)=1, a(2)=4.
(Formerly M3553)


38



1, 4, 19, 91, 436, 2089, 10009, 47956, 229771, 1100899, 5274724, 25272721, 121088881, 580171684, 2779769539, 13318676011, 63813610516, 305749376569, 1464933272329, 7018916985076, 33629651653051, 161129341280179
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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*nk, k)*j^(nk) = (1)^n * U(2*n, i*sqrt(j)/2), i=sqrt(1).  Paul Barry, Mar 13 2005
Number of 01avoiding 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 (2n2) X (2n2) 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
Values of x (or y) in the solutions to x^2  5xy + y^2 + 3 = 0.  Colin Barker, Feb 04 2014
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(n1, 5), y(n) = x(n1)], for n =oo..+oo, with the Chebyshev Spolynomials (A049310), with S(1, 0) = 0, and S(n, x) =  S(n2, 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(n1), for n >= 1, in terms of Spolynomials 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)
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(n1) = S(n1, 5)  S(n2, 5) and Y(n) = (x(n)  x(n1))/3 = S(n1, 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(n1)^2 / a(n2)), 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 466467 (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), 129154.
F. A. Haight, On a generalization of Pythagoras' theorem, pp. 7377 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



FORMULA

G.f.: x*(1  x) / (1  5*x + x^2). Simon Plouffe in his 1992 dissertation.[offset 0]
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^(ni)*binomial(2*ni, 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) = ((sqrt(21)3)*((5+sqrt(21))/2)^n + (sqrt(21)+3)*((5sqrt(21))/2)^n)/2/sqrt(21).  Seiichi Kirikami, Sep 06 2011
a(n) = S(n1, 5)  S(n2, 5) = (1)^n*S(2*n, i*sqrt(3)), n >= 1, with the Chebyshev S polynomials (A049310), and S(n1, 5) = A004254(n), for n >= 0. See a Paul Barry formula (offset corrected).  Wolfdieter Lang, Oct 15 2020
a(n) = a(1n).
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.


MAPLE

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


MATHEMATICA



PROG

(Sage) [lucas_number1(n, 5, 1)lucas_number1(n1, 5, 1) for n in range(1, 23)] # Zerinvary Lajos, Nov 10 2009
(Magma) [ n eq 1 select 1 else n eq 2 select 4 else 5*Self(n1)Self(n2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011
(GAP) a:=[1, 4];; for n in [3..30] do a[n]:=5*a[n1]a[n2]; od; a; # G. C. Greubel, Oct 23 2019


CROSSREFS

Cf. similar sequences listed in A238379.


KEYWORD

nonn,easy


AUTHOR



EXTENSIONS



STATUS

approved



