A027941 -id:A027941 - cp's OEIS frontend

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

Frans J. Faase, Per H. Lundow

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

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).

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).

Cf. A003501, A004254, A030221, A049310, A004254 (partial sums), A290902 (first differences).
Row 5 of array A094954.
Cf. similar sequences listed in A238379.

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

[ 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

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

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

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

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

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

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

More terms from Ray Chandler, Nov 17 2003

A004146 Alternate Lucas numbers - 2.

Original entry on oeis.org

0, 1, 5, 16, 45, 121, 320, 841, 2205, 5776, 15125, 39601, 103680, 271441, 710645, 1860496, 4870845, 12752041, 33385280, 87403801, 228826125, 599074576, 1568397605, 4106118241, 10749957120, 28143753121, 73681302245, 192900153616, 505019158605, 1322157322201

Offset: 0

N. J. A. Sloane

This is the r=5 member in the r-family of sequences S_r(n) defined in A092184 where more information can be found.
Number of spanning trees of the wheel W_n on n+1 vertices. - Emeric Deutsch, Mar 27 2005
Also number of spanning trees of the n-helm graph. - Eric W. Weisstein, Jul 16 2011
a(n) is the smallest number requiring n terms when expressed as a sum of Lucas numbers (A000204). - David W. Wilson, Jan 10 2006
This sequence has a primitive prime divisor for all terms beyond the twelfth. - Anthony Flatters (Anthony.Flatters(AT)uea.ac.uk), Aug 17 2007
From Giorgio Balzarotti, Mar 11 2009: (Start)
Determinant of power series of gamma matrix with determinant 1:
a(n) = Determinant(A + A^2 + A^3 + A^4 + A^5 + ... + A^n)
where A is the submatrix A(1..2,1..2) of the matrix with factorial determinant
A = [[1,1,1,1,1,1,...],[1,2,1,2,1,2,...],[1,2,3,1,2,3,...],[1,2,3,4,1,2,...],
[1,2,3,4,5,1,...],[1,2,3,4,5,6,...],...]. Note: Determinant A(1..n,1..n)= (n-1)!.
See A158039, A158040, A158041, A158042, A158043, A158044, for sequences of matrix 2!,3!,... (End)
The previous comment could be rephrased as: a(n) = -det(A^n - I) where I is the 2 X 2 identity matrix and A = [1, 1; 1, 2]. - Peter Bala, Mar 20 2015
a(n) is also the number of points of Arnold's "cat map" that are on orbits of period n-1. This is a map of the two-torus T^2 into itself. If we regard T^2 as R^2 / Z^2, the action of this map on a two vector in R^2 is multiplication by the unit-determinant matrix A = [2, 1;1, 1], with the vector components taken modulo one. As such, an explicit formula for the n-th entry of this sequence is -det(I-A^n). - Bruce Boghosian, Apr 26 2009
7*a(n) gives the total number of vertices in a heptagonal hyperbolic lattice {7,3} with n total levels, in which an open heptagon is centered at the origin. - Robert M. Ziff, Apr 10 2011
The sequence is the case P1 = 5, P2 = 6, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Apr 03 2014
Determinants of the spiral knots S(3,k,(1,-1)). a(k) = det(S(3,k,(1,-1))). These knots are also the weaving knots W(k,3) and the Turk's Head Links THK(3,k). - Ryan Stees, Dec 14 2014
Even-indexed Fibonacci numbers (1, 3, 8, 21, ...) convolved with (1, 2, 2, 2, 2, ...). - Gary W. Adamson, Aug 09 2016
a(n) is the number of ways to tile a bracelet of length n with 1-color square, 2-color dominos, 3-color trominos, etc. - Yu Xiao, May 23 2020
a(n) is the number of face-labeled unfoldings of a pyramid whose base is a simple n-gon. Cf. A103536. - Rick Mabry, Apr 17 2023

			For k=3, b(3) = sqrt(5)*b(2) - b(1) = 5 - 1 = 4, so det(S(3,3,(1,-1))) = 4^2 = 16.
G.f. = x + 5*x^2 + 16*x^3 + 45*x^4 + 121*x^5 + 320*x^4 + 841*x^5 + ... - _Michael Somos_, Feb 10 2023

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (p. 193, Problem 3.3.40 (a)).
N. Hartsfield and G. Ringel, Pearls in Graph Theory, p. 102. Academic Press: 1990.
B. Hasselblatt and A. Katok, "Introduction to the Modern Theory of Dynamical Systems," Cambridge University Press, 1997.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..2375 (terms 0..200 from T. D. Noe)
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Polynomial sequences on quadratic curves, Integers, Vol. 15, 2015, #A38.
S. Barbero, U. Cerruti, and N. Murru, On polynomial solutions of the Diophantine equation (x + y - 1)^2 = wxy, Rendiconti Sem. Mat. Univ. Pol. Torino (2020) Vol. 78, No. 1, 5-12.
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See pp. 25, 29.
N. Brothers, S. Evans, L. Taalman, L. Van Wyk, D. Witczak, and C. Yarnall, Spiral knots, Missouri J. of Math. Sci., 22 (2010).
M. DeLong, M. Russell, and J. Schrock, Colorability and determinants of T(m,n,r,s) twisted torus knots for n equiv. +/-1(mod m), Involve, Vol. 8 (2015), No. 3, 361-384.
N. Dowdall, T. Mattman, K. Meek, and P. Solis, On the Harary-Kauffman conjecture and turk's head knots, arxiv 0811.0044 [math.GT], 2008.
A. Flatters, Primitive divisors of some Lehmer-Pierce sequences, arXiv:0708.2190 [math.NT], 2007.
Hang Gu and Robert M. Ziff, Crossing on hyperbolic lattices, arXiv:1111.5626 [cond-mat.dis-nn], 2011 (see footnote 32).
Seong Ju Kim, R. Stees, and L. Taalman, Sequences of Spiral Knot Determinants, Journal of Integer Sequences, Vol. 19 (2016), #16.1.4.
Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
B. R. Myers, Number of spanning trees in a wheel, IEEE Trans. Circuit Theory, 18 (1971), 280-282.
B. R. Myers, Number of spanning trees in a wheel, IEEE Trans. Circuit Theory, 18 (1971), 280-282. [Annotated scanned copy. See the last two pages of the scan, the first few pages are of a different article]
L. Oesper, p-Colorings of Weaving Knots, Undergraduate Thesis, Pomona College, 2005.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Franck Ramaharo, A one-variable bracket polynomial for some Turk's head knots, arXiv:1807.05256 [math.CO], 2018.
Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, and Kamal Ali Alezabi, Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network, PLoS ONE (2020) Vol. 15, No. 8, e0237386.
K. R. Rebman, The sequence: 1 5 16 45 121 320 ... in combinatorics, Fib. Quart., 13 (1975), 51-55.
Harry Richman, Farbod Shokrieh, and Chenxi Wu, Counting two-forests and random cut size via potential theory, arXiv:2308.03859 [math.CO], 2023. See p. 18.
Benoit Rittaud and Laurent Vivier, Circular words and applications, arXiv:1108.3618 [cs.FL], 2011.
Benoit Rittaud and Laurent Vivier, Circular words and three applications: factors of the Fibonacci word, F -adic numbers, and the sequence 1, 5, 16, 45, 121, 320, ... , HAL Id: hal-00566314.
Benoit Rittaud and Laurent Vivier, Circular words and three applications: factors of the Fibonacci word, F -adic numbers, and the sequence 1, 5, 16, 45, 121, 320, ... , Functiones et Approximatio Commentarii Mathematici, Volume 47, Number 2 (2012), 207-231.
Ryan Stees, Sequences of Spiral Knot Determinants, Senior Honors Projects. Paper 84. James Madison Univ., May 2016.
Eric Weisstein's World of Mathematics, Helm Graph
Eric Weisstein's World of Mathematics, Spanning Tree
Eric Weisstein's World of Mathematics, Wheel Graph
Eric Weisstein's World of Mathematics, Arnold's cat map
Wikipedia, Arnold's cat map
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,-4,1).

