login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000129 Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2).
(Formerly M1413 N0552)
506
0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, 80782, 195025, 470832, 1136689, 2744210, 6625109, 15994428, 38613965, 93222358, 225058681, 543339720, 1311738121, 3166815962, 7645370045, 18457556052, 44560482149, 107578520350, 259717522849 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Sometimes also called lambda numbers.

Also denominators of continued fraction convergents to sqrt(2): 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, 8119/5741, 19601/13860, 47321/33461, 114243/80782, ... = A001333/A000129.

Number of lattice paths from (0,0) to the line x=n-1 consisting of U=(1,1), D=(1,-1) and H=(2,0) steps (i.e., left factors of Grand Schroeder paths); for example, a(3)=5, counting the paths H, UD, UU, DU and DD. - Emeric Deutsch, Oct 27 2002

a(2*n) with b(2*n) := A001333(2*n), n>=1, give all (positive integer) solutions to Pell equation b^2 - 2*a^2 = +1 (see Emerson reference). a(2*n+1) with b(2*n+1) := A001333(2*n+1), n>=0, give all (positive integer) solutions to Pell equation b^2 - 2*a^2 = -1.

Bisection: a(2*n+1)= T(2*n+1,sqrt(2))/sqrt(2)= A001653(n), n>=0 and a(2*n)= 2*S(n-1,6)= 2*A001109(n),n>=0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first,resp. second kind. S(-1,x)=0. See A053120, resp. A049310. - Wolfdieter Lang, Jan 10 2003

Consider the mapping f(a/b) = (a + 2b)/(a + b). Taking a = b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the following sequence 1/1, 3/2, 7/5, 17/12, 41/29, ... converging to 2^(1/2). Sequence contains the denominators. - Amarnath Murthy, Mar 22 2003

This is also the Horadam sequence (0,1,1,2). a(n) / a(n-1) converges to 2^(1/2) + 1 as n approaches infinity. - Ross La Haye, Aug 18 2003

Number of 132-avoiding two-stack sortable permutations.

For n>0, the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,....,n, s(0) = 2, s(n) = 3. - Herbert Kociemba, Jun 02 2004

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

Counts walks of length n from a vertex of a triangle to another vertex to which a loop has been added. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004

Apart from initial terms, Pisot sequence P(2,5). See A008776 for definition of Pisot sequences. - David W. Wilson

