login
a(n) = (1 + a(n-1)*a(n-2))/a(n-3), a(0) = a(1) = a(2) = 1.
(Formerly M0829)
32

%I M0829 #118 Jul 27 2023 12:37:47

%S 1,1,1,2,3,7,11,26,41,97,153,362,571,1351,2131,5042,7953,18817,29681,

%T 70226,110771,262087,413403,978122,1542841,3650401,5757961,13623482,

%U 21489003,50843527,80198051,189750626,299303201,708158977,1117014753

%N a(n) = (1 + a(n-1)*a(n-2))/a(n-3), a(0) = a(1) = a(2) = 1.

%C For n >= 4 we have the linear recurrence a(n) = 4*a(n-2) - a(n-4). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 04 2001

%C Integer solutions to the equation floor(sqrt(3)*x^2) = x*floor(sqrt(3)*x). - _Benoit Cloitre_, Mar 18 2004

%C For n > 2, a(n) is the smallest integer > a(n-1) such that sqrt(3)*a(n) is closer to and greater than an integer than sqrt(3)*a(n-1). I.e., a(n) is the smallest integer > a(n-1) such that frac(sqrt(3)*a(n)) < frac(sqrt(3)*a(n-1)). - _Benoit Cloitre_, Jan 20 2003

%C The lower principal and intermediate convergents to 3^(1/2), beginning with 1/1, 3/2, 5/3, 12/7, 19/11, form a strictly increasing sequence; essentially, numerators=A143643 and denominators=A005246. - _Clark Kimberling_, Aug 27 2008

%C 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). - _Richard Choulet_, Feb 24 2010

%C From _Tim Monahan_, Jul 07 2011: (Start)

%C In the closed-form formula,

%C sqrt(2+sqrt(3))^n = ((sqrt(6)+sqrt(2))/2)^n;

%C -sqrt(2+sqrt(3))^n = ((-sqrt(6)-sqrt(2))/2)^n;

%C sqrt(2-sqrt(3))^n = ((sqrt(6)-sqrt(2))/2)^n;

%C -sqrt(2-sqrt(3))^n = ((sqrt(2)-sqrt(6))/2)^n.

%C (End)

%C a(n) for n > 1 are the integer square roots of (floor(m^2/3)+1), where the values of m are given by A143643. Also see A082630. - _Richard R. Forberg_, Nov 14 2013

%C The a(n) = (1 + a(n-1)*a(n-2))/a(n-3) recursion has the Laurent property. If a(0), a(1), a(2) are variables, then a(n) is a Laurent polynomial (a rational function with a monomial denominator). - _Michael Somos_, Feb 27 2019

%D Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.

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

%H T. D. Noe, <a href="/A005246/b005246.txt">Table of n, a(n) for n = 0..500</a>

%H Reid Barton, <a href="https://faculty.uml.edu/jpropp/reach/Barton/b-interp.html">A combinatorial interpretation of the sequence 1, 1, 2, 6, 21, 77, ...</a>

%H Reid Barton, <a href="/A101879/a101879.pdf">A combinatorial interpretation of the sequence 1, 1, 2, 6, 21, 77, ...</a>, [Annotated scanned copy]

%H Peter Cameron's Blog, <a href="https://cameroncounts.wordpress.com/2011/06/23/the-ade-affair-3/">The ADE affair, 3</a>, Posted 23/06/2011.

%H T. Crilly, <a href="http://www.jstor.org/stable/3617570">Double sequences of positive integers</a>, Math. Gaz., 69 (1985), 263-271.

%H Enrica Duchi, Andrea Frosini, Renzo Pinzani and Simone Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Duchi/duchi4.html">A Note on Rational Succession Rules</a>, J. Integer Seqs., Vol. 6, 2003.

%H R. K. Guy, <a href="/A005246/a005246.pdf">Letter to N. J. A. Sloane, Feb 1986</a>

%H Clark Kimberling, <a href="http://dx.doi.org/10.1007/s000170050020">Best lower and upper approximates to irrational numbers</a>, Elemente der Mathematik, 52 (1997) 122-126.

%H Valentin Ovsienko, Serge Tabachnikov, <a href="https://arxiv.org/abs/1705.01623">Dual numbers, weighted quivers, and extended Somos and Gale-Robinson sequences</a>, arXiv:1705.01623 [math.CO], 2017. See p. 10.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,4,0,-1).

%F G.f.: (1 + x - 3*x^2 - 2*x^3)/(1 - 4*x^2 + x^4).

%F Limit_{n->oo} a(2n+1)/a(2n) = (3+sqrt(3))/3 = 1.5773502...; lim_{n->oo} a(2n)/a(2n-1) = (3+sqrt(3))/2 = 2.3660254.... - _Benoit Cloitre_, Aug 07 2002

%F A101265(n) = a(n)*a(n+1). - _Franklin T. Adams-Watters_, Apr 24 2006

%F a(n) = a(2-n) for all n in Z. - _Michael Somos_, Nov 15 2006

%F a(2*n + 1) = A001075(n). a(2*n) = A001835(n). a(2*n + 1) - a(2*n) = a(2*n + 2) - a(2*n + 1) = A001353(n). - _Michael Somos_, May 24 2012

%F For n > 2: a(n) = a(n-1) + Sum_{k=1..floor((n-1)/2)} a(2*k). - _Reinhard Zumkeller_, Dec 16 2007

%F From _Richard Choulet_, Feb 24 2010: (Start)

%F a(2*m) = Sum_{p=0..floor(m/2)} (-1)^p*binomial(m-p,p)*4^(m-2*p) - 3*Sum_{p=0..floor((m-1)/2)} (-1)^p*binomial(m-1-p,p)*4^(m-1-2*p).