This is the r=5 member of the family S_r(n) defined in A092184.
Cf. A005248. Partial sums of A002878. Pairwise sums of A027941. Bisection of A074392.
Sequence A032170, the Möbius transform of this sequence, is then the number of prime periodic orbits of Arnold's cat map. - Bruce Boghosian, Apr 26 2009
Cf. A000032, A100047, A001350.
Cf. also A158039, A158040, A158041, A158042, A158043, A158044.
Cf. A103536 for the number of geometrically distinct edge-unfoldings of the regular pyramid. - Rick Mabry, Apr 17 2023

[Lucas(n)-2: n in [0..60 by 2]]; // Vincenzo Librandi, Mar 20 2015

Table[LucasL[2*n] - 2, {n, 0, 20}]
(* Second program: *)
LinearRecurrence[{4, -4, 1}, {0, 1, 5}, 30] (* Jean-François Alcover, Jan 08 2019 *)

a(n) = { we = quadgen(5);((1+we)^n) + ((2-we)^n) - 2;} /* Michel Marcus, Aug 18 2012 */

a(n) = A005248(n) - 2 = A000032(2*n) - 2.
a(n+1) = 3*a(n) - a(n-1) + 2.
G.f.: x*(1+x)/(1-4*x+4*x^2-x^3) = x*(1+x)/((1-x)*(1-3*x+x^2)).
a(n) = 2*(T(n, 3/2)-1) with Chebyshev's polynomials T(n, x) of the first kind. See their coefficient triangle A053120.
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3), n>=3, a(0)=0, a(1)=1, a(2)=5.
a(n) = 2*T(n, 3/2) - 2, with twice the Chebyshev polynomials of the first kind, 2*T(n, x=3/2) = A005248(n).
a(n) = b(n) + b(n-1), n>=1, with b(n):=A027941(n-1), n>=1, b(-1):=0, the partial sums of S(n, 3) = U(n, 3/2) = A001906(n+1), with S(n, x) = U(n, x/2) Chebyshev's polynomials of the second kind.
a(2n) = A000204(2n)^2 - 4 = 5*A000045(2n)^2; a(2n+1) = A000204(2n+1)^2. - David W. Wilson, Jan 10 2006
a(n) = ((3+sqrt(5))/2)^n + ((3-sqrt(5))/2)^n - 2. - Felix Goldberg (felixg(AT)tx.technion.ac.il), Jun 09 2001
a(n) = b(n-1) + b(n-2), n>=1, with b(n):=A027941(n), b(-1):=0, partial sums of S(n, 3) = U(n, 3/2) = A001906(n+1), Chebyshev's polynomials of the second kind.
a(n) = n*Sum_{k=1..n} binomial(n+k-1,2*k-1)/k, n > 0. - Vladimir Kruchinin, Sep 03 2010
a(n) = floor(tau^(2*n)*(tau^(2*n) - floor(tau^(2*n)))), where tau = (1+sqrt(5))/2. - L. Edson Jeffery, Aug 26 2013
From Peter Bala, Apr 03 2014: (Start)
a(n) = U(n-1,sqrt(5)/2)^2, for n >= 1, where U(n,x) denotes the Chebyshev polynomial of the second kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, -3/2; 1, 5/2] and T(n,x) denotes the Chebyshev polynomial of the first kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)
a(k) = det(S(3,k,(1,-1))) = b(k)^2, where b(1)=1, b(2)=sqrt(5), b(k)=sqrt(5)*b(k-1) - b(k-2) = b(2)*b(k-1) - b(k-2). - Ryan Stees, Dec 14 2014
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + Sum_{n >= 1} Fibonacci(2*n)*x^n. Cf. A001350. - Peter Bala, Mar 19 2015
E.g.f.: exp(phi^2*x) + exp(x/phi^2) - 2*exp(x), where phi = (1 + sqrt(5))/2. - G. C. Greubel, Aug 24 2015
a(n) = a(-n) for all n in Z. - Michael Somos, Aug 27 2015
From Peter Bala, Jun 03 2016: (Start)
a(n) = Lucas(2*n) - Lucas(0*n);
a(n)^2 = Lucas(4*n) - 3*Lucas(2*n) + 3*Lucas(0*n) - Lucas(-2*n);
a(n)^3 = Lucas(6*n) - 5*Lucas(4*n) + 10*Lucas(2*n) - 10*Lucas(0*n) + 5*Lucas(-2*n) - Lucas(-4*n) and so on (follows from Binet's formula for Lucas(2*n) and the algebraic identity (x + 1/x - 2)^m = f(x) + f(1/x) where f(x) = (x - 1)^(2*m - 1)/x^(m-1) ). (End)
Limit_{n->infinity} a(n+1)/a(n) = (3 + sqrt(5))/2 = A104457. - Ilya Gutkovskiy, Jun 03 2016
a(n) = (phi^n - phi^(-n))^2, where phi = A001622 = (1 + sqrt(5))/2. - Diego Rattaggi, Jun 10 2020
a(n) = 4*sinh(n*A002390)^2, where A002390 = arcsinh(1/2). - Gleb Koloskov, Sep 18 2021
a(n) = 5*F(n)^2 = L(n)^2 - 4 if n even and a(n) = L(n)^2 = 5*F(n)^2 - 4 if n odd. - Michael Somos, Feb 10 2023
a(n) = n^2 + Sum_{i=1..n-1} i*a(n-i). - Fern Gossow, Dec 03 2024

Correction to formula from Nephi Noble (nephi(AT)math.byu.edu), Apr 09 2002

Chebyshev comments from Wolfdieter Lang, Sep 10 2004

A064831 Partial sums of A001654, or sum of the areas of the first n Fibonacci rectangles.

Original entry on oeis.org

0, 1, 3, 9, 24, 64, 168, 441, 1155, 3025, 7920, 20736, 54288, 142129, 372099, 974169, 2550408, 6677056, 17480760, 45765225, 119814915, 313679521, 821223648, 2149991424, 5628750624, 14736260449, 38580030723, 101003831721

Offset: 0

Howard Stern (hsstern(AT)mindspring.com), Oct 23 2001

The n-th rectangle is F(n)*F(n+1), where F(n) = n-th Fibonacci number (F(1)=1, F(2)=1, F(3)=2, etc.), A000045.
If 2*T(a_n) = the oblong number formed by substituting a(n) in the product formula x(x+1), then 2*T(a_n) = F(n-1)*F(n) * F(n)*F(n+1). Thus a(n) equals the integer part of the square root of the right hand side of the given equation. - Kenneth J Ramsey, Dec 19 2006
Contribution from Johannes W. Meijer, Sep 22 2010: (Start)
The a(n) represent several triangle sums of the Golden Triangle A180662: Kn11 (terms doubled), Kn12(n+1) (terms doubled), Kn4, Ca1 (terms tripled), Ca4, Gi1 (terms quadrupled) and Gi4. See A180662 for the definitions of these sums.
(End)
Define a 2 X (n+1) matrix with elements T(r,0)=A000032(r) and T(r,1) = Fibonacci(r), r=0,1,..,n. The matrix times its transposed is a 2 X 2 matrix with one diagonal element A001654(n+1), the other A216243(n), and A027941(n+1) on both outer diagonals. The determinant of this 2 X 2 matrix is 4*a(n). Example: For n=3 the matrix is 2 X 4 with rows 2 1 3 4; 0 1 1 2 to give as a product the 2 X 2 matrix with rows 30 12; 12 6 and determinant 180-144 = 36 =4*a(3). - J. M. Bergot, Feb 13 2013
a(n+1) is equal to the number of ternary strings of length n without any substring of the form 0x1, where x is in {0,1,2}. - John M. Campbell, Apr 03 2016

Harry J. Smith, Table of n, a(n) for n = 0..200
E. Altinisik, A. Keskin, M. Yildiz, M. Demirbuken, On a conjecture of Ilmonen, Haukkanen and Merikoski concerning the smallest eigenvalues of certain GCD related matrices, Linear Algebra and its Applications, Volume 493, 15 March 2016, Pages 1-13
S. Falcon, On the Sequences of Products of Two k-Fibonacci Numbers, American Review of Mathematics and Statistics, March 2014, Vol. 2, No. 1, pp. 111-120.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (3,0,-3,1).

Cf. A000045, A282464.
Odd terms of A097083.
Partial sums of A001654.

a:=[0,1,3,9];; for n in [5..30] do a[n]:=3*a[n-1]-3*a[n-3]+a[n-4]; od; a; # G. C. Greubel, Jan 09 2019

m:=30; R:=PowerSeriesRing(Integers(), m); [0] cat Coefficients(R!( x/((1-x^2)*(1-3*x+x^2)) )); // G. C. Greubel, Jan 09 2019

Table[ Sum[ Fibonacci[k]*Fibonacci[k + 1], {k, n} ], {n, 0, 30}]
f[n_] := Floor[GoldenRatio^(2 n + 2)/5]; Array[f, 28, 0] (* Robert G. Wilson v, Oct 25 2001 *)
a[0]= 0; a[1]= 1; a[2]= 3; a[3]= 9; a[n_]:= a[n]= 3a[n-1] - 3a[n-3] + a[n-4]; Table[a[n], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 28 2015 *)

PARI
```
a(n)=if(n<0,0,fibonacci(n+1)^2-1+n%2)
```

{ for (n=0, 200, a=fibonacci(n+1)^2 - 1 + n%2; write("b064831.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 27 2009

my(x='x+O('x^30)); concat([0], Vec(x/((1-x^2)*(1-3*x+x^2)))) \\ G. C. Greubel, Jan 09 2019

(x/((1-x^2)*(1-3*x+x^2))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jan 09 2019

a(n) = F(n+1)^2 - 1 if n is even, or F(n+1)^2 if n is odd.
a(n) = A005313(n+1) - n.
G.f.: x/((1-x^2)*(1-3*x+x^2)). - N. J. A. Sloane Jul 15 2002
a(n) = Sum_{k=0..floor(n/2)} U(n-2k-1, 3/2). - Paul Barry, Nov 15 2003
Let M_n denote the n X n Hankel matrix M_n(i, j)=F(i+j-1) where F = A000045 is Fibonacci numbers, then the characteristic polynomial of M_n is x^n - F(2n)x^(n-1) + a(n-1)x^(n-2) . - Michael Somos, Nov 14 2002
a(n) = a(n-1) + A001654(n) with a(0)=0. (Partial sums of A001654). - Johannes W. Meijer, Sep 22 2010
a(n) = floor(phi^(2*n+2)/5), where phi =(1+sqrt(5))/2. - Gary Detlefs Mar 12 2011
a(n) = (A027941(n) + A001654(n))/2, n>=0. - Wolfdieter Lang, Jul 23 2012
a(n) = A005248(n+1)/5 -1/2 -(-1)^n/10. - R. J. Mathar, Feb 21 2013
Recurrence: a(0) = 0, a(1) = 1, a(2) = 3, a(3) = 9, a(n) = 3*a(n-1) - 3*a(n-3) + a(n-4). - Vladimir Reshetnikov, Oct 28 2015
a(n) = Sum_{i=0..n} (n+1-i)*Fibonacci(i)^2. - Bruno Berselli, Feb 20 2017

More terms from Robert G. Wilson v, Oct 25 2001

A030221 Chebyshev even-indexed U-polynomials evaluated at sqrt(7)/2.

Original entry on oeis.org

1, 6, 29, 139, 666, 3191, 15289, 73254, 350981, 1681651, 8057274, 38604719, 184966321, 886226886, 4246168109, 20344613659, 97476900186, 467039887271, 2237722536169, 10721572793574, 51370141431701, 246129134364931, 1179275530392954, 5650248517599839

Offset: 0

Wolfdieter Lang

a(n) = L(n,-5)*(-1)^n, where L is defined as in A108299; see also A004253 for L(n,+5). - Reinhard Zumkeller, Jun 01 2005
General recurrence is a(n) = (a(1)-1)*a(n-1) - a(n-2), a(1) >= 4; lim_{n->oo} a(n) = x*(k*x+1)^n, k =(a(1)-3), x=(1+sqrt((a(1)+1)/(a(1)-3)))/2. Examples in OEIS: a(1)=4 gives A002878. a(1)=5 gives A001834. a(1)=6 gives the present sequence. a(1)=7 gives A002315. a(1)=8 gives A033890. a(1)=9 gives A057080. a(1)=10 gives A057081. - Ctibor O. Zizka, Sep 02 2008
The primes in this sequence are 29, 139, 3191, 15289, 350981, 1681651, ... - Ctibor O. Zizka, Sep 02 2008
Inverse binomial transform of A030240. - Philippe Deléham, Nov 19 2009
For positive n, a(n) equals the permanent of the (2n)X(2n) matrix with sqrt(7)'s along the main diagonal, and i's along the superdiagonal and the subdiagonal (i is the imaginary unit). - John M. Campbell, Jul 08 2011
The aerated sequence (b(n))n>=1 = [1, 0, 6, 0, 29, 0, 139, 0, ...] is a fourth-order linear divisibility sequence; that is, if n | m then b(n) | b(m). It is the case P1 = 0, P2 = -3, Q = -1 of the 3-parameter family of divisibility sequences found by Williams and Guy. See A100047 for a connection with Chebyshev polynomials. - Peter Bala, Mar 22 2015
From Wolfdieter Lang, Oct 26 2020: (Start)
((-1)^n)*a(n) = X(n) = ((-1)^n)*(S(n, 5) + S(n-1, 5)) and Y(n) = X(n-1) gives all integer solutions (modulo sign flip between X and Y) of X^2 + Y^2 + 5*X*Y = +7, for n = -oo..+oo, with Chebyshev S polynomials (see A049310), with S(-1, x) = 0, and S(-n, x) = - S(n-2, x), for n >= 2.
This binary indefinite quadratic form of discriminant 21, representing 7, has only this family of proper solutions (modulo sign flip), and no improper ones.
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)

			G.f. = 1 + 6*x + 29*x^2 + 139*x^3 + 666*x^4 + 3191*x^5 + 15289*x^6 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Polynomial sequences on quadratic curves, Integers, Vol. 15, 2015, #A38.
K. Andersen, L. Carbone, and D. Penta, Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.
K. Dilcher and K. B. Stolarsky, A Pascal-type triangle characterizing twin primes, Amer. Math. Monthly, 112 (2005), 673-681. (see page 678)
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.
Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Generalized Leonardo Number Entries, Ann. Math. Silesianae (2023). See p. 18.
Christian Kassel and Christophe Reutenauer, Pairs of intertwined integer sequences, arXiv:2507.15780 [math.NT], 2025. See p. 13.
Tanya Khovanova, Recursive Sequences.
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38 (2000) 408-419. Eq.(44), rhs, m=6.
Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
Donatella Merlini and Renzo Sprugnoli, Arithmetic into geometric progressions through Riordan arrays, Discrete Mathematics 340.2 (2017): 160-174.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012) The John Selfridge Memorial Volume.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (5,-1).

Cf. A004253, A004254, A100047, A054493 (partial sums), A049310, A003501 (first differences), A299109 (subsequence of primes).

I:=[1,6]; [n le 2 select I[n] else 5*Self(n-1)-Self(n-2): n in [1..30]]; // Vincenzo Librandi, Mar 22 2015

A030221 := proc(n)
    option remember;
    if n <= 1 then
        op(n+1,[1,6]);
    else
        5*procname(n-1)-procname(n-2) ;
    end if;
end proc: # R. J. Mathar, Apr 30 2017

t[n_, k_?EvenQ] := I^k*Binomial[n-k/2, k/2]; t[n_, k_?OddQ] := -I^(k-1)*Binomial[n+(1-k)/2-1, (k-1)/2]; l[n_, x_] := Sum[t[n, k]*x^(n-k), {k, 0, n}]; a[n_] := (-1)^n*l[n, -5]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2013, after Reinhard Zumkeller *)
a[ n_] := ChebyshevU[2 n, Sqrt[7]/2]; (* Michael Somos, Jan 22 2017 *)

{a(n) = simplify(polchebyshev(2*n, 2, quadgen(28)/2))}; /* Michael Somos, Jan 22 2017 */

[(lucas_number2(n,5,1)-lucas_number2(n-1,5,1))/3 for n in range(1,22)] # Zerinvary Lajos, Nov 10 2009

a(n) = 5*a(n-1) - a(n-2), a(-1)=-1, a(0)=1.
a(n) = U(2*n, sqrt(7)/2).
G.f.: (1+x)/(x^2-5*x+1).
a(n) = A004254(n) + A004254(n+1).
a(n) ~ (1/2 + (1/6)*sqrt(21))*((1/2)*(5 + sqrt(21)))^n. - Joe Keane (jgk(AT)jgk.org), May 16 2002
Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i); then a(n) = (-1)^n*q(n, -7). - Benoit Cloitre, Nov 10 2002
A054493(2*n) = a(n)^2 for all n in Z. - Michael Somos, Jan 22 2017
a(n) = -a(-1-n) for all n in Z. - Michael Somos, Jan 22 2017
0 = -7 + a(n)*(+a(n) - 5*a(n+1)) + a(n+1)*(+a(n+1)) for all n in Z. - Michael Somos, Jan 22 2017
a(n) = S(n, 5) + S(n-1, 5) = S(2*n, sqrt(7)) (see above in terms of U), for n >= 0 with S(-1, 5) = 0, where the coefficients of the Chebyshev S polynomials are given in A049310. - Wolfdieter Lang, Oct 26 2020
From Peter Bala, May 16 2025: (Start)
Sum_{n >= 1} (-1)^(n+1)/(a(n) - 1/a(n)) = 1/7 (telescoping series: 7/(a(n) - 1/a(n)) = 1/A004254(n+1) + 1/A004254(n)).
Product_{n >= 1} (a(n) + 1)/(a(n) - 1) = sqrt(7/3) (telescoping product: Product_{k = 1..n} ((a(k) + 1)/(a(k) - 1))^2 = 7/3 * (1 - 8/A231087(n+1))). (End)