Sums of antidiagonals of A038207 [Pascal's triangle squared]. - Ross La Haye, Oct 28 2004

The Pell primality test is "If N is an odd prime, then P(N)-kronecker(2,N) is divisible by N". "Most" composite numbers fail this test, so it makes a useful pseudoprimality test. The odd composite numbers which are Pell pseudoprimes (i.e., that pass the above test) are in A099011. - Jack Brennen, Nov 13 2004

a(n) = sum of n-th row of triangle in A008288 = A094706(n)+A000079(n). - Reinhard Zumkeller, Dec 03 2004

Pell trapezoids (cf. A084158); for n>0, A001109(n)= (a(n-1)+a(n+1))*a(n)/2; e.g., 1189=(12+70)*29/2. - Charlie Marion, Apr 01 2006

(0!a(1),1!a(2),2!a(3),3!a(4),...) and (1,-2,-2,0,0,0,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Oct 29 2007

Let C = (sqrt(2)+1) = 2.414213562..., then for n>1, C^n = a(n)*(1/C) + a(n+1). Example: C^3 = 14.0710678... = 5*(.414213562...) + 12. Let X = the 2 X 2 matrix [0, 1; 1, 2]; then X^n * [1, 0] = [a(n-1), a(n); a(n), a(n+1)]. a(n) = numerator of n-th convergent to (Sqrt(2)-1) = .41421356... = [2, 2, 2,...], the convergents being [1/2, 2/5, 5/12,...]. - Gary W. Adamson, Dec 21 2007

A = sqrt(2) = 2/2 + 2/5 + 2/(5*29) + 2/(29*169) + 2/(169*985) + ...; B = ((5/2) - sqrt(2)) = 2/2 + 2/(2*12) + 2/(12*70) + 2/(70*408) + 2/(408*2378) + ...; A+B = 5/2. C = 1/2 = 2/(1*5) + 2/(2*12) + 2/(5*29) + 2/(12*70) + 2/(29*169) + ... - Gary W. Adamson, Mar 16 2008

Prime Pell numbers with an odd index gives the RMS value (A141812) of prime RMS numbers (A140480). - Ctibor O. Zizka, Aug 13 2008

From Clark Kimberling, Aug 27 2008: (Start)

Related convergents (numerator/denominator):

lower principal convergents: A002315/A001653

upper principal convergents: A001541/A001542

intermediate convergents: A052542/A001333

lower intermediate convergents: A005319/A001541

upper intermediate convergents: A075870/A002315

principal and intermediate convergents: A143607/A002965

lower principal and intermediate convergents: A143608/A079496

upper principal and intermediate convergents: A143609/A084068. (End)

Equals row sums of triangle A143808 starting with offset 1. - Gary W. Adamson, Sep 01 2008

Binomial transform of the sequence:= 0,1,0,2,0,4,0,8,0,16,..., powers of 2 alternating with zeros. - Philippe Deléham, Oct 28 2008

a(n) is also the sum of the n-th row of the triangle formed by starting with the top two rows of Pascal's triangle and then each next row has a 1 at both ends and the interior values are the sum of the three numbers in the triangle above that position. - Patrick Costello (pat.costello(AT)eku.edu), Dec 07 2008

Starting with offset 1 = eigensequence of triangle A135387 (an infinite lower triangular matrix with (2,2,2,...) in the main diagonal and (1,1,1,...) in the subdiagonal. - Gary W. Adamson, Dec 29 2008

Starting with offset 1 = row sums of triangle A153345. - Gary W. Adamson, Dec 24 2008

From Charlie Marion, Jan 07 2009: (Start)

In general, denominators, a(k,n) and numerators, b(k,n), of continued fraction convergents to sqrt((k+1)/k) may be found as follows:

let a(k,0) = 1, a(k,1) = 2k; for n>0, a(k,2n) = 2*a(k,2n-1)+a(k,2n-2)

and a(k,2n+1)=(2k)*a(k,2n)+a(k,2n-1);

let b(k,0) = 1, b(k,1) = 2k+1; for n>0, b(k,2n) = 2*b(k,2n-1)+b(k,2n-2)

and b(k,2n+1)=(2k)*b(k,2n)+b(k,2n-1).

For example, the convergents to sqrt(2/1) start 1/1, 3/2, 7/5, 17/12, 41/29.

In general, if a(k,n) and b(k,n) are the denominators and numerators, respectively, of continued fraction convergents to sqrt((k+1)/k) as defined above, then

k*a(k,2n)^2-a(k,2n-1)*a(k,2n+1)=k=k*a(k,2n-2)*a(k,2n)-a(k,2n-1)^2 and

b(k,2n-1)*b(k,2n+1)-k*b(k,2n)^2=k+1=b(k,2n-1)^2-k*b(k,2n-2)*b(k,2n);

for example, if k=1 and n=3, then a(1,n)=a(n+1) and

1*a(1,6)^2-a(1,5)*a(1,7)=1*169^2-70*408=1;

1*a(1,4)*a(1,6)-a(1,5)^2=1*29*169-70^2=1;

b(1,5)*b(1,7)-1*b(1,6)^2=99*577-1*239^2=2;

b(1,5)^2-1*b(1,4)*b(1,6)=99^2-1*41*239=2.

Cf. A001333, A142238-A142239, A153313-153318.

(End)

Starting with offset 1 = row sums of triangle A155002, equivalent to the statement that the Fibonacci series convolved with the Pell series prefaced with a "1": (1, 1, 2, 5, 12, 29,...) = (1, 2, 5, 12, 29,...).  -Gary W. Adamson, Jan 18 2009

It appears that P(p) == 8^((p-1/2)) mod p, p = prime; analogous to [Schroeder, p.90]: Fp == 5^((p-1)/2)) mod p. Example: Given P(11) = 5741, == 8^5 mod 11. Given P(17) = 11336689, == 8^8 mod 17 since 17 divides (8^8 - P(l7)). - Gary W. Adamson, Feb 21 2009

Equals eigensequence of triangle A154325. - Gary W. Adamson, Feb 12 2009

Another combinatorial interpretation of a(n-1) arises from a simple tiling scenario. Namely, a(n-1) gives the number of ways of tiling a 1 X n rectangle with indistinguishable 1 X 2 rectangles and 1 X 1 squares that come in two varieties, say, A and B. For example, with C representing the 1 X 2 rectangle, we obtain a(4)=12 from AAA, AAB, ABA, BAA, ABB, BAB, BBA, BBB, AC, BC, CA and CB. - Martin Griffiths (griffm(AT)essex.ac.uk), Apr 25 2009

a(n+1)=2*a(n)+ a(n-1) a(1=1,a(2)=2 was used by Theon from Smyrna. - Sture Sjöstedt, May 29 2009

The n-th Pell number counts the perfect matchings of the edge-labeled graph C_2 x P_(n-1), or equivalently, the number of domino tilings of a 2 x (n-1) cylindrical grid. - Sarah-Marie Belcastro (smbelcas(AT)toroidalsnark.net), Jul 04 2009

Number of units of a(n) belongs to a periodic sequence: 0, 1, 2, 5, 2, 9, 0, 9, 8, 5, 8, 1. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 04 2009

As a fraction: 1/79 = 0.0126582278481... or 1/9799 = 0.000102051229...(1/119 and 1/10199 for sequence in reverse). - M. Dols (markdols99(AT)yahoo.com), May 18 2010

As n->infinity, (a(n)/a(n-1)) - (a(n-1)/a(n)) tends to 2.0. Example: a(7)/a(6) - a(6)/a(7) = 169/70 - 70/169 = 2.0000845... - Gary W. Adamson, Jul 16 2010

Numbers n such that 2*n^2+-1 is a square. - Vincenzo Librandi, Jul 18 2010

Starting (1, 2, 5,...) = INVERTi transform of A006190: (1, 3, 10, 33, 109,...). - Gary W. Adamson, Aug 06 2010

[u,v] = [a(n), a(n-1)] generates all Pythagorean triples [u^2-v^2, 2uv, u^2+v^2] whose legs differ by 1. - James R. Buddenhagen, Aug 14 2010

An elephant sequence, see A175654. For the corner squares six A[5] vectors, with decimal values between 21 and 336, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A078057. - Johannes W. Meijer, Aug 15 2010

Let the 2x2 square matrix A=[2, 1; 1, 0] then a(n) = the (1,1) element of A^(n-1). - Carmine Suriano, Jan 14 2011

Define a t-circle to be a first-quadrant circle tangent to the x- and y-axes. Such a circle has coordinates equal to its radius. Let C(0) be the t-circle with radius 1. Then for n > 0, define C(n) to be the next larger t-circle which is tangent to C(n - 1). C(n) has radius A001333(2n) + a(2n)*2^.5 and each of the coordinates of its point of intersection with C(n + 1) is a(2n + 1) + (A001333(2n + 1)*2^.5)/2. See similar Comments for A001109 and A001653, Sep 14 2005. - Charlie Marion, Jan 18 2012

A001333 and A000129 give the diagonal numbers described by Theon from Smyrna. - Sture Sjöstedt, Oct 20 2012

Pell numbers could be named also "silver Fibonacci numbers", since, for n>=1, F(n+1)=ceil(phi*F(n)), if n is even and F(n+1)=floor(phi*F(n)), if n is odd, where phi is golden ratio, while a(n+1)=ceil(delta*a(n)), if n is even and a(n+1)=floor(delta*a(n)), if n is odd, where delta=delta_S=1+sqrt(2) is silver ratio. - Vladimir Shevelev, Feb 22 2013

a(n) is the number of compositions (ordered partitions) of n-1 into two sorts of 1's and one sort of 2's.  Example: the a(3)=5 compositions of 3-1=2 are 1+1, 1+1', 1'+1, 1'+1', and 2. - Bob Selcoe, Jun 21 2013

Between every two consecutive squares of a 1xn array there is a flap that can be folded over one of the two squares. Two flaps can be lowered over the same square in 2 ways, depending on which one is on top. The n-th Pell number counts the ways n-1 flaps can be lowered. For example, a sideway representation for the case n = 3 squares and 2 flaps is \\., .//, \./, ./_., ._\., where . is an empty square. - Jean M. Morales, Sep 18 2013

Define a(-n) to be a(n) for n odd and -a(n) for n even.  Then a(n) = A005319(k)*(a(n-2k+1) - a(n-2k)) + a(n-4k) = A075870(k)*(a(n-2k+2) - a(n-2k+1)) -  a(n-4k+2)). - Charlie Marion, Nov 26 2013

An alternative formulation of the combinatorial tiling interpretation listed above: Except for n=0, a(n-1) is the number of ways of partial tiling a 1 X n board with 1 X 1 squares and 1 X 2 dominoes. - Matthew Lehman, Dec 25 2013

Define a(-n) to be a(n) for n odd and -a(n) for n even.  Then a(n) = A077444(k)*a(n-2k+1)  + a(n-4k+2).  This formula generalizes the formula used to define this sequence. - Charlie Marion, Jan 30 2014

a(n-1) is the top left entry of the n-th power of any of the 3 X 3 matrices [0, 1, 1; 1, 1, 1; 0, 1, 1], [0, 1, 1; 0, 1, 1; 1, 1, 1], [0, 1, 0; 1, 1, 1; 1, 1, 1] or [0, 0, 1; 1, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

a(n+1) counts closed walks on K2 containing two loops on the other vertex. Equivalently the (1,1) entry of A^(n+1) where the adjacency matrix of digraph is A=(0,1;1,2). - David Neil McGrath, Oct 28 2014

REFERENCES

M. Abrate, S. Barbero, U. Cerruti, N. Murru, Construction and composition of rooted trees via descent functions, Algebra, Volume 2013 (2013), Article ID 543913, 11 pages, http://dx.doi.org/10.1155/2013/543913

Ayoub B. Ayoub, "Fibonacci-like sequences and Pell equations", The College Mathematics Journal, Vol. 38 (2007), pp. 49-53.

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 76.

M. Barnabei, F. Bonetti and M. Silimbani, Two permutation classes related to the Bubble Sort operator, Electronic Journal of Combinatorics 19(3) (2012), #P25.

A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.

S.-M. Belcastro, Tilings of 2 x n Grids on Surfaces, preprint.

J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 53.

C. M. da Fonseca, Unifying some Pell and Fibonacci identities, Applied Mathematics and Computation, Volume 236, Jun 01 2014, Pages 41-42,

John Derbyshire, Prime Obsession, Joseph Henry Press, 2004, see p. 16.

E. Deutsch, A formula for the Pell numbers, Problem 10663, Amer. Math. Monthly 107 (No. 4, 2000), solutions pp. 370-371.

E. I. Emerson, Recurrent sequences in the equation DQ^2=R^2+N, Fib. Quart., 7 (1969), 231-242, Ex.1, p. 237-8.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.1.

Shaun Giberson and Thomas J. Osler, Extending Theon's Ladder to Any Square Root, Problem 3858, Elementa, No. 4 1996 [Sture Sjöstedt, May 29 2009]

Martin Griffiths, Pell identities via a quadratic field, International Journal of Mathematical Education in Science and Technology, 2013, DOI:10.1080/0020739X.2013.790512.

R. P. Grimaldi, Ternary strings ..., Congressus Numerantium, 205 (2011), 129-149.

A. F. Horadam, Special Properties of the Sequence W(n){a, b; p, q}, Fibonacci Quarterly, Vol. 5, No. 5, 1967, pp. 424-434.

A. F. Horadam, Pell identities, Fib. Quart., 9 (1971), 245-252, 263.

Haruo Hosoya, What Can Mathematical Chemistry Contribute to the Development of Mathematics?, HYLE--International Journal for Philosophy of Chemistry, Vol. 19, No.1 (2013), pp. 87-105; http://www.hyle.org.

Clark Kimberling, "Best lower and upper approximates to irrational numbers," Elemente der Mathematik, 52 (1997) 122-126.

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

Shirley Law, Hopf Algebra of Sashes, in FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 621-632; http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAT0159/4536.

T. Mansour, M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.

A. Moghaddamfar, H. Tajbakhsh, More Determinant Representations for Sequences, Journal of Integer Sequences, 17 (2014), #14.5.6.

Hao Pan, Arithmetic properties of q-Fibonacci numbers and q-Pell numbers, Discr. Math., 306 (2006), 2118-2127. [N. J. A. Sloane, Jan 29 2009]

D. Panario, M. Sahin, Q. Wang, A family of Fibonacci-like conditional sequences, INTEGERS, Vol. 13, 2013, #A78.

Problem B-82, Fib. Quart., 4 (1966), 374-375.

P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 43.

J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.

J. L. Schiffman, Exploring the Fibonacci sequence of order two with CAS technology, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.392.6982&rep=rep1&type=pdf; no date.

Manfred R. Schroeder, "Number Theory in Science and Communication", 5-th ed., Springer-Verlag, 2009, p. 90. [Gary W. Adamson, Feb 21 2009]

Mark A. Shattuck, Tiling proofs of some formulas for the Pell numbers of odd index, Integers, 9 (2009), 53-64.

M. Shattuck, Combinatorial Proofs of Some Formulas for Triangular Tilings, Journal of Integer Sequences, 17 (2014), #14.5.5.

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).

Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see Eq. (20)).

A. Tekcan, M. Tayat, M. E. Ozbek, The diophantine equation 8x^2-y^2+8x(1+t)+(2t+1)^2=0 and t-balancing numbers, ISRN Combinatorics, Volume 2014, Article ID 897834, 5 pages, http://dx.doi.org/10.1155/2014/897834.

Meral Yasar and Durmus Bozkurt, Another proof of Pell identities by using the determinant of tridiagonal matrix, Appl. Math. Comput., 218 (2012), pp. 6067-6071

LINKS

N. J. A. Sloane and Simone Sandri, Table of n, a(n) for n = 0..1000 (First 500 terms from N. J. A. Sloane).

Tewodros Amdeberhan, Solution to problem #10663 (AMM)

J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

J. Bodeen, S. Butler, T. Kim, X. Sun, S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

E. S. Egge and T. Mansour, 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers.

Shaun Giberson and Thomas J. Osler, Extending Theon's Ladder to Any Square Root, College Mathematics Journal, May, 2004.

Nick Hobson, Python program for this sequence

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 135

Tanya Khovanova, Recursive Sequences

S. Kitaev, J. Remmel and M. Tiefenbruck, Quadrant marked mesh patterns in 132-avoiding permutations II, arXiv preprint arXiv:1302.2274, 2013

Simon Plouffe, Approximations de Séries Génératrices et Quelques Conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

C. Raissi and J. Pei, Towards Bounding Sequential Patterns.

José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368, 2012

James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2

R. A. Sulanke, Moments, Narayana numbers and the cut and paste for lattice paths

Ian Walker, Explorations in Recursion with John Pell and the Pell Sequence.

Eric Weisstein's World of Mathematics, Pell Number

Eric Weisstein's World of Mathematics, Pell Polynomial

Eric Weisstein's World of Mathematics, Square Root

Eric Weisstein's World of Mathematics, Pythagoras's Constant

Eric Weisstein's World of Mathematics, Square Triangular Number

Index entries for "core" sequences

Index entries for sequences related to Chebyshev polynomials.

Index to sequences with linear recurrences with constant coefficients, signature (2,1).

FORMULA

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

a(n) = 2*a(n-1)+a(n-2), a(0)=0, a(1)=1.

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

a(n) = integer nearest a(n-1)/(sqrt(2) - 1), where a(0) = 1. - Clark Kimberling

a(n) = Sum_{i, j, k >= 0: i+j+2k=n} (i+j+k)!/(i!*j!*k!).

a(n)^2 + a(n+1)^2 = a(2n+1) (1999 Putnam examination).

a(2n) = 2*a(n)*A001333(n). - John McNamara, Oct 30 2002

a(n) = ((-i)^(n-1))*S(n-1, 2*i), with S(n, x) := U(n, x/2) Chebyshev's polynomials of the second kind. See A049310. S(-1, x)=0, S(-2, x)= -1.

Binomial transform of expansion of sinh(sqrt(2)x)/sqrt(2). E.g.f.: exp(x)sinh(sqrt(2)x)/sqrt(2). - Paul Barry, May 09 2003

a(n) = sum{k=0, ..floor(n/2), C(n, 2k+1)2^k}. - Paul Barry, May 13 2003

a(n-2) + a(n) = (1 + sqrt2)^(n-1) + (1 - sqrt2)^(n-1) = A002203(n-1). [A002203(n)]^2 - 8[a(n)]^2 = 4(-1)^n. - Gary W. Adamson, Jun 15 2003

Nonreduced G.f. : x(1+x)/(1-x-3x^2-x^3); a(n)=a(n-1)+3a(n-2)+a(n-2). - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004

a(n+1) = sum(C(n-k, k)2^(n-2k), k=0, .., floor[n/2]). - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004

Apart from initial terms, inverse binomial transform of A052955. - Paul Barry, May 23 2004

a(n)^2+a(n+2k+1)^2=A001653(k)*A001653(n+k); e.g., 5^2+70^2=5*985. - Charlie Marion Aug 03 2005

a(n+1) = sum{k=0..n, binomial((n+k)/2, (n-k)/2)(1+(-1)^(n-k))2^k/2}. - Paul Barry, Aug 28 2005

a(n) = a(n - 1) + A001333(n - 1) = A001333(n) - a(n - 1) = A001109(n)/A001333(n) = sqrt(A001110(n)/A001333(n)^2) = ceiling(sqrt(A001108(n)/2)). - Henry Bottomley, Apr 18 2000

a(n) = F(n, 2), the n-th Fibonacci polynomial evaluated at x=2. - T. D. Noe, Jan 19 2006

Define c(2n) = -A001108(n), c(2n+1) = -A001108(n+1) and d(2n) = d(2n+1) = A001652(n), then ((-1)^n)*(c(n) + d(n)) = a(n). [Proof given by Max Alekseyev.] - Creighton Dement, Jul 21 2005

a(r+s) = a(r)*a(s+1) + a(r-1)*a(s). - Lekraj Beedassy, Sep 03 2006

a(n)=(b(n+1)+b(n-1))/n where {b(n)} is the sequence A006645. - Sergio Falcon, Nov 22 2006

From Miklos Kristof, Mar 19 2007: (Start)

Let F(n) = a(n) = Pell numbers, L(n) = A002203 = companion Pell numbers (A002203):

For a>=b and odd b F(a+b)+F(a-b)=L(a)*F(b).

For a>=b and even b F(a+b)+F(a-b)=F(a)*L(b).

For a>=b and odd b F(a+b)-F(a-b)=F(a)*L(b).

For a>=b and even b F(a+b)-F(a-b)=L(a)*F(b).

F(n+m)+(-1)^m*F(n-m) = F(n)*L(m)

F(n+m)-(-1)^m*F(n-m) = L(n)*F(m)

F(n+m+k)+(-1)^k*F(n+m-k)+(-1)^m*(F(n-m+k)+(-1)^k*F(n-m-k)) = F(n)*L(m)*L(k)

F(n+m+k)-(-1)^k*F(n+m-k)+(-1)^m*(F(n-m+k)-(-1)^k*F(n-m-k)) = L(n)*L(m)*F(k)

F(n+m+k)+(-1)^k*F(n+m-k)-(-1)^m*(F(n-m+k)+(-1)^k*F(n-m-k)) = L(n)*F(m)*L(k)

F(n+m+k)-(-1)^k*F(n+m-k)-(-1)^m*(F(n-m+k)-(-1)^k*F(n-m-k)) =8*F(n)*F(m)*F(k). (End)

a(n+1)*a(n)=2*sum{k=0..n, a(k)^2} (a similar relation holds for A001333). - Creighton Dement, Aug 28 2007

a(n+1) = sum(k=0,...,n) binomial(n+1,2k+1) * 2^k = sum(k=0,...,n) A034867(n,k) * 2^k = (1/n!)sum(k=0,...,n) A131980(n,k) * 2^k. - Tom Copeland, Nov 30 2007

Equals row sums of unsigned triangle A133156. - Gary W. Adamson, Apr 21 2008

a(n) (n>=3) is the determinant of the (n-1) by (n-1) tridiagonal matrix with diagonal entries 2, superdiagonal entries 1 and subdiagonal entries -1. - Emeric Deutsch, Aug 29 2008

a(n) = 5*a(n-2)+2*a(n-3), a(n) = 6*a(n-2)-a(n-4). - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 04 2008

a(n) = A000045(n) + sum_{k=1..n-1} A000045(k)*a(n-k). - Roger L. Bagula and Gary W. Adamson, Sep 07 2008

From Hieronymus Fischer, Jan 02 2009: (Start)

fract((1+sqrt(2))^n)) = (1/2)*(1+(-1)^n)-(-1)^n*(1+sqrt(2))^(-n) = (1/2)*(1+(-1)^n)-(1-sqrt(2))^n.

