A001090 a(n) = 8*a(n-1) - a(n-2); a(0) = 0, a(1) = 1.

0, 1, 8, 63, 496, 3905, 30744, 242047, 1905632, 15003009, 118118440, 929944511, 7321437648, 57641556673, 453811015736, 3572846569215, 28128961537984, 221458845734657, 1743541804339272, 13726875588979519, 108071462907496880, 850844827670995521, 6698687158460467288

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

This sequence gives the values of y in solutions of the Diophantine equation x^2 - 15*y^2 = 1; the corresponding values of x are in A001091. - Vincenzo Librandi, Nov 12 2010 [edited by Jon E. Schoenfield, May 02 2014]

For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 8'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

For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,...,7}. - Milan Janjic, Jan 25 2015

From Klaus Purath, Jul 25 2024: (Start)

For any three consecutive terms (x, y, z) y^2 - x*z = 1 always applies.

a(n) = (t(i+2n) - t(i))/(t(i+n+1) - t(i+n-1)) where (t) is any recurrence t(k) = 9t(k-1) - 9t(k-2) + t(k-3) or t(k) = 8t(k-1) - t(k-2) without regard to initial values.

In particular, if the recurrence (t) of the form (9,-9,1) has the initial values t(0) = 1, t(1) = 2, t(2) = 9, a(n) = t(n) - 1 applies. (End)

Examples

			G.f. = x + 8*x^2 + 63*x^3 + 496*x^4 + 3905*x^5 + 30744*x^6 + 242047*x^7 + ...
		

References

• Julio R. Bastida, Quadratic properties of a linearly recurrent sequence. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 163--166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009) - From N. J. A. Sloane, May 30 2012
• 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).

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..100 from T. D. Noe)
• 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.
• H. Brocard, Notes élémentaires sur le problème de Peel, Nouvelle Correspondance Mathématique, 4 (1878), 337-343.
• E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242.
• A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case a=0,b=1; p=8, q=-1.
• Milan 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
• Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419; Eq.(44), lhs, m=10.
• 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.
• Shobhna Singh and Felix Flicker, Exact Solution to the Quantum and Classical Dimer Models on the Spectre Aperiodic Monotiling, arXiv:2309.14447 [cond-mat.str-el], 2023.
• Index entries for sequences related to Chebyshev polynomials.
• Index entries for linear recurrences with constant coefficients, signature (8,-1).

Crossrefs

Cf. A001091, A001906, A004187, A004254, A049310, A070997.

Equals one-third A136325.

Chebyshev sequence U(n, m): A000027 (m=1), A001353 (m=2), A001109 (m=3), this sequence (m=4), A004189 (m=5), A004191 (m=6), A007655 (m=7), A077412 (m=8), A049660 (m=9), A075843 (m=10), A077421 (m=11), A077423 (m=12), A097309 (m=13), A097311 (m=14), A097313 (m=15), A029548 (m=16), A029547 (m=17), A144128 (m=18), A078987 (m=19), A097316 (m=33).

Cf. A323182.

Programs

GAP

m:=4;; a:=[0,1];; for n in [3..20] do a[n]:=2*m*a[n-1]-a[n-2]; od; a; # G. C. Greubel, Dec 23 2019

Magma

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

Maple

A001090:=1/(1-8*z+z**2); # Simon Plouffe in his 1992 dissertation
seq( simplify(ChebyshevU(n-1, 4)), n=0..20); # G. C. Greubel, Dec 23 2019

Mathematica

Table[GegenbauerC[n-1, 1, 4], {n,0,20}] (* Vladimir Joseph Stephan Orlovsky, Sep 11 2008 *)
LinearRecurrence[{8,-1},{0,1},30] (* Harvey P. Dale, Aug 29 2012 *)
a[n_]:= ChebyshevU[n-1, 4]; (* Michael Somos, May 28 2014 *)
CoefficientList[Series[x/(1-8*x+x^2), {x,0,20}], x] (* G. C. Greubel, Dec 20 2017 *)

PARI

{a(n) = subst(poltchebi(n+1) - 4 * poltchebi(n), x, 4) / 15}; /* Michael Somos, Apr 05 2008 */

PARI

{a(n) = polchebyshev(n-1, 2, 4)}; /* Michael Somos, May 28 2014 */

PARI

my(x='x+O('x^30)); concat([0], Vec(x/(1-8*x-x^2))) \\ G. C. Greubel, Dec 20 2017

SageMath

[lucas_number1(n,8,1) for n in range(22)] # Zerinvary Lajos, Jun 25 2008

SageMath

[chebyshev_U(n-1,4) for n in (0..20)] # G. C. Greubel, Dec 23 2019

Formula

15*a(n)^2 - A001091(n)^2 = -1.

a(n) = sqrt((A001091(n)^2 - 1)/15).

a(n) = S(2*n-1, sqrt(10))/sqrt(10) = S(n-1, 8); S(n, x) := U(n, x/2), Chebyshev polynomials of 2nd kind, A049310, with S(-1, x) := 0.

From Barry E. Williams, Aug 18 2000: (Start)

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

G.f.: x/(1-8*x+x^2). (End)

Limit_{n->infinity} a(n)/a(n-1) = 4 + sqrt(15). - Gregory V. Richardson, Oct 13 2002

[A070997(n-1), a(n)] = [1,6; 1,7]^n * [1,0]. - Gary W. Adamson, Mar 21 2008

a(-n) = -a(n). - Michael Somos, Apr 05 2008

a(n+1) = Sum_{k=0..n} A101950(n,k)*7^k. - Philippe Deléham, Feb 10 2012

From Peter Bala, Dec 23 2012: (Start)

Product_{n >= 1} (1 + 1/a(n)) = (1/3)*(3 + sqrt(15)).

Product_{n >= 2} (1 - 1/a(n)) = (1/8)*(3 + sqrt(15)).

(End)

a(n) = A136325(n)/3. - Greg Dresden, Sep 12 2019

E.g.f.: exp(4*x)*sinh(sqrt(15)*x)/sqrt(15). - Stefano Spezia, Dec 12 2022

a(n) = Sum_{k = 0..n-1} binomial(n+k, 2*k+1)*6^k = Sum_{k = 0..n-1} (-1)^(n+k+1)* binomial(n+k, 2*k+1)*10^k. - Peter Bala, Jul 17 2023

Extensions

More terms from Wolfdieter Lang, Aug 02 2000