A049685 a(n) = L(4*n+2)/3, where L=A000032 (the Lucas sequence).

Original entry on oeis.org

1, 6, 41, 281, 1926, 13201, 90481, 620166, 4250681, 29134601, 199691526, 1368706081, 9381251041, 64300051206, 440719107401, 3020733700601, 20704416796806, 141910183877041, 972666870342481, 6666757908520326, 45694638489299801, 313195711516578281

Offset: 0

Clark Kimberling

In general, Sum_{k=0..n} binomial(2*n-k,k)j^(n-k) = (-1)^n*U(2n, I*sqrt(j)/2), i=sqrt(-1). - Paul Barry, Mar 13 2005
a(n) = L(n,7), where L is defined as in A108299; see also A033890 for L(n,-7). - Reinhard Zumkeller, Jun 01 2005
Take 7 numbers consisting of 5 ones together with any two successive terms from this sequence. This set has the property that the sum of their squares is 7 times their product. (R. K. Guy, Oct 12 2005.) See also A111216.
Number of 01-avoiding words of length n on alphabet {0,1,2,3,4,5,6} which do not end in 0. - Tanya Khovanova, Jan 10 2007
For positive n, a(n) equals the permanent of the (2n) X (2n) tridiagonal matrix with sqrt(5)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
From Wolfdieter Lang, Feb 09 2021: (Start)
All positive solutions of the Diophantine equation x^2 + y^2 - 7*x*y = -5 are given by [x(n) = S(n, 7) - S(n-1, 7), y(n) = x(n-1)], for all integer numbers n, with the Chebyshev S-polynomials (A049310), with S(-1, 0) = 0, and S(-n, x) = -S(n-2, x), for n >= 2. x(n) = a(n), for n >= 0.
This indefinite binary quadratic form has discriminant D = +45. There is only this family representing -5 properly with x and y positive, and there are no improper solutions.
All proper and improper solutions of the generalized Pell equation X^2 - 45*Y^2 = +4 are given, up to a combined sign change in X and Y, in terms of x(n) = a(n) from the preceding comment, by X(n) = x(n) + x(n-1) = S(n-1, 7) - S(n-2, 7) and Y(n) = (x(n) - x(n-1))/3 = S(n-1, 7), for all integer numbers n. For positive integers X(n) = A056854(n) and Y(n) = A004187(n). X(-n) = X(n) and Y(-n) = - Y(n), for n >= 1.
The two conjugated proper family 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 numbers n.
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)

			a(3) = L(4*3 + 2)/3 = 843/3 = 281. - _Indranil Ghosh_, Feb 06 2017