See A001622 for a general formula concerning the fractional parts of powers of numbers x>1, which satisfy x-x^(-1)=floor(x).

a(n) = round((1+sqrt(2))^n) for n>0. (End)

a(n)=((4+sqrt18)*(1+sqrt2)^n)+(4-sqrt18)*(1-sqrt2)^n)/4 offset 0. - Al Hakanson (hawkuu(AT)gmail.com), Aug 08 2009

If p[i]=fibonacci(i) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, May 08 2010

a(n) = 3*a(n-1)-a(n-2)-a(n-3),n>2. - Gary Detlefs, Sep 09 2010

a(n) = 2*(a(2k-1)+a(2k))*a(n-2k)-a(n-4k).

  a(n) = 2*(a(2k)+a(2k+1))*a(n-2k-1)+a(n-4k-2). - Charlie Marion, Apr 13 2011

G.f.: x/(1 - 2*x - x^2) = sqrt(2)*G(0)/4 ; G(k) = ((-1)^k) - 1/(((sqrt(2) + 1)^(2*k)) - x*((sqrt(2) + 1)^(2*k))/(x + ((sqrt(2) - 1)^(2*k + 1))/G(k+1))) ; (continued fraction). - Sergei N. Gladkovskii, Dec 02 2011

In general, for n>k, a(n) = a(k+1)*a(n-k) + a(k)*a(n-k-1).  See definition of Pell numbers and the formula for Sep 04 2008. - Charlie Marion, Jan 17 2012

