cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 49 results. Next

A000129 Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2).

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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). Limit_{n->oo} a(n)/a(n-1) = sqrt(2) + 1 = A014176. - Ross La Haye, Aug 18 2003
Number of 132-avoiding two-stack sortable permutations.
From Herbert Kociemba, Jun 02 2004: (Start)
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.
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. (End)
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*(0.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) = 0.414213562... = [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
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, A153314, A153315, A153316, A153317, A153318.
(End)
Starting with offset 1 = row sums of triangle A155002, equivalent to the statement that the Fibonacci sequence convolved with the Pell sequence 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(17)). - 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, 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, Jul 04 2009
As a fraction: 1/79 = 0.0126582278481... or 1/9799 = 0.000102051229...(1/119 and 1/10199 for sequence in reverse). - Mark Dols, May 18 2010
Limit_{n->oo} (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 k such that 2*k^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 2 X 2 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)*sqrt(2) and each of the coordinates of its point of intersection with C(n + 1) is a(2n + 1) + (A001333(2n + 1)*sqrt(2))/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 also be called "silver Fibonacci numbers", since, for n >= 1, F(n+1) = ceiling(phi*F(n)), if n is even and F(n+1) = floor(phi*F(n)), if n is odd, where phi is the golden ratio, while a(n+1) = ceiling(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 the 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 1 X n 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
For n >= 1, a(n) equals the number of ternary words of length n-1 avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015
This is a divisibility sequence (i.e., if n|m then a(n)|a(m)). - Tom Edgar, Jan 28 2015
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Jan 03 2017
a(n) is the number of compositions (ordered partitions) of n-1 into two kinds of parts, n and n', when the order of the 1 does not matter, or equivalently, when the order of the 1' does not matter. Example: When the order of the 1 does not matter, the a(3)=5 compositions of 3-1=2 are 1+1, 1+1'=1+1, 1'+1', 2 and 2'. (Contrast with entry from Bob Selcoe dated Jun 21 2013.) - Gregory L. Simay, Sep 07 2017
Number of weak orderings R on {1,...,n} that are weakly single-peaked w.r.t. the total ordering 1 < ... < n and for which {1,...,n} has exactly one minimal element for the weak ordering R. - J. Devillet, Sep 28 2017
Also the number of matchings in the (n-1)-centipede graph. - Eric W. Weisstein, Sep 30 2017
Let A(r,n) be the total number of ordered arrangements of an n+r tiling of r red squares and white tiles of total length n, where the individual tile lengths can range from 1 to n. A(r,0) corresponds to a tiling of r red squares only, and so A(r,0)=1. Let A_1(r,n) = Sum_{j=0..n} A(r,j) and let A_s(r,n) = Sum_{j=0..n} A_(s-1)(r,j). Then A_0(1,n) + A_2(3,n-4) + A_4(5,n-8) + ... + A_(2j) (2j+1, n-4j) = a(n) without the initial 0. - Gregory L. Simay, May 25 2018
(1, 2, 5, 12, 29, ...) is the fourth INVERT transform of (1, -2, 5, -12, 29, ...), as shown in A073133. - Gary W. Adamson, Jul 17 2019
Number of 2-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
Also called the 2-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence. - Michael A. Allen, Jan 23 2023
Named by Lucas (1878) after the English mathematician John Pell (1611-1685). - Amiram Eldar, Oct 02 2023
a(n) is the number of compositions of n when there are F(i) parts of size i, with i,n >= 1, F(n) the Fibonacci numbers, A000045(n) (see example below). - Enrique Navarrete, Dec 15 2023

Examples

			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 + ...
From _Enrique Navarrete_, Dec 15 2023: (Start)
From the comment on compositions with Fibonacci number of parts, F(n), there are F(1)=1 type of 1, F(2)=1 type of 2, F(3)=2 types of 3, F(4)=3 types of 4, F(5)=5 types of 5 and F(6)=8 types of 6.
The following table gives the number of compositions of n=6 with Fibonacci number of parts:
Composition, number of such compositions, number of compositions of this type:
6,           1,     8;
5+1,         2,    10;
4+2,         2,     6;
3+3,         1,     4;
4+1+1,       3,     9;
3+2+1,       6,    12;
2+2+2,       1,     1;
3+1+1+1,     4,     8;
2+2+1+1,     6,     6;
2+1+1+1+1,   5,     5;
1+1+1+1+1+1, 1,     1;
for a total of a(6)=70 compositions of n=6. (End).

References

  • J. Austin and L. Schneider, Generalized Fibonacci sequences in Pythagorean triple preserving sequences, Fib. Q., 58:1 (2020), 340-350.
  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 76.
  • A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 941.
  • 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.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 204.
  • John Derbyshire, Prime Obsession, Joseph Henry Press, 2004, see p. 16.
  • 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.
  • R. P. Grimaldi, Ternary strings with no consecutive 0's and no consecutive 1's, Congressus Numerantium, 205 (2011), 129-149.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.5 The Fibonacci and Related Sequences, p. 288.
  • Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
  • Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
  • Paulo Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 43.
  • Paulo Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer-Verlag, NY, 2000, p. 3.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 46, 61.
  • J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
  • Manfred R. Schroeder, "Number Theory in Science and Communication", 5th ed., Springer-Verlag, 2009, p. 90.
  • 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).
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987, p. 34.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 62.

Links

Crossrefs

Partial sums of A001333.
2nd row of A172236.
a(n) = A054456(n-1, 0), n>=1 (first column of triangle).
Cf. A002203, A096669, A096670, A097075, A097076, A051927, A005409.
Cf. A175181 (Pisano periods), A214028 (Entry points), A214027 (number of zeros in a fundamental period).
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 (growth power), A098316, A154325, A021083, A243399, A008555.
Cf. A048739.
Cf. A073133.
Cf. A041085.
Cf. A157103, A352361.
Sequences with g.f. 1/(1-k*x-x^2) or x/(1-k*x-x^2): A000045 (k=1), this sequence (k=2), A006190 (k=3), A001076 (k=4), A052918 (k=5), A005668 (k=6), A054413 (k=7), A041025 (k=8), A099371 (k=9), A041041 (k=10), A049666 (k=11), A041061 (k=12), A140455 (k=13), A041085 (k=14), A154597 (k=15), A041113 (k=16), A178765 (k=17), A041145 (k=18), A243399 (k=19), A041181 (k=20).

Programs

  • GAP
    a := [0,1];; for n in [3..10^3] do a[n] := 2 * a[n-1] + a[n-2]; od; A000129 := a; # Muniru A Asiru, Oct 16 2017
  • 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
  • Magma
    [0] cat [n le 2 select n else 2*Self(n-1) + Self(n-2): n in [1..35]]; // Vincenzo Librandi, Aug 08 2015
  • Maple
    A000129 := proc(n) option remember; if n <=1 then n; else 2*procname(n-1)+procname(n-2); fi; end;
a:= n-> (<<2|1>, <1|0>>^n)[1, 2]: seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008
A000129 := n -> `if`(n<2, n, 2^(n-1)*hypergeom([1-n/2, (1-n)/2], [1-n], -1)):
seq(simplify(A000129(n)), n=0..31); # Peter Luschny, Dec 17 2015
  • 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 *)
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 *)
Table[Fibonacci[n, 2], {n, 0, 20}] (* Vladimir Reshetnikov, May 08 2016 *)
Fibonacci[Range[0, 20], 2] (* Eric W. Weisstein, Sep 30 2017 *)
a[ n_] := ChebyshevU[n - 1, I] / I^(n - 1); (* Michael Somos, Oct 30 2021 *)
  • 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 */
  • Maxima
    makelist((%i)^(n-1)*ultraspherical(n-1,1,-%i),n,0,24),expand; /* Emanuele Munarini, Mar 07 2018 */
  • PARI
    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
  • PARI
    {a(n) = polchebyshev(n-1, 2, I) / I^(n-1)}; /* Michael Somos, Oct 30 2021 */
  • Python
    from itertools import islice
def A000129_gen(): # generator of terms
    a, b = 0, 1
    yield from [a,b]
    while True:
        a, b = b, a+2*b
        yield b
A000129_list = list(islice(A000129_gen(),20)) # Chai Wah Wu, Jan 11 2022
  • Sage
    [lucas_number1(n, 2, -1) for n in range(30)]  # Zerinvary Lajos, Apr 22 2009

Formula

G.f.: x/(1 - 2*x - x^2). - Simon Plouffe in his 1992 dissertation.
a(2n+1)=A001653(n). a(2n)=A001542(n). - Ira Gessel, Sep 27 2002
G.f.: Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (2*k + x)/(1 + 2*k*x) ) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (x + 1 + k)/(1 + k*x) ) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (x + 3 - k)/(1 - k*x) ) may all be proved using telescoping series. - Peter Bala, Jan 04 2015
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)).
For initial values a(0) and a(1), a(n) = ((a(0)*sqrt(2)+a(1)-a(0))*(1+sqrt(2))^n + (a(0)*sqrt(2)-a(1)+a(0))*(1-sqrt(2))^n)/(2*sqrt(2)). - Shahreer Al Hossain, Aug 18 2019
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)} binomial(n, 2k+1)*2^k. - Paul Barry, May 13 2003
a(n-2) + a(n) = (1 + sqrt(2))^(n-1) + (1 - sqrt(2))^(n-1) = A002203(n-1). (A002203(n))^2 - 8(a(n))^2 = 4(-1)^n. - Gary W. Adamson, Jun 15 2003
Unreduced g.f.: x(1+x)/(1 - x - 3x^2 - x^3); a(n) = a(n-1) + 3*a(n-2) + a(n-2). - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*2^(n-2k). - 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) X (n-1) tridiagonal matrix with diagonal entries 2, superdiagonal entries 1 and subdiagonal entries -1. - Emeric Deutsch, Aug 29 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/(2*sqrt(2))) for n > 0. (End) [last formula corrected by Josh Inman, Mar 05 2024]
a(n) = ((4+sqrt(18))*(1+sqrt(2))^n + (4-sqrt(18))*(1-sqrt(2))^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] when i<=j, A[i,j]=-1 when 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
From Charlie Marion, Apr 13 2011: (Start)
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). (End)
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
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(n+1)^2 - 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_{r=0..n-1} Sum_{k=0..n-r-1} 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
a(n) = Product_{k divides n} A008555(k). - Tom Edgar, Jan 28 2015
a(n+k)^2 - A002203(k)*a(n)*a(n+k) + (-1)^k*a(n)^2 = (-1)^n*a(k)^2. - Alexander Samokrutov, Aug 06 2015
a(n) = 2^(n-1)*hypergeom([1-n/2, (1-n)/2], [1-n], -1) for n >= 2. - Peter Luschny, Dec 17 2015
a(n+1) = Sum_{k=0..n} binomial(n,k)*2^floor(k/2). - Tony Foster III, May 07 2017
a(n) = exp((i*Pi*n)/2)*sinh(n*arccosh(-i))/sqrt(2). - Peter Luschny, Mar 07 2018
From Rogério Serôdio, Mar 30 2018: (Start)
Some properties:
(1) a(n)^2 - a(n-2)^2 = 2*a(n-1)*(a(n) + a(n-2)) (see A005319);
(2) a(n-k)*a(n+k) = a(n)^2 + (-1)^(n+k+1)*a(k)^2;
(3) Sum_{k=2..n+1} a(k)*a(k-1) = a(n+1)^2 if n is odd, else a(n+1)^2 - 1 if n is even;
(4) a(n) - a(n-2*k+1) = (A077444(k) - 1)*a(n-2*k+1) + a(n-4*k+2);
(5) Sum_{k=n..n+9} a(k) = 41*A001333(n+5). (End)
From Kai Wang, Dec 30 2019: (Start)
a(m+r)*a(n+s) - a(m+s)*a(n+r) = -(-1)^(n+s)*a(m-n)*a(r-s).
a(m+r)*a(n+s) + a(m+s)*a(n+r) = (2*A002203(m+n+r+s) - (-1)^(n+s)*A002203(m-n)*A002203(r-s))/8.
A002203(m+r)*A002203(n+s) - A002203(m+s)*A002203(n+r) = (-1)^(n+s)*8*a(m-n)*a(r-s).
A002203(m+r)*A002203(n+s) - 8*a(m+s)*a(n+r) = (-1)^(n+s)*A002203(m-n)*A002203(r-s).
A002203(m+r)*A002203(n+s) + 8*a(m+s)*a(n+r) = 2*A002203(m+n+r+s)+ (-1)^(n+s)*8*a(m-n)*a(r-s). (End)
From Kai Wang, Jan 12 2020: (Start)
a(n)^2 - a(n+1)*a(n-1) = (-1)^(n-1).
a(n)^2 - a(n+r)*a(n-r) = (-1)^(n-r)*a(r)^2.
a(m)*a(n+1) - a(m+1)*a(n) = (-1)^n*a(m-n).
a(m-n) = (-1)^n (a(m)*A002203(n) - A002203(m)*a(n))/2.
a(m+n) = (a(m)*A002203(n) + A002203(m)*a(n))/2.
A002203(n)^2 - A002203(n+r)*A002203(n-r) = (-1)^(n-r-1)*8*a(r)^2.
A002203(m)*A002203(n+1) - A002203(m+1)*A002203(n) = (-1)^(n-1)*8*a(m-n).
A002203(m-n) = (-1)^(n)*(A002203(m)*A002203(n) - 8*a(m)*a(n) )/2.
A002203(m+n) = (A002203(m)*A002203(n) + 8*a(m)*a(n) )/2. (End)
From Kai Wang, Mar 03 2020: (Start)
Sum_{m>=1} arctan(2/a(2*m+1)) = arctan(1/2).
Sum_{m>=2} arctan(2/a(2*m+1)) = arctan(1/12).
In general, for n > 0,
Sum_{m>=n} arctan(2/a(2*m+1)) = arctan(1/a(2*n)). (End)
a(n) = (A001333(n+3*k) + (-1)^(k-1)*A001333(n-3*k)) / (20*A041085(k-1)) for any k>=1. - Paul Curtz, Jun 23 2021
Sum_{i=0..n} a(i)*J(n-i) = (a(n+1) + a(n) - J(n+2))/2 for J(n) = A001045(n). - Greg Dresden, Jan 05 2022
From Peter Bala, Aug 20 2022: (Start)
Sum_{n >= 1} 1/(a(2*n) + 1/a(2*n)) = 1/2.
Sum_{n >= 1} 1/(a(2*n+1) - 1/a(2*n+1)) = 1/4. Both series telescope - see A075870 and A005319.
Product_{n >= 1} ( 1 + 2/a(2*n) ) = 1 + sqrt(2).
Product_{n >= 2} ( 1 - 2/a(2*n) ) = (1/3)*(1 + sqrt(2)). (End)
G.f. = 1/(1 - Sum_{k>=1} Fibonacci(k)*x^k). - Enrique Navarrete, Dec 17 2023
Sum_{n >=1} 1/a(n) = 1.84220304982752858079237158327980838... - R. J. Mathar, Feb 05 2024
a(n) = ((3^(n+1) + 1)^(n-1) mod (9^(n+1) - 2)) mod (3^(n+1) - 1). - Joseph M. Shunia, Jun 06 2024