Indranil Ghosh, Table of n, a(n) for n = 0..1193
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.
Tanya Khovanova, Recursive Sequences
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 [math.CO], 2014.
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.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory, Vol. 7, No. 5 (2011), pp. 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012), The John Selfridge Memorial Volume.
Index entries for linear recurrences with constant coefficients, signature (7,-1).

Row 7 of array A094954. First differences of A004187.
Cf. A002310, A002320, A049310, A049685, A056854.
Cf. similar sequences listed in A238379.

[Lucas(4*n+2)/3: n in [0..30]]; // G. C. Greubel, Dec 17 2017

Table[LucasL[4*n+2]/3, {n,0,50}] (* or *) LinearRecurrence[{7,-1}, {1,6}, 50] (* G. C. Greubel, Dec 17 2017 *)

a(n)=(fibonacci(4*n+1)+fibonacci(4*n+3))/3 \\ Charles R Greathouse IV, Jun 16 2014

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

Let q(n, x) = Sum_{i=0, n} x^(n-i)*binomial(2*n-i, i); then q(n, 5)=a(n); a(n) = 7a(n-1) - a(n-2). - Benoit Cloitre, Nov 10 2002
From Ralf Stephan, May 29 2004: (Start)
a(n+2) = 7a(n+1) - a(n).
G.f.: (1-x)/(1-7x+x^2).
a(n)*a(n+3) = 35 + a(n+1)*a(n+2). (End)
a(n) = Sum_{k=0..n} binomial(n+k, 2k)*5^k. - Paul Barry, Aug 30 2004
If another "1" is inserted at the beginning of the sequence, then A002310, A002320 and A049685 begin with 1, 2; 1, 3; and 1, 1; respectively and satisfy a(n+1) = (a(n)^2+5)/a(n-1). - Graeme McRae, Jan 30 2005
a(n) = (-1)^n*U(2n, i*sqrt(5)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - Paul Barry, Mar 13 2005
[a(n), A004187(n+1)] = [1,5; 1,6]^(n+1) * [1,0]. - Gary W. Adamson, Mar 21 2008
a(n) = S(n, 7) - S(n-1, 7) with Chebyshev S polynomials S(n-1, 7) = A004187(n), for n >= 0. - Wolfdieter Lang, Feb 09 2021
E.g.f.: exp(7*x/2)*(3*cosh(3*sqrt(5)*x/2) + sqrt(5)*sinh(3*sqrt(5)*x/2))/3. - Stefano Spezia, Apr 14 2025
From Peter Bala, May 04 2025: (Start)
a(n) = sqrt(2/9) * sqrt(1 - T(2*n+1, -7/2)), where T(k, x) denotes the k-th Chebyshev polynomial of the first kind.
a(n) divides a(3*n+1); a(n) divides a(5*n+2); in general, for k >= 0, a(n) divides a((2*k+1)*n + k).
The aerated sequence [b(n)]n>=1 = [1, 0, 6, 0, 41, 0, 281, 0, ...] is a fourth-order linear divisibility sequence; that is, if n | m then b(n) | b(m). It is the case P1 = 0, P2 = -9, Q = 1 of the 3-parameter family of divisibility sequences found by Williams and Guy.
Sum_{n >= 1} 1/(a(n) - 1/a(n)) = 1/5 (telescoping series: for n >= 1, 1/(a(n) - 1/a(n)) = 1/A290903(n-1) - 1/A290903(n).) (End)

A079935 a(n) = 4*a(n-1) - a(n-2) with a(1) = 1, a(2) = 3.

Original entry on oeis.org

1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, 413403, 1542841, 5757961, 21489003, 80198051, 299303201, 1117014753, 4168755811, 15558008491, 58063278153, 216695104121, 808717138331, 3018173449203, 11263976658481, 42037733184721, 156886956080403

Offset: 1

Benoit Cloitre and Paul D. Hanna, Jan 20 2003

See A001835 for another version.
Greedy frac multiples of sqrt(3): a(1)=1, Sum_{n>0} frac(a(n)*x) < 1 at x=sqrt(3).
The n-th greedy frac multiple of x is the smallest integer that does not cause Sum_{k=1..n} frac(a(k)*x) to exceed unity; an infinite number of terms appear as the denominators of the convergents to the continued fraction of x.
Binomial transform of A002605. - Paul Barry, Sep 17 2003
In general, Sum_{k=0..n} binomial(2n-k,k)*j^(n-k) = (-1)^n* U(2n, i*sqrt(j)/2), i=sqrt(-1). - Paul Barry, Mar 13 2005
The Hankel transform of this sequence is [1,2,0,0,0,0,0,0,0,0,0,...]. - Philippe Deléham, Nov 21 2007
From Richard Choulet, May 09 2010: (Start)
This sequence is a particular case of the following situation:
a(0)=1, a(1)=a, a(2)=b with the recurrence relation a(n+3) = (a(n+2)*a(n+1)+q)/a(n)
where q is given in Z to have Q = (a*b^2 + q*b + a + q)/(a*b) itself in Z.
The g.f is f: f(z) = (1 + a*z + (b-Q)*z^2 + (a*b + q - a*Q)*z^3)/(1 - Q*z^2 + z^4);
so we have the linear recurrence: a(n+4) = Q*a(n+2) - a(n).
The general form of a(n) is given by:
a(2*m) = Sum_{p=0..floor(m/2)} (-1)^p*binomial(m-p,p)*Q^(m-2*p) + (b-Q)*Sum_{p=0..floor((m-1)/2)} (-1)^p*binomial(m-1-p,p)*Q^(m-1-2*p) and
a(2*m+1) = a*Sum_{p=0..floor(m/2)} (-1)^p*binomial(m-p,p)*Q^(m-2*p) + (a*b+q-a*Q)*Sum_{p=0..floor((m-1)/2)} (-1)^p*binomial(m-1-p,p)*Q^(m-1-2*p).
(End)
x-values in the solution to 3*x^2 - 2 = y^2. - Sture Sjöstedt, Nov 25 2011
From Wolfdieter Lang, Oct 12 2020: (Start)
[X(n) = S(n, 4) - S(n-1, 4), Y(n) = X(n-1)] gives all positive solutions of X^2 + Y^2 - 4*X*Y = -2, for n = -oo..+oo, where the Chebyshev S-polynomials are given in 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 = +12. There is only this family representing -2 properly with X and Y positive, and there are no improper solutions.
See also the preceding comment by Sture Sjöstedt.
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)
a(n) is also the output of Tesler's formula for the number of perfect matchings of an m x n Mobius band where m and n are both even, specialized to m=2. (The twist is on the length-n side.) - Sarah-Marie Belcastro, Feb 15 2022

			a(4) = 41 since frac(1*x) + frac(3*x) + frac(11*x) + frac(41*x) < 1, while frac(1*x) + frac(3*x) + frac(11*x) + frac(k*x) > 1 for all k > 11 and k < 41.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Dalen Dockery, Marie Jameson, and Samuel Wilson, d-Fold Partition Diamonds, arXiv:2307.02579 [math.NT], 2023.