a(n) = A216134(2*floor[n/2] + 1) - (2 - n(mod 2))A216134(2*floor[n/2]) + (1 - n(mod 2))A216134(2*floor[n/2] - 1); A216134 gives the indices of the Sophie Germain triangular numbers. - Raphie Frank, Jan 04 2013

Sum{n>=1}(-1)^(n-1)/(a(n)*a(n+1))=sqrt(2)-1. - Vladimir Shevelev, Feb 22 2013

From Vladimir Shevelev, Feb 24 2013: (Start)

(1) Expression a(n+1) via a(n): a(n+1) = a(n) + sqrt(2*a^2(n) + (-1)^n);

(2) a^2(n+1) - a(n)*a(n+2) = (-1)^n;

(3) sum_{k=1,...,n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);

(4) a(n)/a(n+1) = sqrt(2)-1 + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)

a(-n) = -(-1)^n * a(n). - Michael Somos, Jun 01 2013

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

G.f.: Q(0)*x/2, 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, Aug 30 2013

a(n) = sum_{0<=r<n} sum_{0<=k<n-r} binomial(r+k,k)*binomial(k,n-k-r-1). - Peter Luschny, Nov 16 2013

a(n) = sum{k=1,3,5,...<=n} C(n,k)*2^((k-1)/2). - Vladimir Shevelev, Feb 06 2014