A001333 Pell-Lucas numbers: numerators of continued fraction convergents to sqrt(2).

Original entry on oeis.org

1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243, 275807, 665857, 1607521, 3880899, 9369319, 22619537, 54608393, 131836323, 318281039, 768398401, 1855077841, 4478554083, 10812186007, 26102926097, 63018038201, 152139002499, 367296043199
Offset: 0

Views

Author

N. J. A. Sloane and R. K. Guy

Keywords

Comments

Number of n-step non-selfintersecting paths starting at (0,0) with steps of types (1,0), (-1,0) or (0,1) [Stanley].
Number of n steps one-sided prudent walks with east, west and north steps. - Shanzhen Gao, Apr 26 2011
Number of ternary strings of length n-1 with subwords (0,2) and (2,0) not allowed. - Olivier Gérard, Aug 28 2012
Number of symmetric 2n X 2 or (2n-1) X 2 crossword puzzle grids: all white squares are edge connected; at least 1 white square on every edge of grid; 180-degree rotational symmetry. - Erich Friedman
a(n+1) is the number of ways to put molecules on a 2 X n ladder lattice so that the molecules do not touch each other.
In other words, a(n+1) is the number of independent vertex sets and vertex covers in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, Apr 04 2017
Number of (n-1) X 2 binary arrays with a path of adjacent 1's from top row to bottom row, see A359576. - R. H. Hardin, Mar 16 2002
a(2*n+1) with b(2*n+1) := A000129(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = -1.
a(2*n) with b(2*n) := A000129(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = +1 (see Emerson reference).
Bisection: a(2*n) = T(n,3) = A001541(n), n >= 0 and a(2*n+1) = S(2*n,2*sqrt(2)) = A002315(n), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.
Binomial transform of A077957. - Paul Barry, Feb 25 2003
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) = 2. - Herbert Kociemba, Jun 02 2004
For n > 1, a(n) corresponds to the longer side of a near right-angled isosceles triangle, one of the equal sides being A000129(n). - Lekraj Beedassy, Aug 06 2004
Exponents of terms in the series F(x,1), where F is determined by the equation F(x,y) = xy + F(x^2*y,x). - Jonathan Sondow, Dec 18 2004
Number of n-words from the alphabet A={0,1,2} which two neighbors differ by at most 1. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Aug 30 2006
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 numerators. - Amarnath Murthy, Mar 22 2003 [Amended by Paul E. Black (paul.black(AT)nist.gov), Dec 18 2006]
Odd-indexed prime numerators are prime RMS numbers (A140480) and also NSW primes (A088165). - Ctibor O. Zizka, Aug 13 2008
The intermediate convergents to 2^(1/2) begin with 4/3, 10/7, 24/17, 58/41; essentially, numerators=A052542 and denominators here. - Clark Kimberling, Aug 26 2008
Equals right border of triangle A143966. Starting (1, 3, 7, ...) equals INVERT transform of (1, 2, 2, 2, ...) and row sums of triangle A143966. - Gary W. Adamson, Sep 06 2008
Inverse binomial transform of A006012; Hankel transform is := [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 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 b(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. A000129, A142238-A142239, A153313-A153318.
(End)
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
Let M = a triangle with the Fibonacci series in each column, but the leftmost column is shifted upwards one row. A001333 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010
a(n) is the number of compositions of n when there are 1 type of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
Equals the INVERTi transform of A055099. - Gary W. Adamson, Aug 14 2010
From L. Edson Jeffery, Apr 04 2011: (Start)
Let U be the unit-primitive matrix (see [Jeffery])
U = U_(8,2) = (0 0 1 0)
(0 1 0 1)
(1 0 2 0)
(0 2 0 1).
Then a(n) = (1/4)*Trace(U^n). (See also A084130, A006012.)
(End)
For n >= 1, row sums of triangle
m/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....2
.2..|..1.....2.....4
.3..|..1.....4.....4.....8
.4..|..1.....4....12.....8....16
.5..|..1.....6....12....32....16....32
.6..|..1.....6....24....32....80....32....64
.7..|..1.....8....24....80....80...192....64...128
which is the triangle for numbers 2^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012
a(n) is also the number of ways to place k non-attacking wazirs on a 2 X n board, summed over all k >= 0 (a wazir is a leaper [0,1]). - Vaclav Kotesovec, May 08 2012
The sequences a(n) and b(n) := A000129(n) are entries of powers of the special case of the Brahmagupta Matrix - for details see Suryanarayan's paper. Further, as Suryanarayan remark, if we set A = 2*(a(n) + b(n))*b(n), B = a(n)*(a(n) + 2*b(n)), C = a(n)^2 + 2*a(n)*b(n) + 2*b(n)^2 we obtain integral solutions of the Pythagorean relation A^2 + B^2 = C^2, where A and B are consecutive integers. - Roman Witula, Jul 28 2012
Pisano period lengths: 1, 1, 8, 4, 12, 8, 6, 4, 24, 12, 24, 8, 28, 6, 24, 8, 16, 24, 40, 12, .... - R. J. Mathar, Aug 10 2012
This sequence and A000129 give the diagonal numbers described by Theon of Smyrna. - Sture Sjöstedt, Oct 20 2012
a(n) is the top left entry of the n-th power of any of the following six 3 X 3 binary matrices: [1, 1, 1; 1, 1, 1; 1, 0, 0] or [1, 1, 1; 1, 1, 0; 1, 1, 0] or [1, 1, 1; 1, 0, 1; 1, 1, 0] or [1, 1, 1; 1, 1, 0; 1, 0, 1] or [1, 1, 1; 1, 0, 1; 1, 0, 1] or [1, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
If p is prime, a(p) == 1 (mod p) (compare with similar comment for A000032). - Creighton Dement, Oct 11 2005, modified by Davide Colazingari, Jun 26 2016
a(n) = A000129(n) + A000129(n-1), where A000129(n) is the n-th Pell Number; e.g., a(6) = 99 = A000129(6) + A000129(5) = 70 + 29. Hence the sequence of fractions has the form 1 + A000129(n-1)/A000129(n), and the ratio A000129(n-1)/A000129(n)converges to sqrt(2) - 1. - Gregory L. Simay, Nov 30 2018
For n > 0, a(n+1) is the length of tau^n(1) where tau is the morphism: 1 -> 101, 0 -> 1. See Song and Wu. - Michel Marcus, Jul 21 2020
For n > 0, a(n) is the number of nonisomorphic quasitrivial semigroups with n elements, see Devillet, Marichal, Teheux. A292932 is the number of labeled quasitrivial semigroups. - Peter Jipsen, Mar 28 2021
a(n) is the permanent of the n X n tridiagonal matrix defined in A332602. - Stefano Spezia, Apr 12 2022
From Greg Dresden, May 08 2023: (Start)
For n >= 2, 4*a(n) is the number of ways to tile this T-shaped figure of length n-1 with two colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 4*a(6) = 396 different tilings.
_
|| _
|||_|||
|_|
(End)
12*a(n) = number of walks of length n in the cyclic Kautz digraph CK(3,4). - Miquel A. Fiol, Feb 15 2024

Examples

			Convergents are 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.
The 15 3 X 2 crossword grids, with white squares represented by an o:
  ooo ooo ooo ooo ooo ooo ooo oo. o.o .oo o.. .o. ..o oo. .oo
  ooo oo. o.o .oo o.. .o. ..o ooo ooo ooo ooo ooo ooo .oo oo.
G.f. = 1 + x + 3*x^2 + 7*x^3 + 17*x^4 + 41*x^5 + 99*x^6 + 239*x^7 + 577*x^8 + ...

References

  • M. R. Bacon and C. K. Cook, Some properties of Oresme numbers and convolutions ..., Fib. Q., 62:3 (2024), 233-240.
  • A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 204.
  • John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.
  • J. Devillet, J.-L. Marichal, and B. Teheux, Classifications of quasitrivial semigroups, Semigroup Forum, 100 (2020), 743-764.
  • Maribel Díaz Noguera [Maribel Del Carmen Díaz Noguera], Rigoberto Flores, Jose L. Ramirez, and Martha Romero Rojas, Catalan identities for generalized Fibonacci polynomials, Fib. Q., 62:2 (2024), 100-111.
  • Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
  • R. P. Grimaldi, Ternary strings with no consecutive 0's and no consecutive 1's, Congressus Numerantium, 205 (2011), 129-149.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.5 The Fibonacci and Related Sequences, p. 288.
  • A. F. Horadam, R. P. Loh, and A. G. Shannon, Divisibility properties of some Fibonacci-type sequences, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.
  • Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
  • Kin Y. Li, Math Problem Book I, 2001, p. 24, Problem 159.
  • I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 102, Problem 10.
  • J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
  • 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).
  • R. P. Stanley, Enumerative Combinatorics, Volume 1 (1986), p. 203, Example 4.1.2.
  • A. Tarn, Approximations to certain square roots and the series of numbers connected therewith, Mathematical Questions and Solutions from the Educational Times, 1 (1916), 8-12.
  • R. C. Tilley et al., The cell growth problem for filaments, Proc. Louisiana Conf. Combinatorics, ed. R. C. Mullin et al., Baton Rouge, 1970, 310-339.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987, p. 34.

Links

Crossrefs

For denominators see A000129.
See A040000 for the continued fraction expansion of sqrt(2).
See also A078057 which is the same sequence without the initial 1.
Cf. also A002203, A152113.
Row sums of unsigned Chebyshev T-triangle A053120. a(n)= A054458(n, 0) (first column of convolution triangle).
Row sums of A140750, A160756, A135837.
Equals A034182(n-1) + 2 and A084128(n)/2^n. First differences of A052937. Partial sums of A052542. Pairwise sums of A048624. Bisection of A002965.
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
Second row of the array in A135597.
Cf. A048211, A153588, A174283, A174284, A174285, A174286, A176499, A176500, A176501, A176502.
Cf. A055099.
Cf. A028859, A001906 / A088305, A033303, A000225, A095263, A003945, A006356, A002478, A214260, A001911 and A000217 for other restricted ternary words.
Cf. Triangle A106513 (alternating row sums).
Equals A293004 + 1.
Cf. A033539, A332602, A086395 (subseq. of primes).

Programs

  • Haskell
    a001333 n = a001333_list !! n
a001333_list = 1 : 1 : zipWith (+)
                       a001333_list (map (* 2) $ tail a001333_list)
-- Reinhard Zumkeller, Jul 08 2012
  • Magma
    [n le 2 select 1 else 2*Self(n-1)+Self(n-2): n in [1..35]]; // Vincenzo Librandi, Nov 10 2018
  • Maple
    A001333 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else 2*procname(n-1)+procname(n-2) fi end;
Digits := 50; A001333 := n-> round((1/2)*(1+sqrt(2))^n);
with(numtheory): cf := cfrac (sqrt(2),1000): [seq(nthnumer(cf,i), i=0..50)];
a:= n-> (M-> M[2, 1]+M[2, 2])(<<2|1>, <1|0>>^n):
seq(a(n), n=0..33);  # Alois P. Heinz, Aug 01 2008
A001333List := proc(m) local A, P, n; A := [1,1]; P := [1,1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-2]]);
A := [op(A), P[-1]] od; A end: A001333List(32); # Peter Luschny, Mar 26 2022
  • Mathematica
    Insert[Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[2], n]]], {n, 1, 40}], 1, 1] (* Stefan Steinerberger, Apr 08 2006 *)