Tanya Khovanova, Recursive Sequences
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), pp. 609-640.
G. Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory B, 78(2000), 198-231.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory, Vol. 7, No. 5 (2011), pp. 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences, Integers, Volume 12A (2012), The John Selfridge Memorial Volume.
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Cf. A002530 (denominators of convergents to sqrt(3)), A079934, A079936, A001353.
Cf. A001835 (same except for the first term).
Row 4 of array A094954.
Cf. similar sequences listed in A238379.

a079935 n = a079935_list !! (n-1)
a079935_list =
   1 : 3 : zipWith (-) (map (4 *) $ tail a079935_list) a079935_list
-- Reinhard Zumkeller, Aug 14 2011

I:=[1,3]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jun 06 2015

f:= gfun:-rectoproc({a(n) = 4*a(n-1) - a(n-2),a(1)=1,a(2)=3}, a(n), remember):
seq(f(n),n=1..30); # Robert Israel, Jun 05 2015

a[n_] := (MatrixPower[{{1, 2}, {1, 3}}, n].{{1}, {1}})[[1, 1]]; Table[ a[n], {n, 0, 23}] (* Robert G. Wilson v, Jan 13 2005 *)
LinearRecurrence[{4,-1},{1,3},30] (* or *) CoefficientList[Series[ (1-x)/(1-4x+x^2),{x,0,30}],x]  (* Harvey P. Dale, Apr 26 2011 *)
a[n_] := Sqrt[2/3] Cosh[(-1 - 2 n) ArcCsch[Sqrt[2]]];
Table[Simplify[a[n-1]], {n, 1, 12}] (* Peter Luschny, Oct 13 2020 *)

