login
a(n) = 2*a(n-1)^2 - 1, starting a(0) = 2.
(Formerly M1817 N0720)
18

%I M1817 N0720 #98 May 15 2023 02:17:05

%S 2,7,97,18817,708158977,1002978273411373057,

%T 2011930833870518011412817828051050497,

%U 8095731360557835890888779535060256832479295062749579257164654370487894017

%N a(n) = 2*a(n-1)^2 - 1, starting a(0) = 2.

%C An infinite coprime sequence defined by recursion. - _Michael Somos_, Mar 14 2004

%C 2^p-1 is prime iff it divides a(p-2), since a(n) = A003010(n)/2, where A003010 is the Lucas-Lehmer sequence used for Mersenne number primality testing. - _M. F. Hasler_, Mar 09 2007

%C From _Cino Hilliard_, Sep 28 2008: (Start)

%C Also numerators of the convergents to the square root of 3 using the following recursion for initial x = 1: x1=x, x=3/x, x=(x+x1)/2.

%C This recursion was derived by experimenting with polynomial recursions of the form x = -a(0)/(a(n-1)x^(n-1) + ... + a(1)) in an effort to find a root for the polynomial a(n)x^n + a(n-1)x^(n-1) + ... + a(0). The process was hit-and-miss until I introduced the averaging step described above. This method is equivalent to Newton's Method although derived somewhat differently. (End)

%C The sequence satisfies the Pell equation a(n)^2 - 3*A071579(n)^2 = 1. - _Vincenzo Librandi_, Dec 19 2011

%C From _Peter Bala_, Nov 2012: (Start)

%C The present sequence corresponds to the case x = 2 of the following general remarks. Let x > 1 and let alpha := {x + sqrt(x^2 - 1)}. Define a sequence a(n) (which depends on x) by setting a(n) = (1/2)*(alpha^(2^n) + (1/alpha)^(2^n)) for n >= 0. It is easy to verify that a(n) is a solution to the recurrence equation a(n+1) = 2*a(n)^2 - 1 with the initial condition a(0) = x.

%C The following algebraic identity is valid for x > 1:

%C sqrt(4*x^2 - 4)/(2*x + 1) = (1 - 1/(2*x))*sqrt(4*y^2 - 4)/(2*y + 1), where y = 2*x^2 - 1. Iterating the identity yields the product expansion sqrt(4*x^2 - 4)/(2*x + 1) = Product_{n >= 0} (1 - 1/(2*a(n))). A second expansion is Product_{n >= 0} (1 + 1/a(n)) = sqrt((x + 1)/(x - 1)). See Mendes-France and van der Poorten. (End)

%D L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, p. 399.

%D E. Lucas, Nouveaux théorèmes d'arithmétique supérieure, Comptes Rend., 83 (1876), 1286-1288.

%D W. Sierpiński, Sur les développements systématiques des nombres en produits infinis, in Œuvres choisies, tome 1, PWN Editions scientifiques de Pologne, 1974.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A002812/b002812.txt">Table of n, a(n) for n = 0..10</a>

%H Georg Cantor, <a href="https://gdz.sub.uni-goettingen.de/id/PPN599415665_0014?tify=%7B%22pages%22%3A%5B156%5D%2C%22pan%22%3A%7B%22x%22%3A0.5%2C%22y%22%3A0.831%7D%2C%22view%22%3A%22info%22%2C%22zoom%22%3A0.349%7D">Zwei Sätze über eine gewisse Zerlegung der Zahlen in unendliche Producte</a>, Zeitschrift für Mathematik und Physik. Band 14, 1869, S. 152-158. (See page 155, II, error in the fourth term.)

%H E. Lucas, <a href="/A001566/a001566.pdf">Nouveaux théorèmes d'arithmétique supérieure</a> (annotated scanned copy)

%H M. Mendes France and A. J. van der Poorten, <a href="http://dx.doi.org/10.1016/0304-3975(89)90045-5">From geometry to Euler identities</a>, Theoret. Comput. Sci., 65 (1989), 213-220.

%H Jeffrey Shallit, <a href="http://www.fq.math.ca/Scanned/31-1/shallit.pdf">Rational numbers with non-terminating, non-periodic modified Engel-type expansions</a>, Fib. Quart., 31 (1993), 37-40.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NewtonsIteration.html">Newton's Iteration</a>

%H <a href="/index/El#Engel">Index entries for sequences related to Engel expansions</a>

%F a(n) = A001075(2^n).

%F a(n) = ((2+sqrt(3))^(2^n) + (2-sqrt(3))^(2^n))/2. - _Bruno Berselli_, Dec 20 2011

%F From _Peter Bala_, Nov 11 2012: (Start)

%F 2*sqrt(3)/5 = Product_{n >= 0} (1 - 1/(2*a(n))).

%F sqrt(3) = Product_{n >= 0} (1 + 1/a(n)).

%F a(n) = (1/2)*A003010(n). (End)

%F a(n) = cos(2^n*arccos(2)). - _Peter Luschny_, Oct 12 2022

%F a(n) = A002531(2^(n+1)). - _Robert FERREOL_, Apr 13 2023

%e G.f. = 2 + 7*x + 97*x^2 + 18817*x^3 + 708158977*x^4 + ...

%p a:=n->((2+sqrt(3))^(2^n)+(2-sqrt(3))^(2^n))/2: seq(floor(a(n)),n=0..10); # _Muniru A Asiru_, Aug 12 2018

%t Table[((2 + Sqrt[3])^2^n + (2 - Sqrt[3])^2^n)/2, {n, 0, 7}] (* _Bruno Berselli_, Dec 20 2011 *)

%t NestList[2#^2-1&,2,10] (* _Harvey P. Dale_, May 04 2013 *)

%t a[ n_] := If[ n < 0, 0, ChebyshevT[2^n, 2]]; (* _Michael Somos_, Dec 06 2016 *)

%o (PARI) {a(n) = if( n<1, 2 * (n==0), 2 * a(n-1)^2 - 1)}; /* _Michael Somos_, Mar 14 2004 */

%o (PARI) /* Roots by recursion. Find first root of ax^2 + b^x + c */

%o rroot2(a,b,c,p) = { local(x=1,x1=1,j); for(j=1,p, x1=x; x=-c/(a*x+b); x=(x1+x)/2; /* Let x be the average of the last 2 values */ print1(numerator(x)","); ); } \\ _Cino Hilliard_, Sep 28 2008

%o (Magma) I:=[2]; [n le 1 select I[n] else 2*Self(n-1)^2-1: n in [1..8]]; // _Vincenzo Librandi_, Dec 19 2011

%o (GAP) a:=[2];; for n in [2..10] do a[n]:=2*a[n-1]^2-1; od; a; # _Muniru A Asiru_, Aug 12 2018

%Y Cf. A001075, A002531, A003010, A071579.

%Y Cf. A177879 (lpf).

%K nonn,easy,nice

%O 0,1

%A _N. J. A. Sloane_