a(2n) = 2*a(n)*(a(n-1) + a(n)). - John Blythe Dobson, Mar 08 2014

a(k*n) = a(k)*a(k*n-k+1) + a(k-1)*a(k*n-k). Charlie Marion, Mar 27 2014

a(k*n) = 2*a(k)*(a(k*n-k)+a(k*n-k-1)) + (-1)^k*a(k*n-2k). - Charlie Marion, Mar 30 2014

a(n+1) = (1+sqrt(2))*a(n)+(1-sqrt(2))^n. - Art DuPre, Apr 04 2014

a(n+1) = (1-sqrt(2))*a(n)+(1+sqrt(2))^n. - Art DuPre, Apr 04 2014

a(n) = F(n) + sum(k=1..n, F(k)*a(n-k) ), n>=0 where F(n) the Fibonacci numbers A000045. -  Ralf Stephan, May 23 2014

a(n) = round(sqrt(a(2n) + a(2n-1)))/2.  - Richard R. Forberg, Jun 22 2014

EXAMPLE

G.f. = x + 2*x^2 + 5*x^3 + 12*x^4 + 29*x^5 + 70*x^6 + 169*x^7 + 408*x^8 + 985*x^9 + ...

MAPLE

A000129 := proc(n) option remember; if n <=1 then n; else 2*A000129(n-1)+A000129(n-2); fi; end;