a(n)=([0,1; -1,4]^(n-1)*[1;3])[1,1] \\ Charles R Greathouse IV, Mar 18 2017

my(x='x+O('x^30)); Vec((1-x)/(1-4*x+x^2)) \\ G. C. Greubel, Feb 25 2019

[lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in range(1, 25)] # Zerinvary Lajos, Apr 29 2009

For n > 0, a(n) = ceiling( (2+sqrt(3))^n/(3+sqrt(3)) ).
From Paul Barry, Sep 17 2003: (Start)
G.f.: (1-x)/(1-4*x+x^2).
E.g.f.: exp(2*x)*(sinh(sqrt(3)*x)/sqrt(3) + cosh(sqrt(3)*x)).
a(n) = ( (3+sqrt(3))*(2+sqrt(3))^n + (3-sqrt(3))*(2-sqrt(3))^n )/6 (offset 0). (End)
a(n) = Sum_{k=0..n} binomial(2*n-k, k)*2^(n-k). - Paul Barry, Jan 22 2005 [offset 0]
a(n) = (-1)^n*U(2*n, i*sqrt(2)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - Paul Barry, Mar 13 2005 [offset 0]
a(n) = Jacobi_P(n,-1/2,1/2,2)/Jacobi_P(n,-1/2,1/2,1). - Paul Barry, Feb 03 2006 [offset 0]
a(n) = sqrt(2+(2-sqrt(3))^(2*n-1) + (2+sqrt(3))^(2*n-1))/sqrt(6). - Gerry Martens, Jun 05 2015
a(n) = (1/2 + sqrt(3)/6)*(2-sqrt(3))^n + (1/2 - sqrt(3)/6)*(2+sqrt(3))^n. - Robert Israel, Jun 05 2015
a(n) = S(n-1,4) - S(n-2,4) = (-1)^(n-1)*S(2*(n-1), i*sqrt(2)), with Chebyshev S-polynomials (A049310), the imaginary unit i, S(-1, x) = 0, for n >= 1. See also the formula above by Paul Barry (with offset 0). - Wolfdieter Lang, Oct 12 2020
a(n) = sqrt(2/3)*cosh((-1 - 2*n) arccsch(sqrt(2))), where arccsch is the inverse hyperbolic cosecant function (with offset 0). - Peter Luschny, Oct 13 2020
From Peter Bala, May 04 2025: (Start)
a(n) = (1/sqrt(3)) * sqrt(1 - T(2*n-1, -2)), where T(k, x) denotes the k-th Chebyshev polynomial of the first kind.
a(n) divides a(3*n-1); a(n) divides a(5*n-2); in general, for k >= 0, a(n) divides a((2*k+1)*n - k).
The aerated sequence [b(n)]n>=1 = [1, 0, 3, 0, 11, 0, 41, 0, ...] is a fourth-order linear divisibility sequence; that is, if n | m then b(n) | b(m). It is the case P1 = 0, P2 = -6, Q = 1 of the 3-parameter family of divisibility sequences found by Williams and Guy.
Sum_{n >= 2} 1/(a(n) - 1/a(n)) = 1/2 (telescoping series: for n >= 1, 1/(a(n) - 1/a(n)) = 1/A052530(n-1) - 1/A052530(n).) (End)

A212336 Expansion of 1/(1 - 23x + 23x^2 - x^3).

Original entry on oeis.org

1, 23, 506, 11110, 243915, 5355021, 117566548, 2581109036, 56666832245, 1244089200355, 27313295575566, 599648413462098, 13164951800590591, 289029291199530905, 6345479454589089320, 139311518709760434136, 3058507932160140461673

Offset: 0

Bruno Berselli, Jun 08 2012

Partial sums of A077421.

Bruno Berselli, Table of n, a(n) for n = 0..200
Robert K. Moniot, A Family of Integer Sequences, 2021.
Index entries for linear recurrences with constant coefficients, signature (23,-23,1).

Sequences with g.f. of the type 1/(1-k*x+k*x^2-x^3): A334673 (k=24), A212336 (k=23), A212335 (k=22), A097833 (k=21), A097832 (k=20), A049664 (k=19), A097831-A097829 (k=18,17,16), A076139 (k=15), A097828-A097826 (k=14,13,12), A097784 (k=11), A092420 (k=10), A076765 (k=9), A092521 (k=8), A053142 (k=7), A089817(k=6), A061278 (k=5), A027941 (k=4), A000217 (k=3), A021823 (k=2), A133872 (k=1), A079978 (k=0).

m:=17; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1/(1-23*x+23*x^2-x^3)));