Table[((1 - Sqrt[2])^n + (1 + Sqrt[2])^n)/2, {n, 0, 29}] // Simplify (* Robert G. Wilson v, May 02 2006 *)
a[0] = 1; a[1] = 1; a[n_] := a[n] = 2a[n - 1] + a[n - 2]; Table[a@n, {n, 0, 29}] (* Robert G. Wilson v, May 02 2006 *)
Table[ MatrixPower[{{1, 2}, {1, 1}}, n][[1, 1]], {n, 0, 30}] (* Robert G. Wilson v, May 02 2006 *)
a=c=0;t={b=1}; Do[c=a+b+c; AppendTo[t,c]; a=b;b=c,{n,40}]; t (* Vladimir Joseph Stephan Orlovsky, Mar 23 2009 *)
LinearRecurrence[{2, 1}, {1, 1}, 40] (* Vladimir Joseph Stephan Orlovsky, Mar 23 2009 *)
Join[{1}, Numerator[Convergents[Sqrt[2], 30]]] (* Harvey P. Dale, Aug 22 2011 *)
Table[(-I)^n ChebyshevT[n, I], {n, 10}] (* Eric W. Weisstein, Apr 04 2017 *)
CoefficientList[Series[(-1 + x)/(-1 + 2 x + x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
Table[Sqrt[(ChebyshevT[n, 3] + (-1)^n)/2], {n, 0, 20}] (* Eric W. Weisstein, Apr 17 2018 *)
  • PARI
    {a(n) = if( n<0, (-1)^n, 1) * contfracpnqn( vector( abs(n), i, 1 + (i>1))) [1, 1]}; /* Michael Somos, Sep 02 2012 */
  • PARI
    {a(n) = polchebyshev(n, 1, I) / I^n}; /* Michael Somos, Sep 02 2012 */
  • PARI
    a(n) = real((1 + quadgen(8))^n); \\ Michel Marcus, Mar 16 2021
  • PARI
    { for (n=0, 4000, a=contfracpnqn(vector(n, i, 1+(i>1)))[1, 1]; if (a > 10^(10^3 - 6), break); write("b001333.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 12 2009
  • Python
    from functools import cache
@cache
def a(n): return 1 if n < 2 else 2*a(n-1) + a(n-2)
print([a(n) for n in range(32)]) # Michael S. Branicky, Nov 13 2022
  • Sage
    from sage.combinat.sloane_functions import recur_gen2
it = recur_gen2(1,1,2,1)
[next(it) for i in range(30)] ## Zerinvary Lajos, Jun 24 2008
  • Sage
    [lucas_number2(n,2,-1)/2 for n in range(0, 30)] # Zerinvary Lajos, Apr 30 2009

Formula

a(n) = A055642(A125058(n)). - Reinhard Zumkeller, Feb 02 2007
a(n) = 2a(n-1) + a(n-2);
a(n) = ((1-sqrt(2))^n + (1+sqrt(2))^n)/2.
a(n)+a(n+1) = 2 A000129(n+1). 2*a(n) = A002203(n).
G.f.: (1 - x) / (1 - 2*x - x^2) = 1 / (1 - x / (1 - 2*x / (1 + x))). - Simon Plouffe in his 1992 dissertation.
A000129(2n) = 2*A000129(n)*a(n). - John McNamara, Oct 30 2002
a(n) = (-i)^n * T(n, i), with T(n, x) Chebyshev's polynomials of the first kind A053120 and i^2 = -1.
a(n) = a(n-1) + A052542(n-1), n>1. a(n)/A052542(n) converges to sqrt(1/2). - Mario Catalani (mario.catalani(AT)unito.it), Apr 29 2003
E.g.f.: exp(x)cosh(x*sqrt(2)). - Paul Barry, May 08 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)2^k. - Paul Barry, May 13 2003
For n > 0, a(n)^2 - (1 + (-1)^(n))/2 = Sum_{k=0..n-1} ((2k+1)*A001653(n-1-k)); e.g., 17^2 - 1 = 288 = 1*169 + 3*29 + 5*5 + 7*1; 7^2 = 49 = 1*29 + 3*5 + 5*1. - Charlie Marion, Jul 18 2003
a(n+2) = A078343(n+1) + A048654(n). - Creighton Dement, Jan 19 2005
a(n) = A000129(n) + A000129(n-1) = A001109(n)/A000129(n) = sqrt(A001110(n)/A000129(n)^2) = ceiling(sqrt(A001108(n))). - Henry Bottomley, Apr 18 2000
Also the first differences of A000129 (the Pell numbers) because A052937(n) = A000129(n+1) + 1. - Graeme McRae, Aug 03 2006
a(n) = Sum_{k=0..n} A122542(n,k). - Philippe Deléham, Oct 08 2006
For another recurrence see A000129.
a(n) = Sum_{k=0..n} A098158(n,k)*2^(n-k). - Philippe Deléham, Dec 26 2007
a(n) = upper left and lower right terms of [1,1; 2,1]^n. - Gary W. Adamson, Mar 12 2008
If p[1]=1, and p[i]=2, (i>1), and if A is 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, Apr 29 2010
For n>=2, a(n)=F_n(2)+F_(n+1)(2), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i)x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
a(-n) = (-1)^n * a(n). - Michael Somos, Sep 02 2012
Dirichlet g.f.: (PolyLog(s,1-sqrt(2)) + PolyLog(s,1+sqrt(2)))/2. - Ilya Gutkovskiy, Jun 26 2016
a(n) = A000129(n) - A000129(n-1), where A000129(n) is the n-th Pell Number. Hence the continued fraction is of the form 1-(A000129(n-1)/A000129(n)). - Gregory L. Simay, Nov 09 2018
a(n) = (A000129(n+3) + A000129(n-3))/10, n>=3. - Paul Curtz, Jun 16 2021
a(n) = (A000129(n+6) - A000129(n-6))/140, n>=6. - Paul Curtz, Jun 20 2021
a(n) = round((1/2)*sqrt(Product_{k=1..n} 4*(1 + sin(k*Pi/n)^2))), for n>=1. - Greg Dresden, Dec 28 2021
a(n)^2 + a(n+1)^2 = A075870(n+1) = 2*(b(n)^2 + b(n+1)^2) for all n in Z where b(n) := A000129(n). - Michael Somos, Apr 02 2022
a(n) = 2*A048739(n-2)+1. - R. J. Mathar, Feb 01 2024
Sum_{n>=1} 1/a(n) = 1.5766479516393275911191017828913332473... - R. J. Mathar, Feb 05 2024
From Peter Bala, Jul 06 2025: (Start)
G.f.: Sum_{n >= 1} (-1)^(n+1) * x^(n-1) * Product_{k = 1..n} (1 - k*x)/(1 - 3*x + k*x^2).
The following series telescope:
Sum_{n >= 1} (-1)^(n+1)/(a(2*n) + 1/a(2*n)) = 1/4, since 1/(a(2*n) + 1/a(2*n)) = 1/A077445(n) + 1/A077445(n+1).
Sum_{n >= 1} (-1)^(n+1)/(a(2*n+1) - 1/a(2*n+1)) = 1/8, since. 1/(a(2*n+1) - 1/a(2*n+1)) = 1/(4*Pell(2*n)) + 1/(4*Pell(2*n+2)), where Pell(n) = A000129(n).
Sum_{n >= 1} (-1)^(n+1)/(a(2*n+1) + 9/a(2*n+1)) = 1/10, since 1/(a(2*n+1) + 9/a(2*n+1)) = b(n) + b(n+1), where b(n) = A001109(n)/(2*Pell(2*n-1)*Pell(2*n+1)).
Sum_{n >= 1} (-1)^(n+1)/(a(n)*a(n+1)) = 1 - sqrt(2)/2 = A268682, since (-1)^(n+1)/(a(n)*a(n+1)) = Pell(n)/a(n) - Pell(n+1)/a(n+1). (End)

Extensions

Chebyshev comments from Wolfdieter Lang, Jan 10 2003

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

Original entry on oeis.org

0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, 154947584, 423324672, 1156544512, 3159738368, 8632565760, 23584608256, 64434348032, 176037912576, 480944521216, 1313964867584
Offset: 0

Views

Author

Colin Mallows

Keywords

Comments

Individually, both this sequence and A028859 are convergents to 1 + sqrt(3). Mutually, both sequences are convergents to 2 + sqrt(3) and 1 + sqrt(3)/2. - Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Nov 04 2001
The number of (s(0), s(1), ..., s(n+1)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| <= 1 for i = 1, 2, ..., n + 1, s(0) = 2, s(n+1) = 3. - Herbert Kociemba, Jun 02 2004
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the denominators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is sqrt(4). - Cino Hilliard, Sep 25 2005
The Hankel transform of this sequence is [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Nov 21 2007
[1, 3; 1, 1]^n *[1, 0] = [A026150(n), a(n)]. - Gary W. Adamson, Mar 21 2008
(1 + sqrt(3))^n = A026150(n) + a(n)*sqrt(3). - Gary W. Adamson, Mar 21 2008
a(n+1) is the number of ways to tile a board of length n using red and blue tiles of length one and two. - Geoffrey Critzer, Feb 07 2009
Starting with offset 1 = INVERT transform of the Jacobsthal sequence, A001045: (1, 1, 3, 5, 11, 21, ...). - Gary W. Adamson, May 12 2009
Starting with "1" = INVERTi transform of A007482: (1, 3, 11, 39, 139, ...). - Gary W. Adamson, Aug 06 2010
An elephant sequence, see A175654. For the corner squares four A[5] vectors, with decimal values 85, 277, 337 and 340, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A026150, without the first leading 1. - Johannes W. Meijer, Aug 15 2010
The sequence 0, 1, -2, 6, -16, 44, -120, 328, -896, ... (with alternating signs) is the Lucas U(-2,-2)-sequence. - R. J. Mathar, Jan 08 2013
a(n+1) counts n-walks (closed) on the graph G(1-vertex;1-loop,1-loop,2-loop,2-loop). - David Neil McGrath, Dec 11 2014
Number of binary strings of length 2*n - 2 in the regular language (00+11+0101+1010)*. - Jeffrey Shallit, Dec 14 2015
For n >= 1, a(n) equals the number of words of length n - 1 over {0, 1, 2, 3} in which 0 and 1 avoid runs of odd lengths. - Milan Janjic, Dec 17 2015
a(n+1) is the number of compositions of n into parts 1 and 2, both of two kinds. - Gregory L. Simay, Sep 20 2017
Number of associative, quasitrivial, and order-preserving binary operations on the n-element set {1, ..., n} that have neutral elements. - J. Devillet, Sep 28 2017
(1 + sqrt(3))^n = A026150(n) + a(n)*sqrt(3), for n >= 0; integers in the real quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 10 2018
Starting with 1, 2, 6, 16, ..., number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>3, 1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the third and fourth elements. - Sergey Kitaev, Dec 09 2020
a(n) is the number of tilings of a 2 X n board missing one corner cell, with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares). Compare to A127864. - Greg Dresden and Yilin Zhu, Jul 17 2025

References

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

Links

Crossrefs

First differences are given by A026150.
a(n) = A073387(n, 0), n>=0 (first column of triangle).
Equals (1/3) A083337. First differences of A077846. Pairwise sums of A028860 and abs(A077917).
a(n) = A028860(n)/2 apart from the initial terms.
Row sums of A081577 and row sums of triangle A156710.
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
Cf. A080953, A052948, A080040, A028859, A030195, A106435, A108898, A125145, A265106, A265107, A265278, A270810, A293005, A293006, A293007.
Cf. A175289 (Pisano periods).
Cf. A002530.
Cf. A127864.

Programs

  • Haskell
    a002605 n = a002605_list !! n
a002605_list =
   0 : 1 : map (* 2) (zipWith (+) a002605_list (tail a002605_list))
-- Reinhard Zumkeller, Oct 15 2011
  • Magma
    [Floor(((1 + Sqrt(3))^n - (1 - Sqrt(3))^n)/(2*Sqrt(3))): n in [0..30]]; // Vincenzo Librandi, Aug 18 2011
  • Magma
    [n le 2 select n-1 else 2*Self(n-1) + 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 07 2018
  • Maple
    a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+2*a[n-2]od: seq(a[n], n=0..33); # Zerinvary Lajos, Dec 15 2008
a := n -> `if`(n<3, n, 2^(n-1)*hypergeom([1-n/2, (1-n)/2], [1-n], -2));
seq(simplify(a(n)), n=0..29); # Peter Luschny, Dec 16 2015
  • Mathematica
    Expand[Table[((1 + Sqrt[3])^n - (1 - Sqrt[3])^n)/(2Sqrt[3]), {n, 0, 30}]] (* Artur Jasinski, Dec 10 2006 *)
a[n_]:=(MatrixPower[{{1,3},{1,1}},n].{{1},{1}})[[2,1]]; Table[a[n],{n,-1,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{2, 2}, {0, 1}, 30] (* Robert G. Wilson v, Apr 13 2013 *)
Round@Table[Fibonacci[n, Sqrt[2]] 2^((n - 1)/2), {n, 0, 20}] (* Vladimir Reshetnikov, Oct 15 2016 *)
nxt[{a_,b_}]:={b,2(a+b)}; NestList[nxt,{0,1},30][[All,1]] (* Harvey P. Dale, Sep 17 2022 *)
  • PARI
    Vec(x/(1-2*x-2*x^2)+O(x^99)) \\ Charles R Greathouse IV, Jun 10 2011
  • PARI
    A002605(n)=([2,2;1,0]^n)[2,1] \\ M. F. Hasler, Aug 06 2018
  • Sage
    [lucas_number1(n,2,-2) for n in range(0, 30)] # Zerinvary Lajos, Apr 22 2009
  • Sage
    a = BinaryRecurrenceSequence(2,2)
print([a(n) for n in (0..29)])  # Peter Luschny, Aug 29 2016

Formula

a(n) = (-I*sqrt(2))^(n-1)*U(n-1, I/sqrt(2)) where U(n, x) is the Chebyshev U-polynomial. - Wolfdieter Lang
G.f.: x/(1 - 2*x - 2*x^2).
From Paul Barry, Sep 17 2003: (Start)
E.g.f.: x*exp(x)*(sinh(sqrt(3)*x)/sqrt(3) + cosh(sqrt(3)*x)).
a(n) = (1 + sqrt(3))^(n-1)*(1/2 + sqrt(3)/6) + (1 - sqrt(3))^(n-1)*(1/2 - sqrt(3)/6), for n>0.
Binomial transform of 1, 1, 3, 3, 9, 9, ... Binomial transform is A079935. (End)
a(n) = Sum_{k=0..floor(n/2)} binomial(n - k, k)*2^(n - k). - Paul Barry, Jul 13 2004
a(n) = A080040(n) - A028860(n+1). - Creighton Dement, Jan 19 2005
a(n) = Sum_{k=0..n} A112899(n,k). - Philippe Deléham, Nov 21 2007
a(n) = Sum_{k=0..n} A063967(n,k). - Philippe Deléham, Nov 03 2006
a(n) = ((1 + sqrt(3))^n - (1 - sqrt(3))^n)/(2*sqrt(3)).
a(n) = Sum_{k=0..n} binomial(n, 2*k + 1) * 3^k.
Binomial transform of expansion of sinh(sqrt(3)x)/sqrt(3) (0, 1, 0, 3, 0, 9, ...). E.g.f.: exp(x)*sinh(sqrt(3)*x)/sqrt(3). - Paul Barry, May 09 2003
a(n) = (1/3)*Sum_{k=1..5} sin(Pi*k/2)*sin(2*Pi*k/3)*(1 + 2*cos(Pi*k/6))^n, n >= 1. - Herbert Kociemba, Jun 02 2004
a(n+1) = ((3 + sqrt(3))*(1 + sqrt(3))^n + (3 - sqrt(3))*(1 - sqrt(3))^n)/6. - Al Hakanson (hawkuu(AT)gmail.com), Jun 29 2009
Antidiagonals sums of A081577. - J. M. Bergot, Dec 15 2012
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 + 2*x)/(x*(4*k + 4 + 2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
a(n) = 2^(n - 1)*hypergeom([1 - n/2, (1 - n)/2], [1 - n], -2) for n >= 3. - Peter Luschny, Dec 16 2015
Sum_{k=0..n} a(k)*2^(n-k) = a(n+2)/2 - 2^n. - Greg Dresden, Feb 11 2022
a(n) = 2^floor(n/2) * A002530(n). - Gregory L. Simay, Sep 22 2022
From Peter Bala, May 08 2024: (Start)
G.f.: x/(1 - 2*x - 2*x^2) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (k + 2*x + 1)/(1 + k*x) )
Also x/(1 - 2*x - 2*x^2) = Sum_{n >= 0} (2*x)^n *( x*Product_{k = 1..n} (m*k + 2 - m + x)/(1 + 2*m*k*x) ) for arbitrary m (both series are telescoping). (End)
a(n) = A127864(n-1) + A127864(n-2). - Greg Dresden and Yilin Zhu, Jul 17 2025

Extensions

Edited by N. J. A. Sloane, Apr 15 2009

A001076 Denominators of continued fraction convergents to sqrt(5).

Original entry on oeis.org

0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020, 1762289, 7465176, 31622993, 133957148, 567451585, 2403763488, 10182505537, 43133785636, 182717648081, 774004377960, 3278735159921, 13888945017644, 58834515230497, 249227005939632, 1055742538989025
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(2*n+1) with b(2*n+1) := A001077(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation b^2 - 5*a^2 = -1, a(2*n) with b(2*n) := A001077(2*n), n >= 1, give all (positive integer) solutions to Pell equation b^2 - 5*a^2 = +1 (cf. Emerson reference).
Bisection: a(2*n+1) = T(2*n+1, sqrt(5))/sqrt(5) = A007805(n), n >= 0 and a(2*n) = 4*S(n-1,18), 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. S(n,18)=A049660(n+1). - Wolfdieter Lang, Jan 10 2003
Apart from initial terms, this is the Pisot sequence E(4,17), a(n) = floor(a(n-1)^2/a(n-2) + 1/2).
This is also the Horadam sequence (0,1,1,4), having the recurrence relation a(n) = s*a(n-1) + r*a(n-2); for n > 1, where a(0) = 0, a(1) = 1, s = 4, r = 1. a(n) / a(n-1) converges to 5^1/2 + 2 as n approaches infinity. 5^(1/2) + 2 can also be written as (2 * Phi) + 1 and Phi^2 + Phi. - Ross La Haye, Aug 18 2003
Numerators of continued fraction [4, 4, 4, ...], where the convergents to [4, 4, 4, ...] = (4/1, 17/4, 72/17, ...). Let X = the 2 X 2 matrix [0, 1; 1, 4]; then X^n = [a(n-1), a(n); a(n), a(n+1)]; e.g., X^3 = [4, 17; 17, 72]. Let C = the limit of a(n)/a(n-1) = 2 + sqrt(5) = 4.236067977...; then C^n = a(n+1) + (1/C)*a(n), where (1/C) = 0.236067977... . Example: C^3 = 76.01315556..., = 72 + 17*(0.2360679...). - Gary W. Adamson, Dec 15 2007, corrected by Greg Dresden, Sep 16 2019, corrected by Alex Mark, Jul 21 2020
Sqrt(5) = 4/2 + 4/17 + 4/(17*305) + 4/(305*5473) + 4/(5473*98209) + ... . - Gary W. Adamson, Dec 15 2007
a(p) == 20^((p-1)/2) (mod p) for odd primes p. - Gary W. Adamson, Feb 22 2009
a(n) = A167808(3*n). - Reinhard Zumkeller, Nov 12 2009
For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 4's along the main diagonal and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
Moreover, a(n) is the second binomial transform of (0,1,0,5,0,25,...) (see also A033887). This fact can be proved similarly like the proof of Paul Barry's remark in A033887 by using the following scaling identity for delta-Fibonacci numbers: y^n b(n;x/y) = Sum_{k=0..n} binomial(n,k) (y-1)^(n-k) b(k;x) and the fact that b(n;2) = (1-(-1)^n) 5^floor(n/2). - Roman Witula, Jul 12 2012
Binomial transform of 0, 1, 2, 8, 24, 80, 256, ... (A063727 with offset 1). - R. J. Mathar, Feb 05 2014
For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,...,4} avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015
With offset 1 is the INVERT transform of A006190: (1, 3, 10, 33, 109, 360, ...). - Gary W. Adamson, Jul 24 2015
From Rogério Serôdio, Mar 30 2018: (Start)
This is a divisibility sequence (i.e., if n|m then a(n)|a(m)).
gcd(a(n),a(n+k)) = a(gcd(n, k)) for all positive integers n and k. (End)
The initial 0 of this sequence is in contradiction with the fact that 0 is no valid denominator and according to all standard references, the first convergent of a continued fraction is p(0)/q(0) = b(0)/1 where b(0) is the first term of the continued fraction, given by the integer part of the number. One may artificially define q(-1) = 0 to have a recurrent relation q(n) = b(n)*q(n-1) + q(n-2), n >= 1, but then its index should be -1. - M. F. Hasler, Nov 01 2019
Number of 4-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
From Michael A. Allen, Feb 15 2023: (Start)
Also called the 4-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence.
a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are 4 kinds of squares available. (End)
a(n) is the smallest nonnegative integer that is the sum of n, but no fewer, Fibonacci numbers including negative-index Fibonacci numbers (A039834), with that sum being a(n) = Sum_{i=0..n-1} A000045(3*i+1). a(n) is also the smallest nonnegative integer that is the sum of n, but no fewer, terms each of which is either a Fibonacci number or the negative of a Fibonacci number. (See A027941 for negatives disallowed.) - Mike Speciner, Oct 08 2023
From Enrique Navarrete, Dec 16 2023: (Start)
a(n) is the number of compositions of n when there are P(k) sorts of parts k, with k,n > = 1, where P(k) = A006190(k) is the k-th 3-metallonacci number (see example below).
In general, the number of compositions with k-metallonacci number of parts is counted by the (k+1)-st metallonacci sequence (note k=1 and k=2 are the Fibonacci and the Pell numbers, respectively). (End).
a(n) is the number of tilings of a 2 X n rectangle missing the top right 1 X 1 cell, using 1 X 1 squares, dominoes and right trominoes. Compare to A110679 which is the same problem but without the missing top right cell. - Greg Dresden and Yilin Zhu, Jul 10 2025

Examples

			1 2 9 38 161 (A001077)
-,-,-,--,---, ...
0 1 4 17 72 (A001076)
G.f. = x + 4*x^2 + 17*x^3 + 72*x^4 + 305*x^5 + 1292*x^6 + 5473*x^7 + 23184*x^8 + ...
From _Enrique Navarrete_, Dec 16 2023: (Start)
From the comment on compositions with 3-metallonacci sorts of parts, A006190(k), there are A006190(1)=1 type of 1, A006190(2)=3 types of 2, A006190(3)=10 types of 3, A006190(4)=33 types of 4, A006190(5)=109 types of 5 and A006190(6)=360 types of 6. The following table gives the number of compositions of n=6:
Composition, number of such compositions, number of compositions of this type:
 6,              1,      360;
 5+1,            2,      218;
 4+2,            2,      198;
 3+3,            1,      100;
 4+1+1,          3,       99;
 3+2+1,          6,      180;
 2+2+2,          1,       27;
 3+1+1+1,        4,       40;
 2+2+1+1,        6,       54;
 2+1+1+1+1,      5,       15;
 1+1+1+1+1+1,    1,        1;
for a total of a(6)=1292 compositions of n=6. (End)

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 23.
  • S. Koshkin, Non-classical linear divisibility sequences ..., Fib. Q., 57 (No. 1, 2019), 68-80. See Table 1.
  • 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).
  • V. Thébault, Les Récréations Mathématiques. Gauthier-Villars, Paris, 1952, p. 282.

Links

Crossrefs

Row n=4 of A073133, A172236 and A352361.
Cf. A000045, A001077, A015448, A175183 (Pisano periods).
Cf. A049660, A007805, A110679.
Partial sums of A033887. First differences of A049652. Bisection of A059973.
Third column of array A028412.

Programs

  • GAP
    a:=[0,1];; for n in [3..30] do a[n]:=4*a[n-1]+a[n-2]; od; a; # Muniru A Asiru, Mar 31 2018
  • Magma
    I:=[0,1]; [n le 2 select I[n] else 4*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 24 2018
  • Maple
    A001076:=-1/(-1+4*z+z**2); # conjectured by Simon Plouffe in his 1992 dissertation
  • Mathematica
    Join[{0}, Denominator[Convergents[Sqrt[5], 30]]] (* Harvey P. Dale, Dec 10 2011 *)
a[ n_] := Fibonacci[3*n] / 2; (* Michael Somos, Feb 23 2014 *)
a[ n_] := ((2 + Sqrt[5])^n - (2 - Sqrt[5])^n) /(2 Sqrt[5]) // Simplify; (* Michael Somos, Feb 23 2014 *)
LinearRecurrence[{4, 1}, {0, 1}, 26] (* Jean-François Alcover, Sep 23 2017 *)
a[ n_] := Fibonacci[n, 4]; (* Michael Somos, Nov 02 2021 *)
  • Maxima
    a(n):=sum(4^(n-1-2*k)*binomial(n-k-1,n-2*k-1),k,0,floor((n)/2));/* Vladimir Kruchinin, Oct 02 2022 */
  • MuPAD
    numlib::fibonacci(3*n)/2 $ n = 0..30; // Zerinvary Lajos, May 09 2008
  • PARI
    {a(n) = fibonacci(3*n) / 2}; /* Michael Somos, Aug 11 2009 */
  • PARI
    {a(n) = imag( (2 + quadgen(20))^n )}; /* Michael Somos, Feb 23 2014 */
  • PARI
    {a(n) = polchebyshev(n-1, 2, 2*I)/I^(n-1)}; /* Michael Somos, Nov 02 2021 */
  • Sage
    [lucas_number1(n,4,-1) for n in range(23)] # Zerinvary Lajos, Apr 23 2009
  • Sage
    [fibonacci(3*n)/2 for n in range(23)] # Zerinvary Lajos, May 15 2009

Formula

a(n) = 4*a(n-1) + a(n-2), n > 1. a(0)=0, a(1)=1.
G.f.: x/(1 - 4*x - x^2).
a(n) = ((2+sqrt(5))^n - (2-sqrt(5))^n)/(2*sqrt(5)).
a(n) = A014445(n)/2 = F(3n)/2.
a(n) = ((-i)^(n-1))*S(n-1, 4*i), with i^2 = -1 and S(n, x) := U(n, x/2) Chebyshev's polynomials of the second kind. See A049310. S(-1, x) = 0.
a(n) = Sum_{i=0..n} Sum_{j=0..n} Fibonacci(i+j)*n!/(i!j!(n-i-j)!)/2. - Paul Barry, Feb 06 2004
E.g.f.: exp(2*x)*sinh(sqrt(5)*x)/sqrt(5). - Vladeta Jovovic, Sep 01 2004
a(n) = F(1) + F(4) + F(7) + ... + F(3n-2), for n > 0.
Conjecture: 2a(n+1) = a(n+2) - A001077(n+1). - Creighton Dement, Nov 28 2004
a(n) = Sum_{k=0..n} Sum_{j=0..n} C(n, j)*C(j, k)*F(j)/2. - Paul Barry, Feb 14 2005
a(n) = A048876(n) - A048875(n). - Creighton Dement, Mar 19 2005
Let M = {{0, 1}, {1, 4}}, v[1] = {0, 1}, v[n] = M.v[n - 1]; then a(n) = v[n][[1]]. - Roger L. Bagula, May 29 2005
a(n) = F(n, 4), the n-th Fibonacci polynomial evaluated at x=4. - T. D. Noe, Jan 19 2006
[A015448(n), a(n)] = [1,4; 1,3]^n * [1,0]. - Gary W. Adamson, Mar 21 2008
a(n) = (Sum_{k=0..n} Fibonacci(3*k-2)) + 1. - Gary Detlefs, Dec 26 2010
a(n) = (3*(-1)^n*F(n) + 5*F(n)^3)/2, n >= 0. See the general D. Jennings formula given in a comment on triangle A111125, where also the reference is given. Here the second (k=1) row [3,1] applies. - Wolfdieter Lang, Sep 01 2012
Sum_{k>=1} (-1)^(k-1)/(a(k)*a(k+1)) = (Sum_{k>=1} (-1)^(k-1)/(F_k*F_(k+1)))^3 = phi^(-3), where F_n is the n-th Fibonacci numbers (A000045) and phi is golden ratio (A001622). - Vladimir Shevelev, Feb 23 2013
G.f.: Q(0)*x/(2-4*x), where Q(k) = 1 + 1/(1 - x*(5*k-4)/(x*(5*k+1) - 2/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Oct 11 2013
a(-n) = -(-1)^n * a(n). - Michael Somos, Feb 23 2014
The o.g.f. A(x) = x/(1 - 4*x - x^2) satisfies A(x) + A(-x) + 8*A(x)*A(-x) = 0 or equivalently (1 + 8*A(x))*(1 + 8*A(-x)) = 1. The o.g.f. for A049660 equals -A(sqrt(x))*A(-sqrt(x)). - Peter Bala, Apr 02 2015
From Rogério Serôdio, Mar 30 2018: (Start)
Some properties:
(1) a(n)*a(n+1) = 4*Sum_{k=1..n} a(k)^2;
(2) a(n)^2 + a(n+1)^2 = a(2*n+1);
(3) a(n)^2 - a(n-2)^2 = 4*a(n-1)*(a(n) + a(n-2));
(4) a(m*(p+1)) = a(m*p)*a(m+1) + a(m*p-1)*a(m);
(5) a(n-k)*a(n+k) = a(n)^2 + (-1)^(n+k+1)*a(k)^2;
(6) a(n-1)*a(n+1) = a(n)^2 + (-1)^n (particular case of (5)!);
(7) a(2*n) = 2*a(n)*(2*a(n) + a(n-1));
(8) 3*Sum_{k=2..n+1} a(k)*a(k-1) is equal to a(n+1)^2 if n odd, and is equal to a(n+1)^2 - 1 if n is even;
(9) a(n) - a(n-2*k+1) = alpha(k)*a(n-2*k+1) + a(n-4*k+2), where alpha(k) = (2+sqrt(5))^(2*k-1) + (2-sqrt(5))^(2*k-1);
(10) 31|Sum_{k=n..n+9} a(k), for all positive n. (End)
O.g.f.: x*exp(Sum_{n >= 1} Lucas(3*n)*x^n/n) = x + 4*x^2 + 17*x^3 + .... - Peter Bala, Oct 11 2019
a(n) = Sum_{k=0..floor(n/2)} 4^(n-2*k-1)*C(n-k-1,n-2*k-1). - Vladimir Kruchinin, Oct 02 2022
a(n) = i^(n-1)*S(n-1, -4*i), with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. - Gary Detlefs and Wolfdieter Lang, Mar 06 2023
G.f.: x/(1 - 4*x - x^2) = Sum_{n >= 0} x^(n+1) * ( Product_{k = 1..n} (m*k + 4 - m + x)/(1 + m*k*x) ) for arbitrary m (a telescoping series). - Peter Bala, May 08 2024
a(n) = 4^(n-1)*hypergeom([(1-n)/2, 1-n/2], [1-n], -1/4) for n > 0. - Peter Luschny, Mar 30 2025
a(n) = a(n-1) + A110679(n-1) + A110679(n-2) = a(n-1) + Fibonacci(3*n-2). - Greg Dresden and Yilin Zhu, Jul 10 2025

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

Original entry on oeis.org

0, 1, 2, 7, 20, 61, 182, 547, 1640, 4921, 14762, 44287, 132860, 398581, 1195742, 3587227, 10761680, 32285041, 96855122, 290565367, 871696100, 2615088301, 7845264902, 23535794707, 70607384120, 211822152361, 635466457082
Offset: 0

Views

Author

Olivier Gérard

Keywords

Comments

Number of walks of length n between any two distinct vertices of the complete graph K_4. - Paul Barry and Emeric Deutsch, Apr 01 2004
For n >= 1, a(n) is the number of integers k, 1 <= k <= 3^(n-1), whose ternary representation ends in an even number of zeros (see A007417). - Philippe Deléham, Mar 31 2004
Form the digraph with matrix A=[0,1,1,1;1,0,1,1;1,1,0,1;1,0,1,1]. A015518(n) corresponds to the (1,3) term of A^n. - Paul Barry, Oct 02 2004
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the denominators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is 2. - Cino Hilliard, Sep 25 2005
(A046717(n))^2 + (2*a(n))^2 = A046717(2n). E.g., A046717(3) = 13, 2*a(3) = 14, A046717(6) = 365. 13^2 + 14^2 = 365. - Gary W. Adamson, Jun 17 2006
For n >= 2, number of ordered partitions of n-1 into parts of sizes 1 and 2 where there are two types of 1 (singletons) and three types of 2 (twins). For example, the number of possible configurations of families of n-1 male (M) and female (F) offspring considering only single births and twins, where the birth order of M/F/pair-of-twins is considered and there are three types of twins; namely, both F, both M, or one F and one M - where birth order within a pair of twins itself is disregarded. In particular, for a(3)=7, two children could be either: (1) F, then M; (2) M, then F; (3) F,F; (4) M,M; (5) F,F twins; (6) M,M twins; or (7) M,F twins (emphasizing that birth order is irrelevant here when both/all children are the same gender and when two children are within the same pair of twins). - Rick L. Shepherd, Sep 18 2004
a(n) is prime for n = {2, 3, 5, 7, 13, 23, 43, 281, 359, ...}, where only a(2) = 2 corresponds to a prime of the form (3^k - 1)/4. All prime terms, except a(2) = 2, are the primes of the form (3^k + 1)/4. Numbers k such that (3^k + 1)/4 is prime are listed in A007658. Note that all prime terms have prime indices. Prime terms are listed in A111010. - Alexander Adamchuk, Nov 19 2006
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-2, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n)=charpoly(A,1). - Milan Janjic, Jan 26 2010
Select an odd size subset S from {1,2,...,n}, then select an even size subset from S. - Geoffrey Critzer, Mar 02 2010
a(n) is the number of ternary sequences of length n where the numbers of (0's, 1's) are (even, odd) respectively, and, by symmetry, the number of such sequences where those numbers are (odd, even) respectively. A122983 covers (even, even), and A081251 covers (odd, odd). - Toby Gottfried, Apr 18 2010
An elephant sequence, see A175654. For the corner squares just one A[5] vector, with decimal value 341, leads to this sequence (without the leading 0). For the central square this vector leads to the companion sequence A046717 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010
Let R be the commutative algebra resulting from adjoining the elements of the Klein four-group to the integers (equivalently, K = Z[x,y,z]/{x*y - z, y*z - x, x*z - y, x^2 - 1, y^2 - 1, z^2 - 1}). Then a(n) is equal to the coefficients of x, y, and z in the expansion of (x + y + z)^n. - Joseph E. Cooper III (easonrevant(AT)gmail.com), Nov 06 2010
Pisano period lengths: 1, 2, 2, 4, 4, 2, 6, 8, 2, 4, 10, 4, 6, 6, 4, 16, 16, 2, 18, 4, ... - R. J. Mathar, Aug 10 2012
The ratio a(n+1)/a(n) converges to 3 as n approaches infinity. - Felix P. Muga II, Mar 09 2014
This is a divisibility sequence, also the values of Chebyshev polynomials, and also the number of ways of packing a 2 X n-1 rectangle with dominoes and unit squares. - R. K. Guy, Dec 16 2016
For n>0, gcd(a(n),a(n+1))=1. - Kengbo Lu, Jul 02 2020

References

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

Links

Crossrefs

a(n) = A080926(n-1) + 1 = (1/3)*A054878(n+1) = (1/3)*abs(A084567(n+1)).
First differences of A033113 and A039300.
Partial sums of A046717.
The following sequences (and others) belong to the same family: A000129, A001333, A002532, A002533, A002605, A015518, A015519, A026150, A046717, A063727, A083098, A083099, A083100, A084057.
Cf. A046717.
Cf. A007658, A111010.
Cf. A001045, A078008, A097073, A115341. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
Cf. A007482, A059260.

Programs

  • Magma
    [Round(3^n/4): n in [0..30]]; // Vincenzo Librandi, Jun 24 2011
  • Mathematica
    Table[(3^n-(-1)^n)/4,{n,0,30}] (* Alexander Adamchuk, Nov 19 2006 *)
  • Maxima
    a(n):= round(3^n/4)$ /* Dimitri Papadopoulos, Nov 28 2023 */
  • PARI
    a(n)=round(3^n/4)
  • Python
    for n in range(0, 20): print(int((3**n-(-1)**n)/4), end=', ') # Stefano Spezia, Nov 30 2018
  • Sage
    [round(3^n/4) for n in range(0,27)]

Formula

G.f.: x/((1+x)*(1-3*x)).
a(n) = (3^n - (-1)^n)/4 = floor(3^n/4 + 1/2).
a(n) = 3^(n-1) - a(n-1). - Emeric Deutsch, Apr 01 2004
E.g.f.: (exp(3*x) - exp(-x))/4. Second inverse binomial transform of (5^n-1)/4, A003463. Inverse binomial transform for powers of 4, A000302 (when preceded by 0). - Paul Barry, Mar 28 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2k+1)*2^(2k). - Paul Barry, May 14 2003
a(n) = Sum_{k=1..n} binomial(n, k)*(-1)^(n+k)*4^(k-1). - Paul Barry, Apr 02 2003
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*2^(n-2*k)*3^k. - Paul Barry, Jul 13 2004
a(n) = U(n-1, i/sqrt(3))(-i*sqrt(3))^(n-1), i^2=-1. - Paul Barry, Nov 17 2003
G.f.: x*(1+x)^2/(1 - 6*x^2 - 8*x^3 - 3*x^4) = x(1+x)^2/characteristic polynomial(x^4*adj(K_4)(1/x)). - Paul Barry, Feb 03 2004
a(n) = sum_{k=0..3^(n-1)} A014578(k) = -(-1)^n*A014983(n) = A051068(3^(n-1)), for n > 0. - Philippe Deléham, Mar 31 2004
E.g.f.: exp(x)*sinh(2*x)/2. - Paul Barry, Oct 02 2004
a(2*n+1) = A054880(n) + 1. - M. F. Hasler, Mar 20 2008
2*a(n) + (-1)^n = A046717(n). - M. F. Hasler, Mar 20 2008
a(n) = ((1+sqrt(4))^n - (1-sqrt(4))^n)/4. - Al Hakanson (hawkuu(AT)gmail.com), Dec 31 2008
a(n) = abs(A014983(n)). - Zerinvary Lajos, May 28 2009
a(n) = round(3^n/4). - Mircea Merca, Dec 28 2010
a(n) = Sum_{k=1,3,5,...} binomial(n,k)*2^(k-1). - Geoffrey Critzer, Mar 02 2010
From Sergei N. Gladkovskii, Jul 19 2012: (Start)
G.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - 1/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + 1/G(k+1)))))); (continued fraction).
E.g.f.: G(0)/4 where G(k)= 1 - 1/(9^k - 3*x*81^k/(3*x*9^k - (2*k+1)/(1 + 1/(3*9^k - 27*x*81^k/(9*x*9^k + (2*k+2)/G(k+1)))))); (continued fraction). (End)
G.f.: G(0)*x/(2*(1-x)), where G(k) = 1 + 1/(1 - x*(4*k-1)/(x*(4*k+3) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
a(n+1) = Sum_{k = 0..n} A238801(n,k)*2^k. - Philippe Deléham, Mar 07 2014
a(n) = (-1)^(n-1)*Sum_{k=0..n-1} A135278(n-1,k)*(-4)^k = (-1)^(n-1)*Sum_{k=0..n-1} (-3)^k. Equals (-1)^(n-1)*Phi(n,-3), where Phi is the cyclotomic polynomial when n is an odd prime. (For n > 0.) - Tom Copeland, Apr 14 2014
a(n) = 2*A006342(n-1) - n mod 2 if n > 0, a(0)=0. - Yuchun Ji, Nov 30 2018
a(n) = 2*A033113(n-2) + n mod 2 if n > 0, a(0)=0. - Yuchun Ji, Aug 16 2019
a(2*k) = 2*A002452(k), a(2*k+1) = A066443(k). - Yuchun Ji, Aug 14 2019
a(n+1) = 2*Sum_{k=0..n} a(k) if n odd, and 1 + 2*Sum_{k=0..n} a(k) if n even. - Kengbo Lu, May 30 2020
a(n) = F(n) + Sum_{k=1..(n-1)} a(k)*L(n-k), for F(n) and L(n) the Fibonacci and Lucas numbers. - Kengbo Lu and Greg Dresden, Jun 05 2020
From Kengbo Lu, Jun 11 2020: (Start)
a(n) = A002605(n) + Sum_{k = 1..n-2} a(k)*A002605(n-k-1).
a(n) = A006130(n-1) + Sum_{k = 1..n-1} a(k)*A006130(n-k-1). (End)
a(2n) = Sum_{i>=0, j>=0} binomial(n-j-1,i)*binomial(n-i-1,j)* 2^(2n-2i-2j-1)* 3^(i+j). - Kengbo Lu, Jul 02 2020
a(n) = 3*a(n-1) - (-1)^n. - Dimitri Papadopoulos, Nov 28 2023
G.f.: x/((1 + x)*(1 - 3*x)) = Sum_{n >= 0} x^(n+1) * Product_{k = 1..n} (k + 3*x + 1)(1 + k*x) (a telescoping series). Cf. A007482. - Peter Bala, May 08 2024
From Peter Bala, Jun 29 2025: (Start)
For n >= 1, a(n+1) = 2^n * hypergeom([1/2 - (1/2)*n, -(1/2)*n], [-n], -3).
G.f. A(x) = x*exp(Sum_{n >= 1} a(2*n)/a(n)*x^n/n) = x + 2*x^2 + 7*x^3 + 20*x^4 + ....
sqrt(A(x)/x) is the g.f. of A002426.
The following series telescope:
Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)) = -1; Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)*a(n+2)*a(n+3)) = -1/98.
In general, for k >= 0, Sum_{n >= 1} (-3)^n/(a(n)*a(n+1)*...*a(n+2*k+1)) = -1/((a(1)*a(2)*...*a(2*k+1))*a(2*k+1)).
Sum_{n >= 1} 3^n/(a(n)*a(n+1)*a(n+2)) = 1/4; Sum_{n >= 1} 3^n/(a(n)*a(n+1)*a(n+2)* a(n+3)*a(n+4)) = 1/5600.
In general, for k >= 1, Sum_{n >= 1} 3^n/(a(n)*a(n+1)*...*a(n+2*k)) = 1/((a(1)*a(2)*...*a(2*k))*a(2*k)). (End)

