login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001076 Denominators of continued fraction convergents to sqrt(5).
(Formerly M3538 N1434)
90
0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, 10182505537, 43133785636, 182717648081, 774004377960, 3278735159921, 13888945017644, 58834515230497, 249227005939632, 1055742538989025 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

Bisection: a(2*n+1) = T(2*n+1, sqrt(5))/sqrt(5) = A007805(n), n >= 0 and a(2*n) = 4*S(n-1,18), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. S(-1,x)=0. See A053120, resp. A049310. S(n,18)=A049660(n+1). - Wolfdieter Lang, Jan 10 2003

Apart from initial terms, this is the Pisot sequence E(4,17), a(n) = floor(a(n-1)^2/a(n-2) + 1/2).

This is also the Horadam sequence (0,1,1,4), having the recurrence relation a(n) = s*a(n-1) + r*a(n-2); for n > 1, where a(0) = 0, a(1) = 1, s = 4, r = 1. a(n) / a(n-1) converges to 5^1/2 + 2 as n approaches infinity. 5^(1/2) + 2 can also be written as (2 * Phi) + 1 and Phi^2 + Phi. - Ross La Haye, Aug 18 2003

Numerators in continued fraction [2, 4, 4, 4, ...] = (1, 4, 17, 72, ...) = numerators of continued fraction [4, 4, 4, ...], where the convergents to [4, 4, 4, ...] = (1/4, 4/17, 17/72, ...). Let X = the 2 X 2 matrix [0, 1; 1, 4]; then X^n = [a(n-1), a(n); a(n), a(n+1)]; e.g., X^3 = [4, 17; 17, 72]. Let C = the limit of a(n)/a(n-1) = 2 + sqrt(5) = 4.236067977...; then C^n = a(n+1) + (1/C)*a(n), where (1/C) = 0.236067977... . Example: C^3 = 76.01315556..., = 72 + 17*(0.2360679...). - Gary W. Adamson, Dec 15 2007

Sqrt(5) = 4/2 + 4/17 + 4/(17*305) + 4/(305*5473) + 4/(5473*98209) + ... . - Gary W. Adamson, Dec 15 2007

a(p) == 20^((p-1)/2)) mod p, for odd primes p. - Gary W. Adamson, Feb 22 2009

A001076 == One half of even Fibonacci numbers. - Vladimir Joseph Stephan Orlovsky, Oct 25 2009

a(n) = A167808(3*n). - Reinhard Zumkeller, Nov 12 2009

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

Moreover, a(n) is the second binomial transform of (0,1,0,5,0,25,...) (see also A033887). This fact can be proved similarly like the proof of Paul Barry's remark in A033887 by using the following scaling identity for delta-Fibonacci numbers: y^n b(n;x/y) = Sum_{k=0..n} binomial(n,k) (y-1)^(n-k) b(k;x) and the fact that b(n;2) = (1-(-1)^n) 5^floor(n/2). - Roman Witula, Jul 12 2012

Binomial transform of 0, 1, 2, 8, 24, 80, 256, ... (A063727 with offset 1). - R. J. Mathar, Feb 05 2014

For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,...,4} avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015

With offset 1 is the INVERT transform of A006190: (1, 3, 10, 33, 109, 360, ...). - Gary W. Adamson, Jul 24 2015

a(n) = A000045(3*n)/2 = (A000045(n)*A047946(n))/2, so a(n) is either divisible by A000045(n)/2 or by A047946(n)/2. When n > 3, A000045(n) > 2 and A047946(n) > 2. Therefore a(3) = 17 is the only prime number in this sequence. - Bobby Jacobs, Sep 17 2017

REFERENCES

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 23.

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

T. D. Noe, Table of n, a(n) for n = 0..200

Paraskevas K. Alvanos, Konstantinos A. Draziotis, Integer Solutions of the Equation y^2 = Ax^4 + B, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.4.

D. W. Boyd, Some integer sequences related to the Pisot sequences, Acta Arithmetica, 34 (1979), 295-305.

D. W. Boyd, Linear recurrence relations for some generalized Pisot sequences, Advances in Number Theory ( Kingston ON, 1991) 333-340, Oxford Sci. Publ., Oxford Univ. Press, New York, 1993

Latham Boyle, Paul J Steinhardt, Self-Similar One-Dimensional Quasilattices, arXiv preprint arXiv:1608.08220, 2016

E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242, Thm. 1, p. 233.

M. C. Firengiz, A. Dil, Generalized Euler-Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 398

M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

Tanya Khovanova, Recursive Sequences

C. Pita, On s-Fibonomials, J. Int. Seq. 14 (2011) # 11.3.7

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Index entries for sequences related to Chebyshev polynomials.

Index entries for linear recurrences with constant coefficients, signature (4,1).

FORMULA

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

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

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

a(n) = A014445(n)/2 = F(3n)/2.

a(n) = ((-i)^(n-1))*S(n-1, 4*i), with i^2 =-1 and S(n, x) := U(n, x/2) Chebyshev's polynomials of the second kind. See A049310. S(-1, x)=0.