with(numtheory):pel := cfrac (sin(Pi/4), 100): seq(nthnumer(pel, i), i=0..29 ); # Zerinvary Lajos, Feb 07 2007

A000129:=-1/(-1+2*z+z**2); # Simon Plouffe in his 1992 dissertation.

a:= n-> (Matrix([[2, 1], [1, 0]])^n)[1, 2]: seq (a(n), n=0..40); # Alois P. Heinz, Aug 01 2008

MATHEMATICA

CoefficientList[Series[x/(1 - 2*x - x^2), {x, 0, 60}], x] (* Stefan Steinerberger, Apr 08 2006 *)

Expand[Table[((1 + Sqrt[2])^n - (1 - Sqrt[2])^n)/(2Sqrt[2]), {n, 0, 30}]] (* Artur Jasinski, Dec 10 2006 *)

a=1; b=0; c=0; lst={b}; Do[c=a+b+c; AppendTo[lst, c]; a=b; b=c, {n, 5!}]; lst (* Vladimir Joseph Stephan Orlovsky, Mar 23 2009 *)

LinearRecurrence[{2, 1}, {0, 1}, 60] (* Harvey P. Dale, Jan 04 2012 *)

a[ n_] := With[ {s = Sqrt@2}, ((1 + s)^n - (1 - s)^n) / (2 s)] // Simplify; (* Michael Somos, Jun 01 2013 *)