Extensions

More terms from Emeric Deutsch, Apr 01 2004
Edited by Ralf Stephan, Aug 30 2004

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

Original entry on oeis.org

1, 1, 5, 13, 41, 121, 365, 1093, 3281, 9841, 29525, 88573, 265721, 797161, 2391485, 7174453, 21523361, 64570081, 193710245, 581130733, 1743392201, 5230176601, 15690529805, 47071589413, 141214768241, 423644304721, 1270932914165, 3812798742493, 11438396227481
Offset: 0

Views

Author

Gervais Deroo and M. Deroo

Keywords

Comments

Form the digraph with matrix A = [0,1,1,1; 1,0,1,1; 1,1,0,1; 1,0,1,1]. Then the sequence 0,1,1,5,... or (3^(n-1)-(-1)^n)/2+0^n/3 with g.f. x(1-x)/(1-2x-3x^2) corresponds to the (1,2) term of A^n. - Paul Barry, Oct 02 2004
3*a(n+1) + a(n) = 4*A060925(n); a(n+1) = A015518(n) + A060925(n); a(n+1) - 6*A015518(n) = (-1)^n. - Creighton Dement, Nov 15 2004
The sequence corresponds to the (1,1) term of the matrix [1,2;2,1]^n. - Simone Severini, Dec 04 2004
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is 2. - Cino Hilliard, Sep 25 2005
a(n)^2 + (2*A015518(n))^2 = a(2n). E.g., a(3) = 13, 2*A015518(3) = 14, A046717(6) = 365. 13^2 + 14^2 = 365. - Gary W. Adamson, Jun 17 2006
Equals INVERTi transform of A104934: (1, 2, 8, 28, 100, 356, 1268, ...). - Gary W. Adamson, Jul 21 2010
a(n) is the number of compositions of n when there are 1 type of 1 and 4 types of other natural numbers. - Milan Janjic, Aug 13 2010
An elephant sequence, see A175655. For the central square just one A[5] vector, with decimal value 341, leads to this sequence (without the first leading 1). For the corner squares this vector leads to the companion sequence A015518 (without the leading 0). - Johannes W. Meijer, Aug 15 2010
Pisano period lengths: 1, 1, 2, 1, 4, 2, 6, 4, 2, 4, 10, 2, 6, 6, 4, 8, 16, 2, 18, 4, ... - R. J. Mathar, Aug 10 2012
a(n) is the number of words of length n over a ternary alphabet whose position in the lexicographic order is a multiple of two. - Alois P. Heinz, Apr 13 2022
a(n) is the sum, for k=0..3, of the number of walks of length n between two vertices at distance k of the cube graph. - Miquel A. Fiol, Mar 09 2024

