|
Search: id:A000129
|
|
|
| A000129 |
|
Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2). (Formerly M1413 N0552)
|
|
+0 277
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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 (deutsch(AT)duke.poly.edu), 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. - W. Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), 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 (amarnath_murthy(AT)yahoo.com), 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 (rlahaye(AT)new.rr.com), Aug 18 2003
Number of 132-avoiding two-stack sortable permutations.
y satisfying x^2 - 2*y^2=-+1. Corresponding x given by A001333(n). - Lekraj Beedassy (blekraj(AT)yahoo.com), Jun 24 2004
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 (kociemba(AT)t-online.de), 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 (kociemba(AT)t-online.de), 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 (davidwwilson(AT)comcast.net)
Sums of antidiagonals of A038207 [Pascal's triangle squared] - Ross La Haye (rlahaye(AT)new.rr.com), 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 (jb(AT)brennen.net), Nov 13, 2004
a(n) = sum of n-th row of triangle in A008288 = A094706(n)+A000079(n). - Reinhard Zumkeller (reinhard.zumkeller(AT)lhsystems.com), 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 (charliemath(AT)optonline.net), Apr 1 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 (tcjpn(AT)msn.com), 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 (qntmpkt(AT)yahoo.com), 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 (qntmpkt(AT)yahoo.com), Mar 16 2008
|
|
REFERENCES
|
P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 76.
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.
A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
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.
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.
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.
Ayoub B. Ayoub, "Fibonacci-like sequences and Pell equations", The College Mathematics Journal, Vol. 38 (2007), pp. 49-53.
|
|
LINKS
|
N. J. A. Sloane, Table of n, a(n) for n = 0..500
Joerg Arndt, Fxtbook
Tewodros Amdeberhan, Solution to problem #10663 (AMM)
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....
Nick Hobson, Python program for this sequence
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 135
Tanya Khovanova, Recursive Sequences
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures}, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
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
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
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.
|
|
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 - from Clark Kimberling (ck6(AT)evansville.edu)
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 (pbarry(AT)wit.ie), May 09 2003
a(n)=sum{k=0, ..floor(n/2), C(n, 2k+1)2^k}. - Paul Barry (pbarry(AT)wit.ie), 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 (qntmpkt(AT)yahoo.com), Jun 15 2003
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 (charliemath(AT)optonline.net) 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 (pbarry(AT)wit.ie), 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 (se16(AT)btinternet.com), Apr 18 2000
a(n)=F(n, 2), the n-th Fibonacci polynomial evaluated at x=2. - T. D. Noe (noe(AT)sspectra.com), 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 (maxal(AT)cs.ucsd.edu) - Creighton Dement (creighton.k.dement(AT)uni-oldenburg.de), Jul 21 2005
a(r+s) = a(r)*a(s+1) + a(r-1)*a(s). - Lekraj Beedassy (blekraj(AT)yahoo.com), Sep 03 2006
a(n)=(b(n+1)+b(n-1))/n where {b(n)} is the sequence A006645 - Sergio Falcon (sfalcon(AT)dma.ulpgc.es), Nov 22 2006
Comments from Miklos Kristof (kristmikl(AT)freemail.hu), 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 (creighton.k.dement(AT)uni-oldenburg.de), 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 (tcjpn(AT)msn.com), Nov 30 2007
Equals row sums of unsigned triangle A133156. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 21 2008
|
|
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 (zerinvarylajos(AT)yahoo.com), Feb 07 2007
A000129:=-1/(-1+2*z+z**2); [S. Plouffe in his 1992 dissertation.]
|
|
MATHEMATICA
|
CoefficientList[Series[x/(1 - 2*x - x^2), {x, 0, 60}], x] - Stefan Steinerberger (stefan.steinerberger(AT)gmail.com), Apr 08 2006
Expand[Table[((1 + Sqrt[2])^n - (1 - Sqrt[2])^n)/(2Sqrt[2]), {n, 0, 30}]] - Artur Jasinski (grafix(AT)csl.pl), Dec 10 2006
|
|
PROGRAM
|
(PARI) a(n)=if(n<0, 0, contfracpnqn(vector(n, i, 1+(i>1)))[2, 1])
|
|
CROSSREFS
|
Partial sums of A001333, also A000129(n)+A000129(n+1) = A001333(n+1).
a(n) = A054456(n-1, 0), n>=1 (first column of triangle).
Cf. A002203, A096669, A096670, A097075, A097076, A051927, A005409.
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.
Adjacent sequences: A000126 A000127 A000128 this_sequence A000130 A000131 A000132
Sequence in context: A067687 A130009 A048624 this_sequence A077985 A054198 A054196
Cf. A133156.
|
|
KEYWORD
|
nonn,easy,core,cofr,nice,frac,new
|
|
AUTHOR
|
njas
|
|
|
Search completed in 0.007 seconds
|