A024537 a(n) = floor( a(n-1)/(sqrt(2) - 1) ), with a(0) = 1.

1, 2, 4, 9, 21, 50, 120, 289, 697, 1682, 4060, 9801, 23661, 57122, 137904, 332929, 803761, 1940450, 4684660, 11309769, 27304197, 65918162, 159140520, 384199201, 927538921, 2239277042, 5406093004, 13051463049, 31509019101, 76069501250, 183648021600

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

a(n) = A048739(n-1)+1 = 1/2 * (P(n)+P(n-1)+1), with P(n) = Pell numbers (A000129).

Number of (3412,#)-avoiding involutions in S_{n+1}, where # can be one of 22 patterns, see Egge reference.

Number of (s(0), s(1), ..., s(n+1)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n+1, s(0) = 1, s(n+1) = 1. - Herbert Kociemba, Jun 02 2004

Define the sequence S(a_0,a_1) by a_{n+2} is the least integer such that a_{n+2}/a_{n+1} > a_{n+1}/a_n for n >= 0 . This is S(2,4). (For proof, see the Alekseyev link.) - R. K. Guy

This sequence occurs in the lower bound of the order of the set of equivalent resistances of n equal resistors combined in series and in parallel (A048211). - Sameen Ahmed Khan, Jun 28 2010

Partial sums of the Pell numbers prefaced with a 1: (1, 1, 2, 5, 12, 29, 70, ...). - Gary W. Adamson, Feb 15 2012

The number of ways to write an n-bit binary sequence and then give runs of ones weakly incrementing labels starting with 1, e.g., 0011010011022203003330044040055555. - Andrew Woods, Jan 03 2015

Sums of the positive coefficients in Chebyshev polynomials of the first kind, beginning with T_1. a(n+1)/a(n) approaches 1/(sqrt(2)-1). - Gregory Gerard Wojnar, Mar 19 2018

Links

• Clark Kimberling, Table of n, a(n) for n = 0..250
• Max Alekseyev, Notes on A024537
• Antoni Amengual, The intriguing properties of the equivalent resistances of n equal resistors combined in series and in parallel, American Journal of Physics, 68(2) (2000) 175-179. [From _Sameen Ahmed Khan_, Jun 28 2010]
• Michael D. Barrus, Weakly threshold graphs, arXiv preprint arXiv:1608.01358 [math.CO], 2016.
• 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
• E. S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, arXiv:math/0307050 [math.CO], 2003; section 8.
• S. Felsner, D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
• Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
• Sameen Ahmed Khan, The bounds of the set of equivalent resistances of n equal resistors combined in series and in parallel, arXiv:1004.3346 [physics.gen-ph], 2010. [_Sameen Ahmed Khan_, Jun 28 2010]
• J. V. Leyendekkers and A. G. Shannon, Pellian sequence relationships among pi, e, sqrt(2), Notes on Number Theory and Discrete Mathematics, Vol. 18, 2012, No. 2, 58-62. See {u_n}. - _N. J. A. Sloane_, Dec 23 2012
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-1).

Crossrefs

Cf. A048211, A153588, A174283-A174286, A176499-A176502. - Sameen Ahmed Khan, Jun 28 2010

Cf. A171842. - Andrew Woods, Jan 03 2015

Programs

Mathematica

NestList[Floor[#/(Sqrt[2]-1)]&,1,40] (* Harvey P. Dale, Apr 01 2012 *)
LinearRecurrence[{3, -1, -1}, {1, 2, 4}, 31] (* Jean-François Alcover, Jan 07 2019 *)

PARI

a=vector(99);a[1]=1; for(n=2,#a,a[n]=a[n-1]\(sqrt(2) - 1)); a \\ Charles R Greathouse IV, Jun 14 2011

PARI

x='x+O('x^99); Vec((1-x-x^2)/((1-x)*(1-2*x-x^2))) \\ Altug Alkan, Mar 19 2018

Formula

a(n) = 2*a(n-1) + a(n-2) - 1. - Christian G. Bower

a(n) = 3*a(n-1) - a(n-2) - a(n-3).

From Paul Barry, Dec 25 2003: (Start)

G.f.: (1 - x - x^2)/((1-x)*(1 - 2*x - x^2)) = (1 - x - x^2)/(1 - 3*x + x^2 + x^3).

E.g.f.: exp((1+sqrt(2))*x)*(1+sqrt(2))/4+exp((1-sqrt(2))*x)*(1-sqrt(2))/4+exp(x)/2. (End)

a(n) = (1/4)*(2 + (1-sqrt(2))^(n+1) + (1+sqrt(2))^(n+1)). - Herbert Kociemba, Jun 02 2004

Let M = a tridiagonal matrix with all 1's in the super and main diagonals and [1,1,0,0,0,...] in the subdiagonal, and let V = vector [1,0,0,0,...], and the rest zeros. The sequence is generated as the leftmost column from iterates of M*V. - Gary W. Adamson, Jun 07 2011

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

a(n) = A171842(n+1), n>=0. That sequence starts with an extra 1. - Andrew Woods, Jan 03 2015

a(n) = 1 + sum_{k=1..floor((n+1)/2)} C(n+1,2*k)*2^(k-1). - Andrew Woods, Jan 03 2015

Extensions

Edited by N. J. A. Sloane at the suggestion of Max Alekseyev, Aug 24 2007