References

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

Links

Crossrefs

The first difference sequence of A015518.
Row sums of triangle A080928.
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. A015518.
Cf. A104934. - Gary W. Adamson, Jul 21 2010

Programs

  • Magma
    [n le 2 select 1 else 2*Self(n-1)+3*Self(n-2): n in [1..35]]; // Vincenzo Librandi, Jul 21 2013
  • Magma
    [(3^n + (-1)^n)/2: n in [0..30]]; // G. C. Greubel, Jan 07 2018
  • Maple
    a[0]:=1:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2] od: seq(a[n], n=0..33); # Zerinvary Lajos, Dec 14 2008
seq(denom(((-2)^(2*n)+6^(2*n))/((-2)^n+6^n)),n=0..26)
  • Mathematica
    Table[(3^n + (-1)^n)/2, {n, 0, 30}] (* Artur Jasinski, Dec 10 2006 *)
CoefficientList[ Series[(1 - x)/(1 - 2x - 3x^2), {x, 0, 30}], x]  (* Robert G. Wilson v, Apr 04 2011 *)
Table[ MatrixPower[{{1, 2}, {1, 1}}, n][[1, 1]], {n, 0, 30}] (* Robert G. Wilson v, Apr 04 2011 *)
  • PARI
    {a(n) = (3^n+(-1)^n)/2};
