A001077 Numerators of continued fraction convergents to sqrt(5).

1, 2, 9, 38, 161, 682, 2889, 12238, 51841, 219602, 930249, 3940598, 16692641, 70711162, 299537289, 1268860318, 5374978561, 22768774562, 96450076809, 408569081798, 1730726404001, 7331474697802, 31056625195209

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• frac
• nice

Comments

a(2*n+1) with b(2*n+1) := A001076(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 5*b^2 = -1.

a(2*n) with b(2*n) := A001076(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 5*b^2 = +1 (see Emerson reference).

Bisection: a(2*n) = T(n,9) = A023039(n), n >= 0 and a(2*n+1) = 2*S(2*n, 2*sqrt(5)) = A075796(n+1), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.

From Greg Dresden, May 21 2023: (Start)

For n >= 2, 8*a(n) is the number of ways to tile this T-shaped figure of length n-1 with four colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 8*a(6) = 23112 different tilings.

_

|| _

|||_|||

|_|

(End)

Examples

			1  2  9  38  161  (A001077)
-, -, -, --, ---, ...
0  1  4  17   72  (A001076)
1 + 2*x + 9*x^2 + 38*x^3 + 161*x^4 + 682*x^5 + 2889*x^6 + 12238*x^7 + ... - _Michael Somos_, Aug 11 2009
		

References

• 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).
• V. Thébault, Les Récréations Mathématiques, Gauthier-Villars, Paris, 1952, p. 282.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
• E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242, Ex. 1, pp. 237-238.
• Tanya Khovanova, Recursive Sequences
• 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
• Index entries for sequences related to Chebyshev polynomials.
• Index entries for linear recurrences with constant coefficients, signature (4,1).

Crossrefs

Cf. A000032, A001076, A023039, A049629, A052924, A078343, A164581, A179237, A180148, A329723, A374439.

Programs

Magma

I:=[1, 2]; [n le 2 select I[n] else 4*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Dec 19 2017

Maple

A001077:=(-1+2*z)/(-1+4*z+z**2); # conjectured by Simon Plouffe in his 1992 dissertation
with(combinat): a:=n->fibonacci(n+1, 4)-2*fibonacci(n, 4): seq(a(n), n=0..30); # Zerinvary Lajos, Apr 04 2008

Mathematica

LinearRecurrence[{4, 1}, {1, 2}, 30]
Join[{1},Numerator[Convergents[Sqrt[5],30]]] (* Harvey P. Dale, Mar 23 2016 *)
CoefficientList[Series[(1-2*x)/(1-4*x-x^2), {x, 0, 30}], x] (* G. C. Greubel, Dec 19 2017 *)
LucasL[3*Range[0,30]]/2 (* Rigoberto Florez, Apr 03 2019 *)
a[ n_] := LucasL[n, 4]/2; (* Michael Somos, Nov 02 2021 *)

PARI

{a(n) = fibonacci(3*n) / 2 + fibonacci(3*n - 1)}; /* Michael Somos, Aug 11 2009 */

PARI

a(n)=if(n<2,n+1,my(t=4);for(i=1,n-2,t=4+1/t);numerator(2+1/t)) \\ Charles R Greathouse IV, Dec 05 2011

PARI

x='x+O('x^30); Vec((1-2*x)/(1-4*x-x^2)) \\ G. C. Greubel, Dec 19 2017

Sage

[lucas_number2(n,4,-1)/2 for n in range(0, 30)] # Zerinvary Lajos, May 14 2009

Formula

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

a(n) = 4*a(n-1) + a(n-2), a(0)=1, a(1)=2.

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

a(n) = A014448(n)/2.

Limit_{n->infinity} a(n)/a(n-1) = phi^3 = 2 + sqrt(5). - Gregory V. Richardson, Oct 13 2002

a(n) = ((-i)^n)*T(n, 2*i), with T(n, x) Chebyshev's polynomials of the first kind A053120 and i^2 = -1.

Binomial transform of A084057. - Paul Barry, May 10 2003

E.g.f.: exp(2x)cosh(sqrt(5)x). - Paul Barry, May 10 2003

a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)*5^k*2^(n-2k). - Paul Barry, Nov 15 2003

a(n) = 4*a(n-1) + a(n-2) when n > 2; a(1) = 1, a(2) = 2. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 25 2004

a(n) = A001076(n+1) - 2*A001076(n) = A097924(n) - A015448(n+1); a(n+1) = A097924(n) + 2*A001076(n) = A097924(n) + 2(A048876(n) - A048875(n)). - Creighton Dement, Mar 19 2005

a(n) = F(3*n)/2 + F(3*n-1) where F() = Fibonacci numbers A000045. - Gerald McGarvey, Apr 28 2007

a(n) = A000032(3*n)/2.

For n >= 1: a(n) = (1/2)*Fibonacci(6*n)/Fibonacci(3*n) and a(n) = integer part of (2 + sqrt(5))^n. - Artur Jasinski, Nov 28 2011

a(n) = Sum_{k=0..n} A201730(n,k)*4^k. - Philippe Deléham, Dec 06 2011

a(n) = A001076(n) + A015448(n). - R. J. Mathar, Jul 06 2012

G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(5*k-4)/(x*(5*k+1) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 27 2013

a(n) is the (1,1)-entry of the matrix W^n with W=[2, sqrt(5); sqrt(5), 2]. - Carmine Suriano, Mar 21 2014

From Rigoberto Florez, Apr 03 2019: (Start)

a(n) = A099919(n) + A049651(n) if n > 0.

a(n) = 1 + Sum_{k=0..n-1} L(3*k + 1) if n >= 0, L(n) = n-th Lucas number (A000032). (End)

From Christopher Hohl, Aug 22 2021: (Start)

For n >= 2, a(2n-1) = A079962(6n-9) + A079962(6n-3).

For n >= 1, a(2n) = sqrt(20*A079962(6n-3)^2 + 1). (End)

a(n) = Sum_{k=0..n-2} A168561(n-2,k)*4^k + 2 * Sum_{k=0..n-1} A168561(n-1,k)*4^k, n>0. - R. J. Mathar, Feb 14 2024

a(n) = 4^n*Sum_{k=0..n} A374439(n, k)*(-1/4)^k. - Peter Luschny, Jul 26 2024

From Peter Bala, Jul 08 2025: (Start)

The following series telescope:

Sum_{n >= 1} 1/(a(n) + 5*(-1)^(n+1)/a(n)) = 3/8, since 1/(a(n) + 5*(-1)^(n+1)/a(n)) = b(n) - b(n+1), where b(n) = (1/4) * (a(n) + a(n-1)) / (a(n)*a(n-1)).

Sum_{n >= 1} (-1)^(n+1)/(a(n) + 5*(-1)^(n+1)/a(n)) = 1/8, since 1/(a(n) + 5*(-1)^(n+1)/a(n)) = c(n) + c(n+1), where c(n) = (1/4) * (a(n) - a(n-1)) / (a(n)*a(n-1)). (End)

Extensions

Chebyshev comments from Wolfdieter Lang, Jan 10 2003