cp's OEIS Frontend

A079935 a(n) = 4*a(n-1) - a(n-2) with a(1) = 1, a(2) = 3.

%I A079935 #133 Jun 03 2025 05:24:03
%S A079935 1,3,11,41,153,571,2131,7953,29681,110771,413403,1542841,5757961,
%T A079935 21489003,80198051,299303201,1117014753,4168755811,15558008491,
%U A079935 58063278153,216695104121,808717138331,3018173449203,11263976658481,42037733184721,156886956080403
%N A079935 a(n) = 4*a(n-1) - a(n-2) with a(1) = 1, a(2) = 3.
%C A079935 See A001835 for another version.
%C A079935 Greedy frac multiples of sqrt(3): a(1)=1, Sum_{n>0} frac(a(n)*x) < 1 at x=sqrt(3).
%C A079935 The n-th greedy frac multiple of x is the smallest integer that does not cause Sum_{k=1..n} frac(a(k)*x) to exceed unity; an infinite number of terms appear as the denominators of the convergents to the continued fraction of x.
%C A079935 Binomial transform of A002605. - _Paul Barry_, Sep 17 2003
%C A079935 In general, Sum_{k=0..n} binomial(2n-k,k)*j^(n-k) = (-1)^n* U(2n, i*sqrt(j)/2), i=sqrt(-1). - _Paul Barry_, Mar 13 2005
%C A079935 The Hankel transform of this sequence is [1,2,0,0,0,0,0,0,0,0,0,...]. - _Philippe Deléham_, Nov 21 2007
%C A079935 From _Richard Choulet_, May 09 2010: (Start)
%C A079935 This sequence is a particular case of the following situation:
%C A079935 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)
%C A079935 where q is given in Z to have Q = (a*b^2 + q*b + a + q)/(a*b) itself in Z.
%C A079935 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);
%C A079935 so we have the linear recurrence: a(n+4) = Q*a(n+2) - a(n).
%C A079935 The general form of a(n) is given by:
%C A079935 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
%C A079935 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).
%C A079935 (End)
%C A079935 x-values in the solution to 3*x^2 - 2 = y^2. - _Sture Sjöstedt_, Nov 25 2011
%C A079935 From _Wolfdieter Lang_, Oct 12 2020: (Start)
%C A079935 [X(n) = S(n, 4) - S(n-1, 4), Y(n) = X(n-1)] gives all positive solutions of X^2 + Y^2 - 4*X*Y = -2, for n = -oo..+oo, where the Chebyshev S-polynomials are given in A049310, with S(-1, 0) = 0, and S(-|n|, x) = - S(|n|-2, x), for |n| >= 2.
%C A079935 This binary indefinite quadratic form has discriminant D = +12. There is only this family representing -2 properly with X and Y positive, and there are no improper solutions.
%C A079935 See also the preceding comment by _Sture Sjöstedt_.
%C A079935 See the formula for a(n) = X(n-1), for n >= 1, in terms of S-polynomials below.
%C A079935 This comment is inspired by a paper by _Robert K. Moniot_ (private communication). See his Oct 04 2020 comment in A027941 related to the case of x^2 + y^2 - 3*x*y = -1 (special Markov solutions). (End)
%C A079935 a(n) is also the output of Tesler's formula for the number of perfect matchings of an m x n Mobius band where m and n are both even, specialized to m=2. (The twist is on the length-n side.) - _Sarah-Marie Belcastro_, Feb 15 2022
%H A079935 G. C. Greubel, <a href="/A079935/b079935.txt">Table of n, a(n) for n = 1..1000</a>
%H A079935 Dalen Dockery, Marie Jameson, and Samuel Wilson, <a href="https://arxiv.org/abs/2307.02579">d-Fold Partition Diamonds</a>, arXiv:2307.02579 [math.NT], 2023.
%H A079935 Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H A079935 Jaime Rangel-Mondragon, <a href="https://web.archive.org/web/20190411024906/http://www.mathematica-journal.com/issue/v9i3/polyominoes.html">Polyominoes and Related Families</a>, The Mathematica Journal, 9:3 (2005), pp. 609-640.
%H A079935 G. Tesler, <a href="https://doi.org/10.1006/jctb.1999.1941">Matchings in graphs on non-orientable surfaces</a>, Journal of Combinatorial Theory B, 78(2000), 198-231.
%H A079935 H. C. Williams and R. K. Guy, <a href="https://doi.org/10.1142/S1793042111004587">Some fourth-order linear divisibility sequences</a>, Intl. J. Number Theory, Vol. 7, No. 5 (2011), pp. 1255-1277.
%H A079935 H. C. Williams and R. K. Guy, <a href="https://www.emis.de/journals/INTEGERS/papers/a17self/a17self.Abstract.html">Some Monoapparitic Fourth Order Linear Divisibility Sequences</a>, Integers, Volume 12A (2012), The John Selfridge Memorial Volume.
%H A079935 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-1).
%F A079935 For n > 0, a(n) = ceiling( (2+sqrt(3))^n/(3+sqrt(3)) ).
%F A079935 From _Paul Barry_, Sep 17 2003: (Start)
%F A079935 G.f.: (1-x)/(1-4*x+x^2).
%F A079935 E.g.f.: exp(2*x)*(sinh(sqrt(3)*x)/sqrt(3) + cosh(sqrt(3)*x)).
%F A079935 a(n) = ( (3+sqrt(3))*(2+sqrt(3))^n + (3-sqrt(3))*(2-sqrt(3))^n )/6 (offset 0). (End)
%F A079935 a(n) = Sum_{k=0..n} binomial(2*n-k, k)*2^(n-k). - _Paul Barry_, Jan 22 2005 [offset 0]
%F A079935 a(n) = (-1)^n*U(2*n, i*sqrt(2)/2), U(n, x) Chebyshev polynomial of second kind, i=sqrt(-1). - _Paul Barry_, Mar 13 2005 [offset 0]
%F A079935 a(n) = Jacobi_P(n,-1/2,1/2,2)/Jacobi_P(n,-1/2,1/2,1). - _Paul Barry_, Feb 03 2006 [offset 0]
%F A079935 a(n) = sqrt(2+(2-sqrt(3))^(2*n-1) + (2+sqrt(3))^(2*n-1))/sqrt(6). - _Gerry Martens_, Jun 05 2015
%F A079935 a(n) = (1/2 + sqrt(3)/6)*(2-sqrt(3))^n + (1/2 - sqrt(3)/6)*(2+sqrt(3))^n. - _Robert Israel_, Jun 05 2015
%F A079935 a(n) = S(n-1,4) - S(n-2,4) = (-1)^(n-1)*S(2*(n-1), i*sqrt(2)), with Chebyshev S-polynomials (A049310), the imaginary unit i, S(-1, x) = 0, for n >= 1. See also the formula above by _Paul Barry_ (with offset 0). - _Wolfdieter Lang_, Oct 12 2020
%F A079935 a(n) = sqrt(2/3)*cosh((-1 - 2*n) arccsch(sqrt(2))), where arccsch is the inverse hyperbolic cosecant function (with offset 0). - _Peter Luschny_, Oct 13 2020
%F A079935 From _Peter Bala_, May 04 2025: (Start)
%F A079935 a(n) = (1/sqrt(3)) * sqrt(1 - T(2*n-1, -2)), where T(k, x) denotes the k-th Chebyshev polynomial of the first kind.
%F A079935 a(n) divides a(3*n-1); a(n) divides a(5*n-2); in general, for k >= 0, a(n) divides a((2*k+1)*n - k).
%F A079935 The aerated sequence [b(n)]n>=1 = [1, 0, 3, 0, 11, 0, 41, 0, ...] is a fourth-order linear divisibility sequence; that is, if n | m then b(n) | b(m). It is the case P1 = 0, P2 = -6, Q = 1 of the 3-parameter family of divisibility sequences found by Williams and Guy.
%F A079935 Sum_{n >= 2} 1/(a(n) - 1/a(n)) = 1/2 (telescoping series: for n >= 1, 1/(a(n) - 1/a(n)) = 1/A052530(n-1) - 1/A052530(n).) (End)
%e A079935 a(4) = 41 since frac(1*x) + frac(3*x) + frac(11*x) + frac(41*x) < 1, while frac(1*x) + frac(3*x) + frac(11*x) + frac(k*x) > 1 for all k > 11 and k < 41.
%p A079935 f:= gfun:-rectoproc({a(n) = 4*a(n-1) - a(n-2),a(1)=1,a(2)=3}, a(n), remember):
%p A079935 seq(f(n),n=1..30); # _Robert Israel_, Jun 05 2015
%t A079935 a[n_] := (MatrixPower[{{1, 2}, {1, 3}}, n].{{1}, {1}})[[1, 1]]; Table[ a[n], {n, 0, 23}] (* _Robert G. Wilson v_, Jan 13 2005 *)
%t A079935 LinearRecurrence[{4,-1},{1,3},30] (* or *) CoefficientList[Series[ (1-x)/(1-4x+x^2),{x,0,30}],x]  (* _Harvey P. Dale_, Apr 26 2011 *)
%t A079935 a[n_] := Sqrt[2/3] Cosh[(-1 - 2 n) ArcCsch[Sqrt[2]]];
%t A079935 Table[Simplify[a[n-1]], {n, 1, 12}] (* _Peter Luschny_, Oct 13 2020 *)
%o A079935 (Sage) [lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in range(1, 25)] # _Zerinvary Lajos_, Apr 29 2009
%o A079935 (Haskell)
%o A079935 a079935 n = a079935_list !! (n-1)
%o A079935 a079935_list =
%o A079935    1 : 3 : zipWith (-) (map (4 *) $ tail a079935_list) a079935_list
%o A079935 -- _Reinhard Zumkeller_, Aug 14 2011
%o A079935 (Magma) I:=[1,3]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Jun 06 2015
%o A079935 (PARI) a(n)=([0,1; -1,4]^(n-1)*[1;3])[1,1] \\ _Charles R Greathouse IV_, Mar 18 2017
%o A079935 (PARI) my(x='x+O('x^30)); Vec((1-x)/(1-4*x+x^2)) \\ _G. C. Greubel_, Feb 25 2019
%Y A079935 Cf. A002530 (denominators of convergents to sqrt(3)), A079934, A079936, A001353.
%Y A079935 Cf. A001835 (same except for the first term).
%Y A079935 Row 4 of array A094954.
%Y A079935 Cf. similar sequences listed in A238379.
%K A079935 nonn,easy
%O A079935 1,2
%A A079935 _Benoit Cloitre_ and _Paul D. Hanna_, Jan 20 2003