I:=[1,23,506]; [n le 3 select I[n] else 23*Self(n-1)-23*Self(n-2)+Self(n-3): n in [1..20]]; // Vincenzo Librandi, Aug 18 2013

a:= n-> (<<0|1|0>, <0|0|1>, <1|-23|23>>^n. <<1, 23, 506>>)[1, 1]:
seq(a(n), n=0..20);  # Alois P. Heinz, Jun 15 2012

CoefficientList[Series[1/(1 - 23 x + 23 x^2 - x^3), {x, 0, 16}], x]
LinearRecurrence[{23, -23, 1}, {1, 23, 506}, 20] (* Vincenzo Librandi, Aug 18 2013 *)

makelist(coeff(taylor(1/(1-23*x+23*x^2-x^3), x, 0, n), x, n), n, 0, 16);

PARI
```
Vec(1/(1-23*x+23*x^2-x^3)+O(x^17))
```

[(1/20)*(-1 +21*chebyshev_U(n, 11) -chebyshev_U(n-1, 11)) for n in (0..30)] # G. C. Greubel, Feb 07 2022

G.f.: 1/((1-x)*(1 - 22*x + x^2)).
a(n) = (((6+sqrt(30))^(2*n+3) + (6-sqrt(30))^(2*n+3))/6^(n+1) - 12)/240.
a(n) = a(-n-3) = 23*a(n-1) - 23*a(n-2) + a(n-3).
a(n)*a(n+2) = a(n+1)*(a(n+1)-1).
a(n+1) - 11*a(n) = A133285(n+2).
11*a(n+1) - a(n) = (1/5)*A157096(n+2).
a(n) = (1/20)*(-1 + 21*ChebyshevU(n, 11) - ChebyshevU(n-1, 11)). - G. C. Greubel, Feb 07 2022

A080097 a(n) = Fibonacci(n+2)^2 - 1.

Original entry on oeis.org

0, 3, 8, 24, 63, 168, 440, 1155, 3024, 7920, 20735, 54288, 142128, 372099, 974168, 2550408, 6677055, 17480760, 45765224, 119814915, 313679520, 821223648, 2149991423, 5628750624, 14736260448, 38580030723, 101003831720

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Jan 29 2003

a(n), a(n)+1 and a(n)+2 are consecutive members of A049997.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Sergio Falcon, On the Sequences of Products of Two k-Fibonacci Numbers, American Review of Mathematics and Statistics, March 2014, Vol. 2, No. 1, pp. 111-120.
Index entries for linear recurrences with constant coefficients, signature (3,0,-3,1).

Equals A007598(n+2) - 1.

Cf. A000032, A000045, A001622, A049997, A059840, A064831, A080144.

List([0..30], n-> Fibonacci(n+2)^2 -1); # G. C. Greubel, Jul 23 2019

[Fibonacci(n+2)^2 -1: n in [0..30]]; // G. C. Greubel, Jul 23 2019

CoefficientList[Series[(3x+2x^2-x^3)/((1-x^2)(1-2x-2x^2+x^3)), {x, 0, 30}], x]
Table[Fibonacci[n+2]^2-1,{n,0,30}] (* Vladimir Joseph Stephan Orlovsky, Apr 03 2011 *)
LinearRecurrence[{3,0,-3,1},{0,3,8,24},40] (* Harvey P. Dale, Nov 23 2024 *)

A080097(n):=fib(n+2)^2-1$ makelist(A080097(n),n,0,30); /* Martin Ettl, Nov 13 2012 */

a(n)=fibonacci(n+2)^2-1 \\ Charles R Greathouse IV, Feb 06 2013

[fibonacci(n+2)^2 -1 for n in (0..30)] # G. C. Greubel, Jul 23 2019

If n is odd, then a(n) = F(n+1)*F(n+3) = F(n)*F(n+4) - 2, else a(n) = F(n)*F(n+4) = F(n+1)*F(n+3) - 2, where F(n) = Fibonacci numbers (A000045).
a(n) = (Lucas(2*n+4) - 2*(-1)^n - 5)/5.
O.g.f.: x*(3-x)/((1-x^2)*(1-3*x+x^2)) (see a comment on A080144). - Wolfdieter Lang, Jul 30 2012
a(n) = Sum_{k=1..n} F(k+3)*F(k) = A027941(n) + 2*A001654(n), n>=0. - Wolfdieter Lang, Jul 27 2012
Sum_{n>=1} 1/a(n) = (43 - 15*sqrt(5))/18 = 29/9 - 5*phi/3, where phi is the golden ratio (A001622). - Amiram Eldar, Oct 20 2020
a(n) = 3*a(n-1) - 3*a(n-3) + a(n-4). - Joerg Arndt, Nov 13 2023

Edited by Ralf Stephan, May 15 2005

A053606 a(n) = (Fibonacci(6*n+3) - 2)/4.

Original entry on oeis.org

0, 8, 152, 2736, 49104, 881144, 15811496, 283725792, 5091252768, 91358824040, 1639367579960, 29417257615248, 527871269494512, 9472265593285976, 169972909409653064, 3050040103780469184, 54730748958638792256, 982103441151717791432

Offset: 0

N. J. A. Sloane, James Sellers, Jan 20 2000

Define a(1)=0, a(2)=8 with 5*(a(1)^2) + 5*a(1) + 1 = j(1)^2 = 1^2 and 5*(a(2)^2) + 5*a(2) + 1 = j(2)^2 = 19^2. Then a(n) = a(n-2) + 8*sqrt(5*(a(n-1)^2) + 5*a(n-1)+1). Another definition: a(n) such that 5*(a(n)^2) + 5*a(n) + 1 = j(n)^2. - Pierre CAMI, Mar 30 2005
It appears this sequence gives all nonnegative m such that 5*m^2 + 5*m + 1 is a square. - Gerald McGarvey, Apr 03 2005
sqrt(5*a(n)^2+5*a(n)+1) = A049629(n). - Gerald McGarvey, Apr 19 2005
a(n) is such that 5*a(n)^2 + 5*a(n) + 1 = j^2 = the square of A049629(n). Also A049629(n)/a(n) tends to sqrt(5) as n increases. - Pierre CAMI, Apr 21 2005
From Russell Jay Hendel, Apr 25 2015: (Start)
We prove the two McGarvey-CAMI conjectures mentioned at the beginning of the Comments section. Let, as usual, F(n) = A000045(n), the Fibonacci numbers. In the sequel we indicate equations with upper case letters ((A), (B), (C), (D)) for ease of reference.
Then we must prove (A), 5*((F(6*n+3)-2)/4)^2 + 5*((F(6*n+3)-2)/4) + 1 = ((F(6*n+5)-F(6*n+1))/4)^2. Let m = 3*n+1 so that 6*n+1, 6*n+3, and 6*n+5 are 2*m-1, 2*m+1, and 2*m+3 respectively. Define G(m) = F(6*n+3) = F(2*m+1) = A001519(m+1), the bisected Fibonacci numbers. We can now simplify equation (A) by i) multiplying the LHS and RHS by 16, ii) expanding squares, and iii) gathering like terms. This shows proof of (A) equivalent to proving (B), 5*G(m)^2-4 = (G(m+1)-G(m-1))^2.
By Jarden's theorem (D. Jarden, Recurring sequences, 2nd ed. Jerusalem, Riveon Lematematika, (1966)), if {H(n)}{n >=1} is any recursive sequence satisfying (C), H(n)=3H(n-1)-H(n-2), then {H(n)}^2{n >=1} is also a recursive sequence satisfying (D), H(n)^2=8H(n-1)^2-8H(n-2)^2+H(n-3)^2. As noted in the Formula section of A001519, {G(m)}_{m >= 1} satisfies (C).
Proof of (B) is now straightforward. Since {G(m)}{m >=1} satisfies (C), it follows that {G(m)^2}{m >=1} satisfies (D), and therefore, {5G(m)^2-4}_{m >=1} also satisfies (D).
Similarly, since {G(m)}{m >=1} satisfies (C), it follows that both {G(m+1)}{m >=1}, {G(m-1)}{m >=1} and their difference {G(m+1)-G(m-1)}{m >=1} satisfy (C), and therefore {G(m+1)-G(m-1)}^2_{m >=1} satisfies (D).
But then the LHS and RHS of (B) are equal for m=1,2,3 and satisfy the same recursion, (D). Hence the LHS and RHS of (B) are equal for all m. This completes the proof. (End)