%F a(2*m+1) = Sum_{p=0..floor(m/2)} (-1)^p*binomial(m-p,p)*4^(m-2*p) - 2*Sum_{p=0..floor((m-1)/2)} (-1)^p*binomial(m-1-p,p)*4^(m-1-2*p). (End)

%F From _Tim Monahan_, Jul 01 2011: (Start)

%F Closed form without extra leading 1: ((sqrt(6)+3)*(sqrt(2+sqrt(3))^n+(sqrt(2-sqrt(3))^n))+(3-sqrt(6))*(-sqrt(2+sqrt(3))^n+(-sqrt(2-sqrt(3))^n)))/12.

%F Closed form with extra leading 1: ((6+3*sqrt(6)-2*sqrt(3)-3*sqrt(2))*(sqrt(2+sqrt(3))^n)+(6+3*sqrt(6)+2*sqrt(3)+3*sqrt(2))*(sqrt(2-sqrt(3))^n)+(6-3*sqrt(6)-2*sqrt(3)+3*sqrt(2))*(-sqrt(2+sqrt(3))^n)+(6-3*sqrt(6)+2*sqrt(3)-3*sqrt(2))*(-sqrt(2-sqrt(3))^n))/24. (End)

%F a(2*n+2) = Sum_{k = 0..n} 2^k*binomial(n+k,2*k); a(2*n+1) = Sum_{k = 0..n} n/(n+k)*2^k*binomial(n+k,2*k) for n >= 1. Row sums of A211956. - _Peter Bala_, May 01 2012

%F a(n) = ((sqrt(2)+sqrt(3)+(-1)^n*(sqrt(2)-sqrt(3)))*sqrt(2+(2-sqrt(3))^n*(2+ sqrt(3))-(-2+sqrt(3))*(2+ sqrt(3))^n))/(4*sqrt(3)). - _Gerry Martens_, Jun 06 2015

%F 0 = a(n) - 2*a(n+1) + a(n+2) if n is even, 0 = a(n) - 3*a(n+1) + a(n+2) if n is odd for all n in Z. - _Michael Somos_, Feb 10 2017

%e G.f. = 1 + x + x^2 + 2*x^3 + 3*x^4 + 7*x^5 + 11*x^6 + 26*x^7 + 41*x^8 + ...

%e From _Richard Choulet_, Feb 24 2010: (Start)

%e a(4) = 4^2 - 4^0 - 3*4^1 = 3.

%e a(7) = 4^3 - 4*binomial(2,1) - 2*(4^2-1) = 26. (End)

%p A005246:=-(-1-z+2*z**2+z**3)/(1-4*z**2+z**4); # Conjectured by _Simon Plouffe_ in his 1992 dissertation. Gives sequence except for one of the leading 1's.

%p for q from 1 to 10 do :a:=1:b:=1:Q:=(a*b^2+q*b+a+q)/(a*b): for m from 0 to 15 do U(m):=sum((-1)^p*binomial(m-p,p)*Q^(m-2*p),p=0..floor(m/2))+(b-Q)*sum((-1)^p*binomial(m-1-p,p)*Q^(m-1-2*p),p=0..floor((m-1)/2)):od: for m from 0 to 15 do V(m):=a*sum((-1)^p*binomial(m-p,p)*Q^(m-2*p),p=0..floor(m/2))+(a*b+q-a*Q)*sum((-1)^p*binomial(m-1-p,p)*Q^(m-1-2*p),p=0..floor((m-1)/2)):od:for m from 0 to 15 do W(2*m):=U(m):od:for m from 0 to 14 do W(2*m+1):=V(m):od:seq(W(m),m=0..30):od; # _Richard Choulet_, Feb 24 2010

%t RecurrenceTable[{a[0]==a[1]==a[2]==1,a[n]==(1+a[n-1]a[n-2])/a[n-3]},a,{n,40}] (* _Harvey P. Dale_, May 28 2013 *)

%t a[n_] := Cosh[(n-1)*ArcSinh[1/Sqrt[2]]]*If[EvenQ[n], Sqrt[2/3], 1]; Table[a[n] // FunctionExpand, {n, 0, 34}] (* _Jean-François Alcover_, Dec 10 2014, after _Peter Bala_ *)

%t a[ n_] := With[{m = If[ n < 0, 2 - n, n]}, SeriesCoefficient[ (1 + x - 3 x^2 - 2 x^3) / (1 - 4 x^2 + x^4), {x, 0, m}]]; (* _Michael Somos_, Feb 10 2017 *)

%o (PARI) {a(n) = if( n<0, n = 2 - n); polcoeff((1 + x - 3*x^2 - 2*x^3) / (1 - 4*x^2 + x^4) + x * O(x^n), n)}; /* _Michael Somos_, Nov 15 2006 */

%o (PARI) {a(n) = real( (2 + quadgen(12))^(n\2) * if( n%2, 1, 1 - 1 / quadgen(12)) )}; /* _Michael Somos_, May 24 2012 */

%o (Haskell)

%o a005246 n = a005246_list !! n

%o a005246_list = 1 : 1 : 1 : map (+ 1) (zipWith div

%o (zipWith (*) (drop 2 a005246_list) (tail a005246_list)) a005246_list)

%o -- _Reinhard Zumkeller_, Mar 07 2012

%Y Bisections are A001835 and A001075.

%Y Cf. A101265. Row sums of A211956.

%Y Cf. A001353.

%K easy,nonn,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from _Michael Somos_, Aug 01 2001