a(n) = Sum_{i=0..n} Sum_{j=0..n} Fibonacci(i+j)*n!/(i!j!(n-i-j)!)/2. - Paul Barry, Feb 06 2004

E.g.f.: exp(2*x)*sinh(sqrt(5)*x)/sqrt(5). - Vladeta Jovovic, Sep 01 2004

a(n) = F(1) + F(4) + F(7) + ... + F(3n-2), for n > 0.

Conjecture: 2a(n+1) = a(n+2) - A001077(n+1). - Creighton Dement, Nov 28 2004

a(n) = Sum_{k=0..n} Sum_{j=0..n} C(n, j)C(j, k)F(j)/2. - Paul Barry, Feb 14 2005

a(n) = A048876(n) - A048875(n). - Creighton Dement, Mar 19 2005

Let M = {{0, 1}, {1, 4}}, v[1] = {0, 1}, v[n] = M.v[n - 1]; then a(n) = v[n][[1]]. - Roger L. Bagula, May 29 2005

a(n) = F(n, 4), the n-th Fibonacci polynomial evaluated at x=4. - T. D. Noe, Jan 19 2006

[A015448(n), a(n)] = [1,4; 1,3]^n * [1,0]. - Gary W. Adamson, Mar 21 2008

a(n) = (Sum_{k=0..n} Fibonacci(3*k-2)) + 1. - Gary Detlefs Dec 26 2010

a(n) = (3*(-1)^n*F(n) + 5*F(n)^3)/2, n >= 0. See the general D. Jennings formula given in a comment on triangle A111125, where also the reference is given. Here the second (k=1) row [3,1] applies. - Wolfdieter Lang, Sep 01 2012

Sum_{k>=1} (-1)^(k-1)/(a(k)*a(k+1)) = (Sum_{k>=1} (-1)^(k-1)/(F_k*F_(k+1)))^3 = phi^(-3), where F_n is the n-th Fibonacci numbers (A000045) and phi is golden ratio (A001622). - Vladimir Shevelev, Feb 23 2013

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

a(-n) = -(-1)^n * a(n). - Michael Somos, Feb 23 2014

The o.g.f. A(x) = x/(1 - 4*x - x^2) satisfies A(x) + A(-x) + 8*A(x)*A(-x) = 0 or equivalently (1 + 8*A(x))*(1 + 8*A(-x)) = 1. The o.g.f. for A049660 equals -A(sqrt(x))*A(-sqrt(x)). - Peter Bala, Apr 02 2015

EXAMPLE

1 2 9 38 161 (A001077)

-,-,-,--,---, ...

0 1 4 17 72 (A001076)

G.f. = x + 4*x^2 + 17*x^3 + 72*x^4 + 305*x^5 + 1292*x^6 + 5473*x^7 + 23184*x^8 + ...

MAPLE

A001076:=-1/(-1+4*z+z**2); # conjectured by Simon Plouffe in his 1992 dissertation

K:=z/(1-4*z-z^2): Kser:=series(K, z=0, 30): seq(coeff(Kser, z, n), n= 0..21); # Zerinvary Lajos, Nov 08 2007

with(combinat): a:=n->fibonacci(n+2, 4)-4*fibonacci(n+1, 4): seq(a(n), n=0..25); # Zerinvary Lajos, Apr 04 2008

MATHEMATICA

CoefficientList[Series[-z/(z^2 + 4 z - 1), {z, 0, 200}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 23 2011 *)

Join[{0}, Denominator[Convergents[Sqrt[5], 30]]] (* Harvey P. Dale, Dec 10 2011 *)

a[ n_] := Fibonacci[ 3 n] / 2; (* Michael Somos, Feb 23 2014 *)

a[ n_] := ((2 + Sqrt[5])^n - (2 - Sqrt[5])^n) /(2 Sqrt[5]) // Simplify; (* Michael Somos, Feb 23 2014 *)

LinearRecurrence[{4, 1}, {0, 1}, 26] (* Jean-François Alcover, Sep 23 2017 *)

PROG

(MuPAD) numlib::fibonacci(3*n)/2 $ n = 0..30; // Zerinvary Lajos, May 09 2008

(Sage) [lucas_number1(n, 4, -1) for n in xrange(0, 23)] # Zerinvary Lajos, Apr 23 2009

(Sage) [fibonacci(3*n)/2 for n in xrange(0, 23)] # Zerinvary Lajos, May 15 2009

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

(PARI) {a(n) = imag( (2 + quadgen(20))^n )}; /* Michael Somos, Feb 23 2014 */

CROSSREFS

Cf. A000045, A001077, A015448, A175183 (Pisano periods).

Cf. A049660, A007805.

Partial sums of A033887. First differences of A049652. Bisection of A059973.

Third column of array A028412.

Sequence in context: A108929 A022031 A255117 * A122451 A257388 A113442

Adjacent sequences:  A001073 A001074 A001075 * A001077 A001078 A001079

KEYWORD

nonn,easy,cofr,nice,changed

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 18 16:24 EST 2017. Contains 296177 sequences.