PROG

(PARI) { default(realprecision, 2000); for (n=0, 4000, a=contfracpnqn(vector(n, i, 1+(i>1)))[2, 1]; if (a > 10^(10^3 - 6), break); write("b000129.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 12 2009

(PARI) {a(n) = imag( (1 + quadgen( 8))^n )}; /* Michael Somos, Jun 01 2013 */

(PARI) {a(n) = if( n<0, -(-1)^n, 1) * contfracpnqn( vector( abs(n), i, 1 + (i>1))) [2, 1]}; /* Michael Somos, Jun 01 2013 */

(PARI) a(n)=([2, 1; 1, 0]^n)[2, 1] \\ Charles R Greathouse IV, Mar 04 2014

(Sage) [lucas_number1(n, 2, -1) for n in xrange(0, 30)] # Zerinvary Lajos, Apr 22 2009 (Haskell)

a000129 n = a000129_list !! n

a000129_list = 0 : 1 : zipWith (+) a000129_list (map (2 *) $ tail a000129_list)

-- Reinhard Zumkeller, Jan 05 2012, Feb 05 2011

(Maxima)

a[0]:0$

a[1]:1$

a[n]:=2*a[n-1]+a[n-2]$

A000129(n):=a[n]$

makelist(A000129(n), n, 0, 30); /* Martin Ettl, Nov 03 2012 */

CROSSREFS

Partial sums of A001333.

a(n) = A054456(n-1, 0), n>=1 (first column of triangle).

Cf. A002203, A096669, A096670, A097075, A097076, A051927, A005409, A175181 (Pisano periods).

A077985 is a signed version.

INVERT transform of Fibonacci numbers (A000045).

Cf. A038207.

The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.

Cf. A034867, A131980, A133156, A143808, A135387, A153346, A001622, A006497, A014176, A098316, A154325, A021083, A216134, A243399.

Sequence in context: A215936 * A077985 A215928 A054198 A054196 A131710

Adjacent sequences:  A000126 A000127 A000128 * A000130 A000131 A000132

KEYWORD

nonn,easy,core,cofr,nice,frac

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 18 06:09 EST 2014. Contains 252079 sequences.