for(n=0,30, print1(a(n), ", ")) /* modified by G. C. Greubel, Jan 07 2018 */
  • PARI
    x='x+O('x^30); Vec((1-x)/((1+x)*(1-3*x))) \\ G. C. Greubel, Jan 07 2018
  • Sage
    [lucas_number2(n,2,-3)/2 for n in range(0, 27)] # Zerinvary Lajos, Apr 30 2009

Formula

G.f.: (1-x)/((1+x)*(1-3*x)).
a(n) = (3^n + (-1)^n)/2.
a(n) = Sum_{k=0..n} binomial(n, 2k)2^(2k). - Paul Barry, Feb 26 2003
Binomial transform of A000302 (powers of 4) with interpolated zeros. Inverse binomial transform of A081294. - Paul Barry, Mar 17 2003
E.g.f.: exp(x)cosh(2x). - Paul Barry, Mar 17 2003
a(n) = ceiling(3^n/4) + floor(3^n/4) = ceiling(3^n/4)^2 - floor(3^n/4)^2. - Paul Barry, Jan 17 2005
a(n) = Sum_{k=0..n} Sum_{j=0..n} C(n,j)C(n-j,k)*(1+(-1)^(j-k))/2. - Paul Barry, May 21 2006
a(n) = Sum_{k=0..n} A098158(n,k)*4^(n-k). - Philippe Deléham, Dec 26 2007
a(n) = (3^n + (-1)^n)/2. - M. F. Hasler, Mar 20 2008
a(n) = 2 A015518(n) + (-1)^n; for n > 0, a(n) = A080925(n). - M. F. Hasler, Mar 20 2008
((1 + sqrt4)^n + (1 - sqrt4)^n)/2. The offset is 0. a(3)=13. - Al Hakanson (hawkuu(AT)gmail.com), Nov 22 2008
If p[1]=1 and p[i]=4 (i > 1), and if A is 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, Apr 29 2010
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(4*k-1)/(x*(4*k+3) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
G.f.: G(0)/2, where G(k) = 1 + (-1)^k/(3^k - 3*9^k*x/(3*3^k*x + (-1)^k/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Oct 17 2013

Extensions

Description corrected by and more terms from Michael Somos

A026150 a(0) = a(1) = 1; a(n+2) = 2*a(n+1) + 2*a(n).

Original entry on oeis.org

1, 1, 4, 10, 28, 76, 208, 568, 1552, 4240, 11584, 31648, 86464, 236224, 645376, 1763200, 4817152, 13160704, 35955712, 98232832, 268377088, 733219840, 2003193856, 5472827392, 14952042496, 40849739776
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n+1)/A002605(n) converges to sqrt(3). - Mario Catalani (mario.catalani(AT)unito.it), Apr 22 2003
a(n+1)/a(n) converges to 1 + sqrt(3) = 2.732050807568877293.... - Philippe Deléham, Jul 03 2005
Binomial transform of expansion of cosh(sqrt(3)x) (A000244 with interpolated zeros); inverse binomial transform of A001075. - Philippe Deléham, Jul 04 2005
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 3 times the bottom to get the new top. The limit of the sequence of fractions is sqrt(3). - Cino Hilliard, Sep 25 2005
Inverse binomial transform of A001075: (1, 2, 7, 26, 97, 362, ...). - Gary W. Adamson, Nov 23 2007
Starting (1, 4, 10, 28, 76, ...), the sequence is the binomial transform of [1, 3, 3, 9, 9, 27, 27, 81, 81, ...], and inverse binomial transform of A001834: (1, 5, 19, 71, 265, ...). - Gary W. Adamson, Nov 30 2007
[1, 3; 1, 1]^n * [1,0] = [a(n), A002605(n)]. - Gary W. Adamson, Mar 21 2008
(1 + sqrt(3))^n = a(n) + A002605(n)*(sqrt(3)). - Gary W. Adamson, Mar 21 2008
Equals right border of triangle A143908. Also, starting (1, 4, 10, 28, ...) = row sums of triangle A143908 and INVERT transform of (1, 3, 3, 3, ...). - Gary W. Adamson, Sep 06 2008
a(n) is the number of compositions of n when there are 1 type of 1 and 3 types of other natural numbers. - Milan Janjic, Aug 13 2010
An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 85, 277, 337 and 340, lead to this sequence (without the first leading 1). For the corner squares these vectors lead to the companion sequence A002605 (without the leading 0). - Johannes W. Meijer, Aug 15 2010
Pisano period lengths: 1, 1, 1, 1, 24, 1, 48, 1, 3, 24, 10, 1, 12, 48, 24, 1,144, 3,180, 24, ... - R. J. Mathar, Aug 10 2012
(1 + sqrt(3))^n = a(n) + A002605(n)*sqrt(3), for n >= 0; integers in the real quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 10 2018
a(n) is also the number of solutions for cyclic three-dimensional stable matching instances with master preference lists of size n (Escamocher and O'Sullivan 2018). - Guillaume Escamocher, Jun 15 2018
Starting from a(1), first differences of A005665. - Ivan N. Ianakiev, Nov 22 2019
Number of 3-permutations of n elements avoiding the patterns 231, 312. See Bonichon and Sun. - Michel Marcus, Aug 19 2022

Examples

			G.f. = 1 + x + 4*x^2 + 10*x^3 + 28*x^4 + 76*x^5 + 208*x^6 + 568*x^7 + ...

References

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

Links

Crossrefs

First differences of A002605.
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. A001075, A001834, A083337, A002605, A143908, A028859, A030195, A106435, A108898, A125145, A053120.

Programs

  • Haskell
    a026150 n = a026150_list !! n
a026150_list = 1 : 1 : map (* 2) (zipWith (+) a026150_list (tail
a026150_list))
-- Reinhard Zumkeller, Oct 15 2011
  • Magma
    [n le 2 select 1 else 2*Self(n-1) + 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 07 2018
  • Maple
    with(combstruct):ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), a):ZL1:=Prod(begin_blockP, Z, end_blockP):ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL2,ZL2,ZL2), b=ZL1], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n)/3, n=2..27); # Zerinvary Lajos, Mar 08 2008
  • Mathematica
    Expand[Table[((1 + Sqrt[3])^n + (1 - Sqrt[3])^n)/(2), {n, 0, 30}]] (* Artur Jasinski, Dec 10 2006 *)