G. C. Greubel, Table of n, a(n) for n = 0..790
F. Ellermann, Illustration of binomial transforms
Index entries for linear recurrences with constant coefficients, signature (19,-19,1).

Cf. A049629.

Related to sum of Fibonacci(kn) over n.. A000071, A027941, A099919, A058038, A138134.

List([0..30], n-> (Fibonacci(6*n+3)-2)/4); # G. C. Greubel, May 16 2019

[(Fibonacci(6*n+3)-2)/4: n in [0..30]]; // Vincenzo Librandi, Apr 20 2011

A053606 := proc(n) add(combinat[fibonacci](6*k),k=0..n) ;end proc:
seq(A053606(n),n=0..30) ;

Table[(Fibonacci[6n+3] -2)/4, {n,0,30}] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)

a(n)=fibonacci(6*n+3)\4 \\ Charles R Greathouse IV, Jul 02 2013

[(fibonacci(6*n+3)-2)/4 for n in (0..30)] # G. C. Greubel, May 16 2019

a(n) = 8*A049664(n).
a(n+1) = 9*a(n) + 2*sqrt(5*(2*a(n)+1)^2-1) + 4. - Richard Choulet, Aug 30 2007
G.f.: 8*x/((1-x)*(1-18*x+x^2)). - Richard Choulet, Oct 09 2007
a(n) = 18*a(n-1) - a(n-2) + 8, n > 1. - Gary Detlefs, Dec 07 2010
a(n) = Sum_{k=0..n} A134492(k). - Gary Detlefs, Dec 07 2010
a(n) = (Fibonacci(6*n+6) - Fibonacci(6*n) - 8)/16. - Gary Detlefs, Dec 08 2010

A059840 a(n) = F(n)F(n-1) if n odd otherwise F(n)F(n-1)-1, where F = Fibonacci numbers A000045.

Original entry on oeis.org

0, 0, 2, 5, 15, 39, 104, 272, 714, 1869, 4895, 12815, 33552, 87840, 229970, 602069, 1576239, 4126647, 10803704, 28284464, 74049690, 193864605, 507544127, 1328767775, 3478759200, 9107509824, 23843770274, 62423800997, 163427632719, 427859097159, 1120149658760, 2932589879120

Offset: 1

N. J. A. Sloane, Feb 26 2001

Harry J. Smith, Table of n, a(n) for n = 1..500
S. Falcon, On the Sequences of Products of Two k-Fibonacci Numbers, American Review of Mathematics and Statistics, March 2014, Vol. 2, No. 1, pp. 111-120.
H. Ohtsuka and S. Nakamura, On the sum of reciprocal sums of Fibonacci numbers, Fibonacci Quart. 46/47 (2008/2009), 153-159.
Index entries for linear recurrences with constant coefficients, signature (3,0,-3,1).

Cf. A000045, A001654, A059248, A064831, A119996.

List([1..30],n->Sum([1..n-2],k->Fibonacci(k)*Fibonacci(k+2))); # Muniru A Asiru, Aug 09 2018

F:=Fibonacci; [(n mod 2) eq 0 select F(n)*F(n-1)-1 else F(n)*F(n-1): n in [1..30]]; // G. C. Greubel, Jul 23 2019

seq(coeff(series(x^3*(2-x)/((1-x^2)*(1-3*x+x^2)), x,n+1),x,n),n=1..30); # Muniru A Asiru, Aug 09 2018

Table[If[OddQ[n],Fibonacci[n]Fibonacci[n-1],Fibonacci[n] Fibonacci[n-1]-1],{n,30}]  (* Harvey P. Dale, Apr 20 2011 *)

a(n) = { fibonacci(n)*fibonacci(n-1) - (n%2 == 0) } \\ Harry J. Smith, Jun 29 2009

a=(x^3*(2-x)/((1-x^2)*(1-3*x+x^2))).series(x, 30).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Jul 23 2019

G.f.: x^3*(2 - x)/((1 - x^2)*(1 - 3*x + x^2)). See a comment on A080144. - Wolfdieter Lang, Jul 30 2012
a(n) = Sum_{k=1..n-2} F(k)*F(k+2). - Alexander Adamchuk, May 17 2007
a(n+2) = (3*A001654(n) + A027941(n))/2, n >= 0. - Wolfdieter Lang, Jul 21 2012
a(n+2) = (3*(-1)^(n+1) - 5 + 2*Lucas(2*n + 3))/10, n >= 0. - Ehren Metcalfe, Aug 21 2017
a(n) = floor(1/(Sum_{k>=n} 1/Fibonacci(k)^2)) [Ohtsuka and Nakamura]. - Michel Marcus, Aug 09 2018
For n > 2, 2 * A000217(a(n)) = A228873(n-2). - Diego Rattaggi, Jan 27 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A004146 Alternate Lucas numbers - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A064831 Partial sums of A001654, or sum of the areas of the first n Fibonacci rectangles.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

A030221 Chebyshev even-indexed U-polynomials evaluated at sqrt(7)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A049685 a(n) = L(4*n+2)/3, where L=A000032 (the Lucas sequence).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A079935 a(n) = 4*a(n-1) - a(n-2) with a(1) = 1, a(2) = 3.

A212336 Expansion of 1/(1 - 23x + 23x^2 - x^3).

A059840 a(n) = F(n)F(n-1) if n odd otherwise F(n)F(n-1)-1, where F = Fibonacci numbers A000045.