LinearRecurrence[{2, 2}, {1, 1}, 30] (* T. D. Noe, Mar 25 2011 *)
Round@Table[LucasL[n, Sqrt[2]] 2^(n/2 - 1), {n, 0, 20}] (* Vladimir Reshetnikov, Oct 15 2016 *)
  • Maxima
    a(n) := if n<=1 then 1 else 2*a(n-1)+2*a(n-2);
makelist(a(n),n,0,20); /* Emanuele Munarini, Apr 14 2017 */
  • PARI
    {a(n) = if( n<0, 0, real((1 + quadgen(12))^n))};
  • Sage
    from sage.combinat.sloane_functions import recur_gen2; it = recur_gen2(1,1,2,2); [next(it) for i in range(30)] # Zerinvary Lajos, Jun 25 2008
  • Sage
    [lucas_number2(n,2,-2)/2 for n in range(0, 26)] # Zerinvary Lajos, Apr 30 2009

Formula

a(n) = (1/2)*((1 + sqrt(3))^n + (1 - sqrt(3))^n). - Benoit Cloitre, Oct 28 2002
G.f.: (1 - x)/(1 - 2*x - 2*x^2).
a(n) = a(n-1) + A083337(n-1). A083337(n)/a(n) converges to sqrt(3). - Mario Catalani (mario.catalani(AT)unito.it), Apr 29 2003
From Paul Barry, May 15 2003: (Start)
a(n) = Sum_{k=0..floor(n/2)} C(n, 2k)*3^k;
E.g.f.: exp(x)*cosh(sqrt(3)x). (End)
a(n) = Sum_{k=0..n} A098158(n,k)*3^(n - k). - Philippe Deléham, Dec 26 2007
a(n) = upper left and lower right terms of [1, 1; 3, 1]^n. (1 + sqrt(3))^n = a(n) + A083337(n)/(sqrt(3)). - Gary W. Adamson, Mar 12 2008
a(n) = A080040(n)/2. - Philippe Deléham, Nov 19 2008
If p[1] = 1, and p[i] = 3, (i > 1), and if A is 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, Apr 29 2010
a(n) = 2 * A052945(n-1). - Vladimir Joseph Stephan Orlovsky, Mar 24 2011
a(n) = round((1 + sqrt(3))^n/2) for n > 0. - Bruno Berselli, Feb 04 2013
G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x*(3*k - 1)/(x*(3*k + 2) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 25 2013
a(n) = (-sqrt(2)*i)^n*T(n,sqrt(2)*i/2), with i = sqrt(-1) and the Chebyshev T-polynomials (A053120). - Wolfdieter Lang, Feb 10 2018

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

Original entry on oeis.org

1, 1, 5, 9, 29, 65, 181, 441, 1165, 2929, 7589, 19305, 49661, 126881, 325525, 833049, 2135149, 5467345, 14007941, 35877321, 91909085, 235418369, 603054709, 1544728185, 3956947021, 10135859761, 25963647845, 66507086889, 170361678269
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Length-n words with letters {0,1,2,3,4} where no two consecutive letters are nonzero, see fxtbook link below. - Joerg Arndt, Apr 08 2011
Equals INVERTi transform of A063727: (1, 2, 8, 24, 80, 256, 832, ...). - Gary W. Adamson, Aug 12 2010
a(n) is equal to the permanent of the n X n Hessenberg matrix with 1's along the main diagonal, 2's along the superdiagonal and the subdiagonal, and 0's everywhere else. - John M. Campbell, Jun 09 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n >= 2, 5*a(n-2) equals the number of 5-colored compositions of n with all parts >= 2, such that no adjacent parts have the same color. - Milan Janjic, Nov 26 2011
Pisano period lengths: 1, 1, 8, 1, 6, 8, 48, 2, 24, 6,120, 8, 12, 48, 24, 4,136, 24, 18, 6, ... - R. J. Mathar, Aug 10 2012
This is one of only two Lucas-type sequences whose 8th term is a square. The other one is A097705. - Michel Marcus, Dec 07 2012
Numerators of stationary probabilities for the M2/M/1 queue. In this queue, customers arrives in groups of 2. Intensity of arrival = 1. Service rate = 4. There is only one server and an infinite queue. - Igor Kleiner, Nov 02 2018
Number of 4-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
From M. Eren Kesim, May 13 2021: (Start)
a(n) is equal to the number of n-step walks from a universal vertex to another (itself or the other) on the diamond graph. It is also equal to the number of (n+1)-step walks from vertex A to vertex B on the graph below.
B--C
| /|
|/ |
A--D
(End)
From Wolfdieter Lang, Jan 03 2024: (Start)
This sequence {a(n-1)}, with a(-1) = 0, appears in the formula for powers of phi17 := (1 + sqrt(17))/2 = A222132, the fundamental (integer) algebraic number of Q(sqrt(17)): phi17^n = A052923(n) + a(n-1)*phi17, for n >= 0.
Limit_{n->oo} a(n+1)/a(n) = phi17. (End)

Examples

			G.f. = 1 + x + 5*x^2 + 9*x^3 + 29*x^4 + 65*x^5 + 181*x^6 + 441*x^7 + 1165*x^8 + ...

References

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

Links

Crossrefs

Cf. A006130, A015440, A026581, A026583, A026597, A026599, A052923, A097705, A102446, A063727, A344236, A344261.

Programs

  • GAP
    a:=[1,1];; for n in [3..30] do a[n]:=a[n-1]+4*a[n-2]; od; a; # G. C. Greubel, Dec 26 2019
  • Magma
    [ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+4*Self(n-2): n in [1..40] ]; // Vincenzo Librandi, Aug 19 2011
  • Maple
    A006131:=-1/(-1+z+4*z**2); # conjectured by Simon Plouffe in his 1992 dissertation
seq( simplify((2/I)^n*ChebyshevU(n, I/4)), n=0..30); # G. C. Greubel, Dec 26 2019
  • Mathematica
    m = 16; f[n_] = Product[(1 + m*Cos[k*Pi/n]^2), {k, 1, Floor[(n - 1)/2]}]; Table[FullSimplify[ExpandAll[f[n]]], {n, 0, 15}]; N[%] (* Roger L. Bagula, Nov 21 2008 *)
a[n_]:=(MatrixPower[{{1,4},{1,0}},n].{{1},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{1, 4}, {1, 1}, 29] (* Jean-François Alcover, Sep 25 2017 *)
Table[2^n*Fibonacci[n+1, 1/2], {n,0,30}] (* G. C. Greubel, Dec 26 2019 *)
  • PARI
    a(n)=([0,1; 4,1]^n*[1;1])[1,1] \\ Charles R Greathouse IV, Oct 03 2016
  • PARI
    vector(31, n, (2/I)^(n-1)*polchebyshev(n-1, 2, I/4) ) \\ G. C. Greubel, Dec 26 2019
  • Python
    def A006131_list(n):
    list = [1, 1] + [0] * (n - 2)
    for i in range(2, n):
        list[i] = list[i - 1] + 4 * list[i - 2]
    return list
print(A006131_list(29)) # M. Eren Kesim, Jul 19 2021
  • Sage
    [lucas_number1(n,1,-4) for n in range(1, 30)] # Zerinvary Lajos, Apr 22 2009

Formula

G.f.: 1/(1 - x - 4*x^2).
a(n) = (((1+sqrt(17))/2)^(n+1) - ((1-sqrt(17))/2)^(n+1))/sqrt(17).
a(n+1) = Sum_{k=0..ceiling(n/2)} 4^k*binomial(n-k, k). - Benoit Cloitre, Mar 06 2004
a(n) = Sum_{k=0..n} binomial((n+k)/2, (n-k)/2)*(1+(-1)^(n-k))*2^(n-k)/2. - Paul Barry, Aug 28 2005
a(n) = A102446(n)/2. - Zerinvary Lajos, Jul 09 2008
a(n) = Sum_{k=0..n} A109466(n,k)*(-4)^(n-k). - Philippe Deléham, Oct 26 2008
a(n) = Product_{k=1..floor((n - 1)/2)} (1 + 16*cos(k*Pi/n)^2). - Roger L. Bagula, Nov 21 2008
Limiting ratio a(n+1)/a(n) is (1 + sqrt(17))/2 = 2.561552812... - Roger L. Bagula, Nov 21 2008
The fraction b(n) = a(n)/2^n satisfies b(n) = 1/2 b(n-1) + b(n-2); g.f. 1/(1-x/2-x^2); b(n) = (( (1+sqrt(17))/4 )^(n+1) - ( (1-sqrt(17))/4 )^(n+1))*2/sqrt(17). - Franklin T. Adams-Watters, Nov 30 2009
G.f.: G(0)/(2-x), where G(k) = 1 + 1/(1 - x*(17*k-1)/(x*(17*k+16) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 20 2013
G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + 4*x)/( x*(4*k+3 + 4*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 09 2013
G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(k+1 + 4*x)/( x*(k+3/2 + 4*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 14 2013
G.f.: 1 / (1 - x / (1 - 4*x / (1 + 4*x))). - Michael Somos, Sep 15 2013
a(n) = (Sum_{1<=k<=n+1, k odd} C(n+1,k)*17^((k-1)/2))/2^n. - Vladimir Shevelev, Feb 05 2014
a(n) = 2^n*Fibonacci(n+1, 1/2) = (2/i)^n*ChebyshevU(n, i/4). - G. C. Greubel, Dec 26 2019
E.g.f.: exp(x/2)*(sqrt(17)*cosh(sqrt(17)*x/2) + sinh(sqrt(17)*x/2))/sqrt(17). - Stefano Spezia, Dec 27 2019
a(n) = A344236(n) + A344261(n). - M. Eren Kesim, May 13 2021
With an initial 0 prepended, the sequence [0, 1, 1, 5, 9, 29, 65, ...] satisfies the congruences a(n*p^k) == e*a(n*p^(k-1)) (mod p^k) for positive integers k and n and all primes p, where e = +1 for the primes p listed in A296938, e = 0 when p = 17, otherwise e = -1. - Peter Bala, Dec 28 2022
a(n) = A052923(n+2)/4. - Wolfdieter Lang, Jan 03 2024
From Peter Bala, Jun 27 2025: (Start)
The following products telescope:
Product_{k >= 0} (1 + 4^k/a(2*k+1)) = 1 + sqrt(17).
Product_{k >= 1} (1 - 4^k/a(2*k+1)) = 1/18 * (1 + sqrt(17)).
Product_{k >= 0} (1 + (-4)^k/a(2*k+1)) = (1/17) * (17 + sqrt(17)).
Product_{k >= 1} (1 - (-4)^k/a(2*k+1)) = (1/18) * (17 + sqrt(17)). (End)

Extensions

More terms from Roger L. Bagula, Sep 26 2006

A033887 a(n) = Fibonacci(3*n + 1).

Original entry on oeis.org

1, 3, 13, 55, 233, 987, 4181, 17711, 75025, 317811, 1346269, 5702887, 24157817, 102334155, 433494437, 1836311903, 7778742049, 32951280099, 139583862445, 591286729879, 2504730781961, 10610209857723, 44945570212853, 190392490709135, 806515533049393, 3416454622906707
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Binomial transform of A063727, and second binomial transform of (1,1,5,5,25,25,...), which is A074872 with offset 0. - Paul Barry, Jul 16 2003
Equals INVERT transform of A104934: (1, 2, 8, 28, 100, 356, ...) and INVERTi transform of A005054: (1, 4, 20, 100, 500, ...). - Gary W. Adamson, Jul 22 2010
a(n) is the number of compositions of n when there are 3 types of 1 and 4 types of other natural numbers. - Milan Janjic, Aug 13 2010
F(3*n+1) = 3^n*a(n;2/3), where a(n;d), n = 0, 1, ..., d, denote the delta-Fibonacci numbers defined in comments to A000045 (see also the papers by Witula et al.). - Roman Witula, Jul 12 2012
We note that the remark above by Paul Barry can be easily obtained from the following scaling identity for delta-Fibonacci numbers y^n a(n;x/y) = Sum_{k=0..n} binomial(n,k) (y-1)^(n-k) a(k;x) and the fact that a(n;2)=5^floor(n/2). Indeed, for x=y=2 we get 2^n a(n;1) = Sum_{k=0..n} binomial(n,k) a(k;2) and, by A000045: Sum_{k=0..n} binomial(n,k) 2^k a(k;1) = Sum_{k=0..n} binomial(n,k) F(k+1) 2^k = 3^n a(n;2/3) = F(3n+1). - Roman Witula, Jul 12 2012
Except for the first term, this sequence can be generated by Corollary 1 (iv) of Azarian's paper in the references for this sequence. - Mohammad K. Azarian, Jul 02 2015
Number of 1’s in the substitution system {0 -> 110, 1 -> 11100} at step n from initial string "1" (1 -> 11100 -> 111001110011100110110 -> ...). - Ilya Gutkovskiy, Apr 10 2017
The o.g.f. of {F(m*n + 1)}A000045%20and%20L%20=%20A000032.%20-%20_Wolfdieter%20Lang">{n>=0}, for m = 1, 2, ..., is G(m,x) = (1 - F(m-1)*x) / (1 - L(m)*x + (-1)^m*x^2), with F = A000045 and L = A000032. - _Wolfdieter Lang, Feb 06 2023

Examples

			a(5) = Fibonacci(3*5 + 1) = Fibonacci(16) = 987. - _Indranil Ghosh_, Feb 04 2017

Links

Crossrefs

Cf. A000032, A000045, A104934, A005054, A063727 (inverse binomial transform), A082761 (binomial transform), A001076, A001077.
Cf. A016777, A049310, A049651, A074872, A122070, A167808, A185384.

Programs

Formula

a(n) = A001076(n) + A001077(n) = A001076(n+1) - A001076(n).
a(n) = 2*A049651(n) + 1.
a(n) = 4*a(n-1) + a(n-2) for n>1, a(0)=1, a(1)=3;
G.f.: (1 - x)/(1 - 4*x - x^2).
a(n) = ((1 + sqrt(5))*(2 + sqrt(5))^n - (1 - sqrt(5))*(2 - sqrt(5))^n)/(2*sqrt(5)).
a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(n,j)*C(n-j,k)*F(n-j+1). - Paul Barry, May 19 2006
First differences of A001076. - Al Hakanson (hawkuu(AT)gmail.com), May 02 2009
a(n) = A167808(3*n+1). - Reinhard Zumkeller, Nov 12 2009
a(n) = Sum_{k=0..n} C(n,k)*F(n+k+1). - Paul Barry, Apr 19 2010
Let p[1]=3, p[i]=4, (i>1), and A be a 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, Apr 29 2010
a(n) = Sum_{i=0..n} C(n,n-i)*A063727(i). - Seiichi Kirikami, Mar 06 2012
a(n) = Sum_{k=0..n} A122070(n,k) = Sum_{k=0..n} A185384(n,k). - Philippe Deléham, Mar 13 2012
a(n) = A000045(A016777(n)). - Michel Marcus, Dec 10 2015
a(n) = F(2*n)*L(n+1) + F(n-1)*(-1)^n for n > 0. - J. M. Bergot, Feb 09 2016
a(n) = Sum_{k=0..n} binomial(n,k)*5^floor(k/2)*2^(n-k). - Tony Foster III, Sep 03 2017
2*a(n) = Fibonacci(3*n) + Lucas(3*n). - Bruno Berselli, Oct 13 2017
a(n)^2 is the denominator of continued fraction [4,...,4, 2, 4,...,4], which has n 4's before, and n 4's after, the middle 2. - Greg Dresden and Hexuan Wang, Aug 30 2021
a(n) = i^n*(S(n, -4*i) + i*S(n-1, -4*i)), with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. From the simplified trisection formula. See the first entry above with A001076. - Gary Detlefs and Wolfdieter Lang, Mar 06 2023
E.g.f.: exp(2*x)*(5*cosh(sqrt(5)*x) + sqrt(5)*sinh(sqrt(5)*x))/5. - Stefano Spezia, May 24 2024

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

Original entry on oeis.org

1, 1, 6, 16, 56, 176, 576, 1856, 6016, 19456, 62976, 203776, 659456, 2134016, 6905856, 22347776, 72318976, 234029056, 757334016, 2450784256, 7930904576, 25664946176, 83053510656, 268766806016, 869747654656, 2814562533376, 9108115685376, 29474481504256
Offset: 0

Views

Author

Paul Barry, May 10 2003

Keywords

Comments

Inverse binomial transform of A001077. Binomial transform of expansion of cosh(sqrt(5)*x) (1,0,5,0,25,...).
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 5 times the bottom to get the new top. The limit of the sequence of fractions is sqrt(5). - Cino Hilliard, Sep 25 2005
Numerators of fractions in the approximation of the square root of 5 satisfying: a(n) = (a(n-1)+c)/(a(n-1)+1), with c=5 and a(1)=1. For denominators see A063727. - Mark Dols, Jul 24 2009
Equals right border of triangle A143969. (1, 6, 16, 56, ...) = row sums of triangle A143969 and INVERT transform of (1, 5, 5, 5, ...). - Gary W. Adamson, Sep 06 2008
a(n) is the number of compositions of n when there are 1 type of 1 and 5 types of other natural numbers. - Milan Janjic, Aug 13 2010
From Gary W. Adamson, Jul 30 2016: (Start)
The sequence is case N=1 in an infinite set obtained by taking powers of the 2 X 2 matrix M = [(1,5); (1,N)], then extracting the upper left terms. The infinite set begins:
N=1 (A084057): 1, 6, 16, 56, 176, 576, 1856, ...
N=2 (A108306): 1, 6, 21, 81, 306, 1161, 4401, ...
N=3 (A164549): 1, 6, 26, 116, 516, 2296, 10216, ...
N=4 (A015449): 1, 6, 31, 161, 836, 4341, 22541, ...
N=5 (A000400): 1, 6, 36, 216, 1296, 7776, 46656, ...
N=6 (A049685): 1, 6, 41, 281, 1926, 13201, 90481, ...
N=7 (.......): 1, 6, 46, 356, 2756, 21336, 222712, ...
...
Sequences in the above set can be obtained by taking INVERT transforms of the following:
N=1 INVERT transform of (1, 5, 5, 5, 5, 5, ...
N=2 ..."......"......". (1, 5, 10, 20, 40, 80, ...
N=3 ..."......"......". (1, 5, 15, 45, 135, 405, ...
N=4 ..."......"......". (1, 5, 20, 80, 320, 1280, ...
...
with the pattern (1, 5, N*5, (N^2)*5, (N^3)*5, ...
It appears that the sequence generated from powers (n>0) of the matrix P = [(1,a); (1,b)], (a,b > 0), then extracting the upper left terms, is equal to the INVERT transform of the sequence starting: (1, a, b*a, (b^2)*a, (b^3)*a, ...). (End)

References

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

Links

Crossrefs

Cf. A046717, A002533, A098158, A143969, A269992.
a(n) = A087131(n)/2.
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. A108306, A164549, A015449, A000400, A049685

Programs

  • Magma
    I:=[1,1]; [n le 2 select I[n] else 2*Self(n-1)+4*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Jul 31 2016
  • Mathematica
    f[n_] := Simplify[((1 + Sqrt[5])^n + (1 - Sqrt[5])^n)/2]; Array[f, 28, 0] (* Or *)
LinearRecurrence[{2, 4}, {1, 1}, 28] (* Robert G. Wilson v, Sep 18 2013 *)
RecurrenceTable[{a[1] == 1, a[2] == 1, a[n] == 2 a[n-1] + 4 a[n-2]}, a, {n, 30}] (* Vincenzo Librandi, Jul 31 2016 *)
Table[2^(n-1) LucasL[n], {n, 0, 20}] (* Vladimir Reshetnikov, Sep 19 2016 *)
  • PARI
    lucas(n)=fibonacci(n-1)+fibonacci(n+1)
a(n)=lucas(n)/2*2^n \\ Charles R Greathouse IV, Sep 18 2013
  • Sage
    from sage.combinat.sloane_functions import recur_gen2b; it = recur_gen2b(1,1,2,4, lambda n: 0); [next(it) for i in range(1,26)] # Zerinvary Lajos, Jul 09 2008
  • Sage
    [lucas_number2(n,2,-4)/2 for n in range(0, 26)] # Zerinvary Lajos, Apr 30 2009

Formula

a(n) = ((1+sqrt(5))^n + (1-sqrt(5))^n)/2.
G.f.: (1-x) / (1-2*x-4*x^2).
E.g.f.: exp(x) * cosh(sqrt(5)*x).
a(2n+1) = 2*a(n)*a(n+1) - (-4)^n. - Mario Catalani (mario.catalani(AT)unito.it), Jun 13 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2*k)*5^k . - Paul Barry, Jul 25 2004
a(n) = Sum_{k=0..n} A098158(n,k)*5^(n-k). - Philippe Deléham, Dec 26 2007
a(n) = 2^(n-1)*A000032(n). - Mark Dols, Jul 24 2009
If p(1)=1, and p(i)=5 for i>1, and if A is the Hessenberg matrix of order n defined by: A(i,j) = p(j-i+1) for 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, Apr 29 2010
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(5*k-1)/(x*(5*k+4) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
a(n) = A063727(n) - A063272(n-1). - R. J. Mathar, Jun 06 2019
a(n) = 1 + 5*A014335(n). - R. J. Mathar, Jun 06 2019
Sum_{n>=1} 1/a(n) = A269992. - Amiram Eldar, Feb 01 2021
Showing 1-10 of 49 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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