A005668 -id:A005668 - cp's OEIS frontend

A175185 Pisano period of the 6-Fibonacci numbers A005668.

1, 2, 2, 4, 20, 2, 16, 8, 6, 20, 24, 4, 6, 16, 20, 16, 36, 6, 8, 20, 16, 24, 48, 8, 100, 6, 18, 16, 60, 20, 30, 32, 24, 36, 80, 12, 12, 8, 6, 40, 40, 16, 42, 24, 60, 48, 96, 16, 112, 100, 36, 12, 26, 18, 120, 16, 8, 60, 40, 20, 124, 30, 48, 64, 60, 24, 22, 36, 48, 80, 70, 24, 148

Offset: 1

R. J. Mathar, Mar 01 2010

Period of the sequence defined by reading A005668 modulo n.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Sergio Falcon and Ángel Plaza, k-Fibonacci sequences modulo m, Chaos, Solit. Fractals 41 (2009), 497-504.
Eric Weisstein's World of Mathematics, Pisano period.
Wikipedia, Pisano period.

Cf. A001175, A005668, A175181, A175182, A175183, A175184.

F := proc(k,n) option remember; if n <= 1 then n; else k*procname(k,n-1)+procname(k,n-2) ; end if; end proc:
Pper := proc(k,m) local cha, zer,n,fmodm ; cha := [] ; zer := [] ; for n from 0 do fmodm := F(k,n) mod m ; cha := [op(cha),fmodm] ; if fmodm = 0 then zer := [op(zer),n] ; end if; if nops(zer) = 5 then break; end if; end do ; if [op(1..zer[2],cha) ] = [ op(zer[2]+1..zer[3],cha) ] and [op(1..zer[2],cha)] = [ op(zer[3]+1..zer[4],cha) ] and [op(1..zer[2],cha)] = [ op(zer[4]+1..zer[5],cha) ] then return zer[2] ; elif [op(1..zer[3],cha) ] = [ op(zer[3]+1..zer[5],cha) ] then return zer[3] ; else return zer[5] ; end if; end proc:
k := 6 ; seq( Pper(k,m),m=1..80) ;

Table[s = t = Mod[{0, 1}, n]; cnt = 1; While[tmp = Mod[6*t[[2]] + t[[1]], n]; t[[1]] = t[[2]]; t[[2]] = tmp; s!= t, cnt++]; cnt, {n, 100}] (* Vincenzo Librandi, Dec 20 2012, after T. D. Noe *)

A099366 Squares of A005668.

Original entry on oeis.org

0, 1, 36, 1369, 51984, 1974025, 74960964, 2846542609, 108093658176, 4104712468081, 155870980128900, 5918992532430121, 224765845252215696, 8535183127051766329, 324112192982714904804, 12307728150216114616225

Offset: 0

Wolfdieter Lang, Oct 18 2004

See the comment in A099279. This is example a=6.

a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using half-squares (1/2 X 1 pieces, always placed so that the shorter sides are horizontal) and (1/2,1/2)-fences if there are 6 kinds of half-squares available. A (w,g)-fence is a tile composed of two w X 1 pieces separated horizontally by a gap of width g. a(n+1) also equals the number of tilings of an n-board using (1/4,1/4)-fences and (1/4,3/4)-fences if there are 6 kinds of (1/4,1/4)-fences available. - Michael A. Allen, Apr 21 2023

Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.
Sergio Falcon, Some series of reciprocal k-Fibonacci numbers, Asian Journal of Mathematics and Computer Research, Vol. 11, No. 3 (2016), pp. 184-191; ResearchGate link.
Index entries for linear recurrences with constant coefficients, signature (37,37,-1).
Index entries for sequences related to Chebyshev polynomials.

Cf. other squares of k-metallonacci numbers (for k=1 to 10): A007598, A079291, A092936, A099279, A099365, this sequence, A099367, A099369, A099372, A099374.

with (combinat):seq(fibonacci(n,6)^2,n=0..15); # Zerinvary Lajos, Apr 09 2008

LinearRecurrence[{37,37,-1},{0,1,36},20] (* Harvey P. Dale, Sep 23 2018 *)

a(n) = A005668(n)^2.
a(n) = 37*a(n-1) + 37*a(n-2) - a(n-3), n >= 3; a(0)=0, a(1)=1, a(2)=36.
a(n) = 38*a(n-1) - a(n-2) - 2*(-1)^n, n >= 2; a(0)=0, a(1)=1.
a(n) = (T(n, 19) - (-1)^n)/20 with the Chebyshev polynomials of the first kind: T(n, 19) = A078986(n).
G.f.: x*(1-x)/((1 - 38*x + x^2)*(1+x)) = x*(1-x)/(1 - 37*x - 37*x^2 + x^3).
a(n) = (1 - (-1)^n)/2 + 36*Sum_{r=1..n-1} r*a(n-r). - Michael A. Allen, Apr 21 2023
Product_{n>=2} (1 + (-1)^n/a(n)) = (3 + sqrt(10))/6 (Falcon, 2016, p. 189, eq. (3.1)). - Amiram Eldar, Dec 03 2024

A338080 Odd composite integers such that A005668(m)^2 == 1 (mod m).

Original entry on oeis.org

9, 57, 63, 143, 171, 247, 323, 399, 407, 481, 629, 703, 721, 779, 899, 927, 1121, 1239, 1407, 1441, 1463, 1703, 1729, 2419, 2529, 2639, 2737, 3289, 3367, 3689, 4081, 4847, 4879, 4921, 5291, 5339, 5871, 6061, 6479, 6489, 6601, 6721, 6989, 7067, 7471, 7859, 8401, 8911, 8987, 9139, 9361

Offset: 1

Ovidiu Bagdasar, Oct 08 2020

nonn

The generalized Lucas sequence of integer parameters (a,b) is defined by
U(m+2) = a*U(m+1)-b*U(m) and U(0)=0, U(1)=1.
Whenever p is prime and b=-1,1 we have U^2(p) == 1 (mod p).
Here we define the odd composite integers for which U^2(m) == 1 (mod m) holds, for a=6, b=-1, where U(m) is A005668(m).

D. Andrica, O. Bagdasar, Recurrent Sequences: Key Results, Applications and Problems. Springer, 2020.
D. Andrica, O. Bagdasar, On some new arithmetic properties of the generalized Lucas sequences, Mediterr. J. Math. (to appear, 2021)

Cf. A337231 (a=1, odd terms), A337232 (a=1, even terms), A337233 (a=2), A337234 (a=3, odd terms), A337235 (a=3, even terms), A337236 (a=4), A337237 (a=5).

Select[Range[3, 15000, 2], CompositeQ[#] && Divisible[Fibonacci[#, 6]*Fibonacci[#, 6] - 1, #] &]

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

N. J. A. Sloane

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

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

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.

Simone Sandri, Table of n, a(n) for n = 0..1000 (first 500 terms from N. J. A. Sloane)
M. Abrate, S. Barbero, U. Cerruti, and N. Murru, Construction and composition of rooted trees via descent functions, Algebra, Volume 2013 (2013), Article ID 543913, 11 pages.
Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.
Paraskevas K. Alvanos and Konstantinos A. Draziotis, Integer Solutions of the Equation y^2 = Ax^4 + B, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.4.
Ayoub B. Ayoub, Fibonacci-like sequences and Pell equations, The College Mathematics Journal, Vol. 38 (2007), pp. 49-53.
Ovidiu Bagdasar, Eve Hedderwick, and Ioan-Lucian Popa, On the ratios and geometric boundaries of complex Horadam sequences, Electronic Notes in Discrete Mathematics (2018) Vol. 67, 63-70.
Aseem R. Baranwal and Jeffrey Shallit, Critical exponent of infinite balanced words via the Pell number system, arXiv:1902.00503 [cs.FL], 2019.
Elena Barcucci, Antonio Bernini, and Renzo Pinzani, A Gray code for a regular language, Semantic Sensor Networks Workshop 2018, CEUR Workshop Proceedings (2018) Vol. 2113.
Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Motzkin paths with a restricted first return decomposition, Integers (2019) Vol. 19, A46.
M. Barnabei, F. Bonetti, and M. Silimbani, Two permutation classes related to the Bubble Sort operator, Electronic Journal of Combinatorics 19(3) (2012), #P25.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 20, 29.
Sarah-Marie Belcastro, Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces, J. Integer Seq. 26 (2023), Article 23.5.6.
J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7.
Latham Boyle and Paul J. Steinhardt, Self-Similar One-Dimensional Quasilattices, arXiv preprint arXiv:1608.08220 [math-ph], 2016.
B. Bradie, Extensions and Refinements of some properties of sums involving Pell Numbers, Miss. J. Math. Sci 22 (1) (2010) 37-43.
Jhon J. Bravo, Jose L. Herrera, and José L. Ramírez, Combinatorial Interpretation of Generalized Pell Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.2.1.
Dorota Bród, On a New One Parameter Generalization of Pell Numbers, Annales Mathematicae Silesianae 33 (2019), 66-76.
Steve Butler, Jason Ekstrand, and Steven Osborne, Counting Tilings by Taking Walks in a Graph, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 165.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Geoffrey B. Campbell and Aleksander Zujev, Gaussian integer solutions for the fifth power taxicab number problem, arXiv:1511.07424 [math.NT], 2015.
Frédéric Chapoton, A note on gamma triangles and local gamma vectors, arXiv:1809.00575 [math.CO], 2018.
C. O. Chow, S. M. Ma, T. Mansour, and M. Shattuck, Counting permutations by cyclic peaks and valleys, Annales Mathematicae et Informaticae, (2014), Vol. 43, pp. 43-54.
Hongshen Chua, A Study of Second-Order Linear Recurrence Sequences via Continuants, J. Int. Seq. (2023) Vol. 26, Art. 23.8.8.
M. Couceiro, J. Devillet, and J.-L. Marichal, Quasitrivial semigroups: characterizations and enumerations, arXiv:1709.09162 [math.RA], 2017.
Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, Exhaustive generation for permutations avoiding a (colored) regular sets of patterns, arXiv:1809.00742 [cs.DM], 2018.
C. M. da Fonseca, Unifying some Pell and Fibonacci identities, Applied Mathematics and Computation, Volume 236, Jun 01 2014, Pages 41-42.
Mahadi Ddamulira, On the x-coordinates of Pell equations which are products of two Pell numbers, arXiv:1906.06330 [math.NT], 2019.
E. Deutsch, A formula for the Pell numbers, Problem 10663, Amer. Math. Monthly 107 (No. 4, 2000), solutions pp. 370-371.
Antonio J. Di Scala, Nadir Murru, and Carlo Sanna, Lucas pseudoprimes and the Pell conic, arXiv:2001.00353 [math.NT], 2020.
E. S. Egge and T. Mansour, 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers, arXiv:math/0205206 [math.CO], 2002.
Shalosh B. Ekhad and Tewodros Amdeberhan, Solution to problem #10663 (AMM).
C. Elsner, On Error Sums for Square Roots of Positive Integers with Applications to Lucas and Pell Numbers, J. Int. Seq. 17 (2014) # 14.4.4.
E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242, Ex. 1, pp. 237-238.
Sergio Falcón, Relationships between Some k-Fibonacci Sequences, Applied Mathematics, 2014, 5, 2226-2234.
Sergio Falcón, Generating Function of Some k-Fibonacci and k-Lucas Sequences, International Journal of Innovation in Science and Mathematics (2019) Vol. 7, Issue 2, 2347-9051.
Sergio Falcón, Binomial Transform of the Generalized k-Fibonacci Numbers, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.
Bakir Farhi, Summation of Certain Infinite Lucas-Related Series, J. Int. Seq., Vol. 22 (2019), Article 19.1.6.
M. C. Firengiz and A. Dil, Generalized Euler-Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
Felix Flicker, Time quasilattices in dissipative dynamical systems, arXiv:1707.09371 [nlin.CD], 2017. Also SciPost Phys. 5, 001 (2018).
Robert Frontczak and Taras Goy, Mersenne-Horadam identities using generating functions, Carpathian Math. Publ. (2020) Vol. 12, No. 1, 34-45.
Shaun Giberson and Thomas J. Osler, Extending Theon's Ladder to Any Square Root, College Mathematics Journal, May, 2004.
Juan B. Gil and Aaron Worley, Generalized metallic means, arXiv:1901.02619 [math.NT], 2019.
Taras Goy, Pell numbers identities from Toeplitz-Hessenberg determinants, Novi Sad J. Math., 49 (2) (2019), 87-94.
Martin Griffiths, Pell identities via a quadratic field, International Journal of Mathematical Education in Science and Technology, 2013.
R. P. Grimaldi, Tilings, Compositions, and Generalizations, J. Int. Seq. 13 (2010), 10.6.5.
M. A. Gruber, Artemas Martin, A. H. Bell, J. H. Drummond, A. H. Holmes and H. C. Wilkes, Problem 47, Amer. Math. Monthly, 4 (1897), 25-28.
Tian-Xiao He, Peter J.-S. Shiue, Zihan Nie, and Minghao Chen, Recursive sequences and Girard-Waring identities with applications in sequence transformation, Electronic Research Archive (2020) Vol. 28, No. 2, 1049-1062.
R. J. Hetherington, Letter to N. J. A. Sloane, Oct 26 1974
Gábor Hetyei, The type B permutohedron and the poset of intervals as a Tchebyshev transform, University of North Carolina-Charlotte (2019).
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Nick Hobson, Python program for this sequence
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
A. F. Horadam, Special Properties of the Sequence W(n){a,b; p,q}, Fib. Quart., Vol. 5, No. 5 (1967), pp. 424-434.
A. F. Horadam, Pell Identities, Fib. Quart., Vol. 9, No. 3, 1971, pp. 245-252, 263.
Haruo Hosoya, What Can Mathematical Chemistry Contribute to the Development of Mathematics?, HYLE--International Journal for Philosophy of Chemistry, Vol. 19, No.1 (2013), pp. 87-105.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 135
Milan Janjić, On Linear Recurrence Equations Arising from Compositions of Positive Integers, J. Int. Seq. 18 (2015), #15.4.7.
Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.
Tanya Khovanova, Recursive Sequences.
Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.
C. J. Kirchen, Letter to N. J. A. Sloane, Feb 11 1974.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16.
K. Kuhapatanakul, On the Sums of Reciprocal Generalized Fibonacci Numbers, J. Int. Seq. 16 (2013) #13.7.1.
Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, and Fausto Jarquín-Zárate, The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d)), arXiv:1904.13002 [math.NT], 2019.
Shirley Law, Hopf Algebra of Sashes, in FPSAC 2014, Chicago, USA; Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, 2014, 621-632.
H. Li and T. MacHenry, Permanents and Determinants, Weighted Isobaric Polynomials, and Integer Sequences, J. Int. Seq. 16 (2013) #13.3.5, example 46.
Édouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article Théorie des Fonctions Numériques Simplement Périodiques, I, Amer. J. Math., 1 (1878), 184-240.
T. Mansour and M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
A. Moghaddamfar and H. Tajbakhsh, More Determinant Representations for Sequences, Journal of Integer Sequences, 17 (2014), #14.5.6.
Sophie Morier-Genoud and Valentin Ovsienko, q-deformed rationals and q-continued fractions, arXiv:1812.00170 [math.CO], 2018-2020.
Sophie Morier-Genoud and Valentin Ovsienko, q-deformed rationals and q-continued fractions, (2019) [math].
Emanuele Munarini, A generalization of André-Jeannin's symmetric identity, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 98-118.
Mariana Nagy, Simon R. Cowell, and Valeriu Beiu, Survey of Cubic Fibonacci Identities - When Cuboids Carry Weight, arXiv:1902.05944 [math.HO], 2019.
Ahmet Öteleş, Bipartite Graphs Associated with Pell, Mersenne and Perrin Numbers, An. Şt. Univ. Ovidius Constantą, (2019) Vol. 27, Issue 2, 109-120.
Ahmet Öteleş, Zekeriya Y. Karata, and Diyar O. Mustafa Zangana, Jacobsthal Numbers and Associated Hessenberg Matrices, J. Int. Seq., 21 (2018), #18.2.5.
Arzu Özkoç, Some algebraic identities on quadra Fibona-Pell integer sequence, Advances in Difference Equations, 2015, 2015:148.
Hao Pan, Arithmetic properties of q-Fibonacci numbers and q-Pell numbers, Discr. Math., 306 (2006), 2118-2127.
D. Panario, M. Sahin, and Q. Wang, A family of Fibonacci-like conditional sequences, INTEGERS, Vol. 13, 2013, #A78.
Simon Plouffe, Approximations de Séries Génératrices et Quelques Conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Raul Prisacariu, Generating k-Pell Infinite Series Using Whittaker's Formula, The Mathematics Enthusiast: Vol. 15 : No. 3, Article 7, 2018.
C. Raissi and J. Pei, Towards Bounding Sequential Patterns, KDD'11, Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011.
Franck Ramaharo, An approximate Jerusalem square whose side equals a Pell number, arXiv:1801.00466 [math.CO], 2018.
José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368 [cs.DM], 2012-2014.
John Riordan and N. J. A. Sloane, Correspondence, 1974.
Michelle Rudolph-Lilith, On the Product Representation of Number Sequences, with Application to the Fibonacci Family, arXiv preprint arXiv:1508.07894 [math.NT], 2015.
J. L. Schiffman, Exploring the Fibonacci sequence of order two with CAS technology, Electronic Proceedings of the Twenty-fourth Annual International Conference on Technology in Collegiate Mathematics, Orlando, Florida, March 22-25, 2012, Paper C027.
Jon E. Schoenfield, Prime factorization of a(n) for n = 1..630. (a(422) corrected by Amiram Eldar)
James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2.
Mark Shattuck, Tiling proofs of some formulas for the Pell numbers of odd index, Integers, 9 (2009), 53-64.
Mark Shattuck, Combinatorial Proofs of Some Formulas for Triangular Tilings, Journal of Integer Sequences, 17 (2014), #14.5.5.
Joseph M. Shunia, Polynomial Quotient Rings and Kronecker Substitution for Deriving Combinatorial Identities, arXiv preprint arXiv:2404.00332 [math.GM], 2024.
Nanci Smith, Problem B-82 An Integer Valued Function, Fib. Quart., 4 (1966), 374-375.
Yüksel Soykan, On Generalized Third-Order Pell Numbers, Asian Journal of Advanced Research and Reports (2019) Vol. 6, No. 1, Article No. AJARR.51635, 1-18.
Yüksel Soykan, On Summing Formulas For Generalized Fibonacci and Gaussian Generalized Fibonacci Numbers, Advances in Research (2019) Vol. 20, No. 2, 1-15, Article No. AIR.51824.
Yüksel Soykan, On generalized sixth-order Pell sequences, Journal of Scientific Perspectives (2020) Vol. 4, No. 1, 49-70.
Yüksel Soykan, Generalized Fibonacci Numbers: Sum Formulas, Journal of Advances in Mathematics and Computer Science (2020) Vol. 35, No. 1, 89-104.
Yüksel Soykan, Closed Formulas for the Sums of Squares of Generalized Fibonacci Numbers, Asian Journal of Advanced Research and Reports (2020) Vol. 9, No. 1, 23-39, Article no. AJARR.55441.
Yüksel Soykan, Closed Formulas for the Sums of Cubes of Generalized Fibonacci Numbers: Closed Formulas of Sum_{k=0..n} W_k^3 and Sum_{k=1..n} W_(-k)^3, Archives of Current Research International (2020) Vol. 20, Issue 2, 58-69.
Yüksel Soykan, A Study on Generalized Fibonacci Numbers: Sum Formulas Sum_{k=0..n} k * x^k * W_k^3 and Sum_{k=1..n} k * x^k W_-k^3 for the Cubes of Terms, Earthline Journal of Mathematical Sciences (2020) Vol. 4, No. 2, 297-331.
Yüksel Soykan, Mehmet Gümüş, and Melih Göcen, A Study On Dual Hyperbolic Generalized Pell Numbers, Malaya Journal of Matematik, vol. 9, no. 03, July 2021, pp. 99-116.
Robin James Spivey, Close encounters of the golden and silver ratios, Notes on Number Theory and Discrete Mathematics (2019) Vol. 25, No. 3, 170-184.
R. A. Sulanke, Moments, Narayana numbers and the cut and paste for lattice paths
Ping Sun, Enumeration of standard Young tableaux of shifted strips with constant width, arXiv:1506.07256 [math.CO], 24 Jun 2015.
Tamas Szakacs, Convolution of second order linear recursive sequences I, Ann. Math. Inform. 46 (2016), 205-216.
Wipawee Tangjai, A Non-standard Ternary Representation of Integers, Thai J. Math (2020) Special Issue: Annual Meeting in Mathematics 2019, 269-283.
Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 63).
A. Tekcan, M. Tayat, and M. E. Ozbek, The diophantine equation 8x^2-y^2+8x(1+t)+(2t+1)^2=0 and t-balancing numbers, ISRN Combinatorics, Volume 2014, Article ID 897834, 5 pages.
P. E. Trier, "Almost Isosceles" Right-Angled Triangles, Eureka, No. 4, May 1940, pp. 9 - 11.
Andrew Vince, The average size of a connected vertex set of a graph-explicit formulas and open problems, University of Florida (2019).
Ian Walker, Explorations in Recursion with John Pell and the Pell Sequence.
Kai Wang, On k-Fibonacci Sequences And Infinite Series List of Results and Examples, 2020.
Eric Weisstein's World of Mathematics, Centipede Graph.
Eric Weisstein's World of Mathematics, Independent Edge Set.
Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Pell Number.
Eric Weisstein's World of Mathematics, Pell Polynomial.
Eric Weisstein's World of Mathematics, Pythagoras's Constant.
Eric Weisstein's World of Mathematics, Square Root.
Eric Weisstein's World of Mathematics, Square Triangular Number.
Meral Yasar and Durmus Bozkurt, Another proof of Pell identities by using the determinant of tridiagonal matrix, Appl. Math. Comput., 218 (2012), pp. 6067-6071.
Leon Zaporski and Felix Flicker, Superconvergence of Topological Entropy in the Symbolic Dynamics of Substitution Sequences, arXiv:1811.00331 [nlin.CD], 2018.
Abdelmoumène Zekiri, Farid Bencherif, and Rachid Boumahdi, Generalization of an Identity of Apostol, J. Int. Seq., Vol. 21 (2018), Article 18.5.1.
Jianqiang Zhao, Finite Multiple zeta Values and Finite Euler Sums, arXiv preprint arXiv:1507.04917 [math.NT], 2015.
Index entries for "core" sequences.
Index entries for sequences related to Chebyshev polynomials.
Index to divisibility sequences.
Index entries for linear recurrences with constant coefficients, signature (2,1).

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

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

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

[0] cat [n le 2 select n else 2*Self(n-1) + Self(n-2): n in [1..35]]; // Vincenzo Librandi, Aug 08 2015

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

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

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 */

makelist((%i)^(n-1)*ultraspherical(n-1,1,-%i),n,0,24),expand; /* Emanuele Munarini, Mar 07 2018 */

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

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

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

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

{a(n) = polchebyshev(n-1, 2, I) / I^(n-1)}; /* Michael Somos, Oct 30 2021 */

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

[lucas_number1(n, 2, -1) for n in range(30)]  # Zerinvary Lajos, Apr 22 2009

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

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

Original entry on oeis.org

0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, 2003229469, 6616217487, 21851881930, 72171863277, 238367471761, 787274278560, 2600190307441, 8587845200883, 28363725910090

Offset: 0

N. J. A. Sloane

Denominators of continued fraction convergents to (3+sqrt(13))/2. - Benoit Cloitre, Jun 14 2003
a(n) and A006497(n) occur in pairs: (a,b): (1,3), (3,11), (10,36), (33,119), (109,393), ... such that b^2 - 13a^2 = 4(-1)^n. - Gary W. Adamson, Jun 15 2003
Form the 4-node graph with matrix A = [1,1,1,1; 1,1,1,0; 1,1,0,1; 1,0,1,1]. Then this sequence counts the walks of length n from the vertex with degree 5 to one (any) of the other vertices. - Paul Barry, Oct 02 2004
a(n+1) is the binomial transform of A006138. - Paul Barry, May 21 2006
a(n+1) is the diagonal sum of the exponential Riordan array (exp(3x),x). - Paul Barry, Jun 03 2006
Number of paths in the right half-plane from (0,0) to the line x=n-1, consisting of steps U=(1,1), D=(1,-1), h=(1,0) and H=(2,0). Example: a(3)=10 because we have hh, H, UD, DU, hU, Uh, UU, hD, Dh and DD. - Emeric Deutsch, Sep 03 2007
Equals INVERT transform of A000129. Example: a(5) = 109 = (29, 12, 5, 2, 1) dot (1, 1, 3, 10, 33) = (29 + 12 + 15 + 20 + 33). - Gary W. Adamson, Aug 06 2010
For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 3's along the main diagonal, 1's along the superdiagonal and subdiagonal, and 0's everywhere else. - John M. Campbell, Jul 08 2011
These numbers could also be called "bronze Fibonacci numbers". Indeed, 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; analogously, for Pell numbers (A000129), or "silver Fibonacci numbers", P(n+1) = ceiling(delta*a(n)), if n is even and P(n+1) = floor(delta*a(n)), if n is odd, where delta = delta_S = 1 + sqrt(2) is the silver ratio. Here, for n >= 1, we have a(n+1) = ceiling(c*a(n)), if n is even and a(n+1) = floor(c*a(n)), if n is odd, where c = (3 + sqrt(13))/2 is the bronze ratio (cf. comment in A098316). - Vladimir Shevelev, Feb 23 2013
Let p(n,x) denote the Fibonacci polynomial, defined by p(1,x) = 1, p(2,x) = x, p(n,x) = x*p(n-1,x) + p(n-2,x). Let q(n,x) be the numerator polynomial of the rational function p(n, x + 1 + 1/x). Then q(n,1) = a(n). - Clark Kimberling, Nov 04 2013
The (1,1)-entry of the matrix A^n where A = [0,1,0; 1,2,1; 1,1,2]. - David Neil McGrath, Jul 18 2014
a(n+1) counts closed walks on K2, containing three 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,3). - David Neil McGrath, Oct 29 2014
For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,2,3} avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015
With offset 1 is the INVERTi transform of A001076. - Gary W. Adamson, Jul 24 2015
Apart from the initial 0, this is the p-INVERT transform of (1,0,1,0,1,0,...) for p(S) = 1 - 3 S. See A291219. - Clark Kimberling, Sep 02 2017
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)
Numbers of straight-chain fatty acids involving oxo and/or hydroxy groups, if cis-/trans isomerism and stereoisomerism are neglected. - Stefan Schuster, Apr 04 2018
Number of 3-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
From Michael A. Allen, Jan 25 2023: (Start)
Also called the 3-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 3 kinds of squares available. (End)
a(n) is the number of compositions of n when there are P(k) sorts of parts k, with k,n >= 1, P(k) = A000129(k) is the k-th Pell number (see example below). - Enrique Navarrete, Dec 15 2023

			From _Enrique Navarrete_, Dec 15 2023: (Start)
From the comment on compositions with Pell number of parts, A000129(k), there are A000129(1)=1 type of 1, A000129(2)=2 types of 2, A000129(3)=5 types of 3, A000129(4)=12 types of 4, A000129(5)=29 types of 5 and A000129(6)=70 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,     70;
  5+1,            2,     58;
  4+2,            2,     48;
  3+3,            1,     25;
  4+1+1,          3,     36;
  3+2+1,          6,     60;
  2+2+2,          1,      8;
  3+1+1+1,        4,     20;
  2+2+1+1,        6,     24;
  2+1+1+1+1,      5,     10;
  1+1+1+1+1+1,    1,      1;
for a total of a(6)=360 compositions of n=6. (End).

H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 128.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
L.-N. Machaut, Query 3436, L'Intermédiaire des Mathématiciens, 16 (1909), 62-63. - N. J. A. Sloane, Mar 08 2022

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.
Dorin Andrica, Ovidiu Bagdasar, and George Cătălin Tųrcąs, On some new results for the generalised Lucas sequences, An. Şt. Univ. Ovidius Constanţa (Romania, 2021) Vol. 29, No. 1, 17-36.
Ayoub B. Ayoub, Fibonacci-like sequences and Pell equations, The College Mathematics Journal, Vol. 38 (2007), pp. 49-53.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 8, 29.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 8.
Henrique F. da Cruz, Ilda Inácio, and Rogério Serôdio, Convertible subspaces that arise from different numberings of the vertices of a graph, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 473-486.
Colin Defant, Meeting Covered Elements in nu-Tamari Lattices, arXiv:2104.03890 [math.CO], 2021.
Sergio Falcon, On The Generating Functions of the Powers of the K-Fibonacci Numbers, Scholars Journal of Engineering and Technology (SJET), 2014; 2 (4C):669-675.
Sergio Falcon, The k-Fibonacci difference sequences, Chaos, Solitons & Fractals, Volume 87, June 2016, Pages 153-157.
M. C. Firengiz and A. Dil, Generalized Euler-Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
Juan B. Gil and Aaron Worley, Generalized metallic means, arXiv:1901.02619 [math.NT], 2019.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
A. F. Horadam, Generating identities for generalized Fibonacci and Lucas triples, Fib. Quart., 15 (1977), 289-292.
Haruo Hosoya, What Can Mathematical Chemistry Contribute to the Development of Mathematics?, HYLE--International Journal for Philosophy of Chemistry, Vol. 19, No.1 (2013), pp. 87-105.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 158
Milan Janjić, Hessenberg Matrices and Integer Sequences, J. Int. Seq. 13 (2010) # 10.7.8, section 3.
Milan Janjić, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Tanya Khovanova, Recursive Sequences
W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, A Pascal rhombus, Fibonacci Quarterly, 35 (1976), 318-328.
Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, and Fausto Jarquín-Zárate, The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d)), arXiv:1904.13002 [math.NT], 2019.
Prabha Sivaraman Nair and Rejikumar Karunakaran, On k-Fibonacci Brousseau Sums, J. Int. Seq. (2024) Art. No. 24.6.4. See p. 2.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
S. Schuster, M. Fichtner and S. Sasso, Use of Fibonacci numbers in lipidomics - Enumerating various classes of fatty acids, Sci. Rep., 7 (2017) 39821.
Kai Wang, On k-Fibonacci Sequences And Infinite Series List of Results and Examples, 2020.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (3,1).

Row sums of Pascal's rhombus (A059317). Also row sums of triangle A054456(n, m).
Sequences with g.f. 1/(1-k*x-x^2) or x/(1-k*x-x^2): A000045 (k=1), A000129 (k=2), this sequence (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).
Cf. A006497, A052906, A175182 (Pisano periods), A201001 (prime subsequence), A092936 (squares).
Cf. A243399.

a:=[0,1];; for n in [3..30] do a[n]:=3*a[n-1]+a[n-2]; od; a; # Muniru A Asiru, Mar 31 2018

a006190 n = a006190_list !! n
a006190_list = 0 : 1 : zipWith (+) (map (* 3) $ tail a006190_list) a006190_list
-- Reinhard Zumkeller, Feb 19 2011

[ n eq 1 select 0 else n eq 2 select 1 else 3*Self(n-1)+Self(n-2): n in [1..30] ]; // Vincenzo Librandi, Aug 19 2011

a[0]:=0: a[1]:=1: for n from 2 to 35 do a[n]:= 3*a[n-1]+a[n-2] end do: seq(a[n],n=0..30); # Emeric Deutsch, Sep 03 2007
A006190:=-1/(-1+3*z+z**2); # Simon Plouffe in his 1992 dissertation, without the leading 0
seq(combinat[fibonacci](n,3),n=0..30); # R. J. Mathar, Dec 07 2011

a[n_] := (MatrixPower[{{1, 3}, {1, 2}}, n].{{1}, {1}})[[2, 1]]; Table[ a[n], {n, -1, 24}] (* Robert G. Wilson v, Jan 13 2005 *)
LinearRecurrence[{3,1},{0,1},30] (* or *) CoefficientList[Series[x/ (1-3x-x^2), {x,0,30}], x] (* Harvey P. Dale, Apr 20 2011 *)
Table[If[n==0, a1=1; a0=0, a2=a1; a1=a0; a0=3*a1+a2], {n, 0, 30}] (* Jean-François Alcover, Apr 30 2013 *)
Table[Fibonacci[n, 3], {n, 0, 30}] (* Vladimir Reshetnikov, May 08 2016 *)

a(n)=if(n<1,0,contfracpnqn(vector(n,i,2+(i>1)))[2,1])

a(n)=([1,3;1,2]^n)[2,1] \\ Charles R Greathouse IV, Mar 06 2014

concat([0],Vec(x/(1-3*x-x^2)+O(x^30))) \\ Joerg Arndt, Apr 30 2013

[lucas_number1(n,3,-1) for n in range(0, 30)] # Zerinvary Lajos, Apr 22 2009

G.f.: x/(1 - 3*x - x^2).
From Benoit Cloitre, Jun 14 2003: (Start)
a(3*n) = 2*A041019(5*n-1), a(3*n+1) = A041019(5*n), a(3*n+2) = A041019(5*n+3).
a(2*n) = 3*A004190(n-1); a(3*n) = 10*A041613(n-1) for n >= 1. (End)
From Gary W. Adamson, Jun 15 2003: (Start)
a(n-1) + a(n+1) = A006497(n).
A006497(n)^2 - 13*a(n)^2 = 4(-1)^n. (End)
a(n) = U(n-1, (3/2)i)(-i)^(n-1), i^2 = -1. - Paul Barry, Nov 19 2003
a(n) = Sum_{k=0..n-1} binomial(n-k-1,k)*3^(n-2*k-1). - Paul Barry, Oct 02 2004
a(n) = F(n, 3), the n-th Fibonacci polynomial evaluated at x=3.
Let M = {{0, 1}, {1, 3}}, v[1] = {0, 1}, v[n] = M.v[n - 1]; then a(n) = Abs[v[n][[1]]]. - Roger L. Bagula, May 29 2005 [Or a(n) = [M^(n+1)]{1,1}. - _L. Edson Jeffery, Aug 27 2013]
From Paul Barry, May 21 2006: (Start)
a(n+1) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(k-j).
a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(n-j-k).
a(n+1) = Sum_{k=0..floor(n/2)} C(n-k,k)*3^(n-2*k).
a(n) = Sum_{k=0..n} C(k,n-k)*3^(2*k-n). (End)
E.g.f.: exp(3*x/2)*sinh(sqrt(13)*x/2)/(sqrt(13)/2). - Paul Barry, Jun 03 2006
a(n) = (ap^n - am^n)/(ap - am), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2.
Let C = (3 + sqrt(13))/2 = exp arcsinh(3/2) = 3.3027756377... Then C^n, n > 0 = a(n)*(1/C) + a(n+1). Let X = the 2 X 2 matrix [0, 1; 1, 3]. Then X^n = [a(n-1), a(n); a(n), a(n+1)]. - Gary W. Adamson, Dec 21 2007
1/3 = 3/(1*10) + 3/(3*33) + 3/(10*109) + 3/(33*360) + 3/(109*1189) + ... . - Gary W. Adamson, Mar 16 2008
a(n) = ((3 + sqrt(13))^n - (3 - sqrt(13))^n)/(2^n*sqrt(13)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009
a(p) == 13^((p-1)/2) mod p, for odd primes p. - Gary W. Adamson, Feb 22 2009
From Johannes W. Meijer, Jun 12 2010: (Start)
Limit_{k->oo} a(n+k)/a(k) = (A006497(n) + a(n)*sqrt(13))/2.
Limit_{n->oo} A006497(n)/a(n) = sqrt(13). (End)
Sum_{k>=1} (-1)^(k-1)/(a(k)*a(k+1)) = (sqrt(13)-3)/2. - Vladimir Shevelev, Feb 23 2013
From Vladimir Shevelev, Feb 24 2013: (Start)
(1) Expression a(n+1) via a(n): a(n+1) = (3*a(n) + sqrt(13*a(n)^2 + 4*(-1)^n))/2;
(2) a^2(n+1) - a(n)*a(n+2) = (-1)^n;
(3) Sum_{k=1..n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);
(4) a(n)/a(n+1) = (sqrt(13)-3)/2 + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)
a(n) = sqrt(13*(A006497(n))^2 + (-1)^(n-1)*52)/13. - Vladimir Shevelev, Mar 13 2013
Sum_{n >= 1} 1/( a(2*n) + 1/a(2*n) ) = 1/3; Sum_{n >= 1} 1/( a(2*n + 1) - 1/a(2*n + 1) ) = 1/9. - Peter Bala, Mar 26 2015
From Rogério Serôdio, Mar 30 2018: (Start)
Some properties:
(1) a(n)*a(n+1) = 3*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 = 3*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(2*n) = a(n)*(3*a(n) + 2*a(n-1));
(7) 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;
(8) a(n) = alpha(k)*a(n-2*k+1) + a(n-4*k+2), where alpha(k) = ap^(2*k-1) + am^(2*k-1), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2;
(9) 131|Sum_{k=n..n+9} a(k), for all positive n. (End)
From Kai Wang, Feb 10 2020: (Start)
a(n)^2 - a(n+r)*a(n-r) = (-1)^(n-r)*a(r)^2 - Catalan's identity.
arctan(1/a(2n)) - arctan(1/a(2n+2)) = arctan(a(2)/a(2n+1)).
arctan(1/a(2n)) = Sum_{m>=n} arctan(a(2)/a(2m+1)).
The same formula holds for Fibonacci numbers and Pell numbers. (End)
a(n+2) = 3^(n+1) + Sum_{k=0..n} a(k)*3^(n-k). - Greg Dresden and Gavron Campbell, Feb 22 2022
G.f. = 1/(1-Sum_{k>=1} P(k)*x^k), P(k)=A000129(k) (with a(0)=1). - Enrique Navarrete, Dec 17 2023
G.f.: x/(1 - 3*x - x^2) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (m*k + 3 - m + x)/(1 + m*k*x) ) for arbitrary m (a telescoping series). - Peter Bala, May 08 2024
Sum_{n>=0} a(n)/phi^(3*n) = 1, where phi = A001622 is the golden ratio. - Diego Rattaggi, Apr 07 2025

Second formula corrected by Johannes W. Meijer, Jun 02 2010

A002530 a(n) = 4*a(n-2) - a(n-4) for n > 1, a(n) = n for n = 0, 1.

Original entry on oeis.org

0, 1, 1, 3, 4, 11, 15, 41, 56, 153, 209, 571, 780, 2131, 2911, 7953, 10864, 29681, 40545, 110771, 151316, 413403, 564719, 1542841, 2107560, 5757961, 7865521, 21489003, 29354524, 80198051, 109552575, 299303201, 408855776, 1117014753, 1525870529, 4168755811

Offset: 0

N. J. A. Sloane

Denominators of continued fraction convergents to sqrt(3), for n >= 1.
Also denominators of continued fraction convergents to sqrt(3) - 1. See A048788 for numerators. - N. J. A. Sloane, Dec 17 2007. Convergents are 1, 2/3, 3/4, 8/11, 11/15, 30/41, 41/56, 112/153, ...
Consider the mapping f(a/b) = (a + 3*b)/(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, 2/1, 5/3, 7/4, 19/11, ... converging to 3^(1/2). Sequence contains the denominators. The same mapping for N, i.e., f(a/b) = (a + Nb)/(a + b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571), ...; the sum of the first 6 terms of this series = 1.7320490367..., while sqrt(3) = 1.7320508075... - Gary W. Adamson, Dec 15 2007
From Clark Kimberling, Aug 27 2008: (Start)
  Related convergents (numerator/denominator):
  lower principal convergents: A001834/A001835
  upper principal convergents: A001075/A001353
  intermediate convergents: A005320/A001075
  principal and intermediate convergents: A143642/A140827
  lower principal and intermediate convergents: A143643/A005246. (End)
Row sums of triangle A152063 = (1, 3, 4, 11, ...). - Gary W. Adamson, Nov 26 2008
From Alois P. Heinz, Apr 13 2011: (Start)
Also number of domino tilings of the 3 X (n-1) rectangle with upper left corner removed iff n is even.  For n=4 the 4 domino tilings of the 3 X 3 rectangle with upper left corner removed are:
   . ._. . ._. . ._. . ._.
   .|__| .|__| .| | | .|___|
   | |_| | | | | | ||| |_| |
   ||__| |||_| ||__| |_|_|  (End)
This is the sequence of Lehmer numbers u_n(sqrt(R),Q) with the parameters R = 2 and Q = -1. It is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for all natural numbers n and m. - Peter Bala, Apr 18 2014
2^(-floor(n/2))*(1 + sqrt(3))^n = A002531(n) + a(n)*sqrt(3); integers in the real quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 11 2018
Let T(n) = 2^(n mod 2), U(n) = a(n), V(n) = A002531(n), x(n) = V(n)/U(n). Then T(n*m) * U(n+m) = U(n)*V(m) + U(m)*V(n), T(n*m) * V(n+m) = 3*U(n)*U(m) + V(m)*V(n), x(n+m) = (3 + x(n)*x(m))/(x(n) + x(m)). - Michael Somos, Nov 29 2022

			Convergents to sqrt(3) are: 1, 2, 5/3, 7/4, 19/11, 26/15, 71/41, 97/56, 265/153, 362/209, 989/571, 1351/780, 3691/2131, ... = A002531/A002530 for n >= 1.
1 + 1/(1 + 1/(2 + 1/(1 + 1/2))) = 19/11 so a(5) = 11.
G.f. = x + x^2 + 3*x^3 + 4*x^4 + 11*x^5 + 15*x^6 + 41*x^7 + ... - _Michael Somos_, Mar 18 2022

Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
Russell Lyons, A bird's-eye view of uniform spanning trees and forests, in Microsurveys in Discrete Probability, AMS, 1998.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 181.
Murat Sahin and Elif Tan, Conditional (strong) divisibility sequences, Fib. Q., 56 (No. 1, 2018), 18-31.
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).
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.

Harry J. Smith, Table of n, a(n) for n = 0..2000
Peter Bala, Notes on 2-periodic continued fractions and Lehmer sequences
Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays, JIS 12 (2009) 09.8.6.
Mario Catalani, Sequences related to convergents to square root of rationals, arXiv:math/0305270 [math.NT], 2003.
Marcia Edson, Scott Lewis and Omer Yayenie, The k-periodic Fibonacci sequence and an extended Binet's formula, INTEGERS 11 (2011) #A32.
Aviezri S. Fraenkel, Jonathan Levitt, and Michael Shimshoni, Characterization of the set of values f(n)=[n alpha], n=1,2,..., Discrete Math. 2 (1972), no.4, 335-345.
Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.
Clark Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.
MacTutor, D'Arcy Thompson on Greek irrationals
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Albert Tarn, Approximations to certain square roots and the series of numbers connected therewith [Annotated scanned copy]
D'Arcy Thompson, Excess and Defect: Or the Little More and the Little Less, Mind, New Series, Vol. 38, No. 149 (Jan., 1929), pp. 43-55 (13 pages). See page 48.
Hein van Winkel, Q-quadrangles inscribed in a circle, 2014. See Table 1. [Reference from Antreas Hatzipolakis, Jul 14 2014]
Russell Walsmith, CL-Chemy Transforms Fibonacci-Type Sequences to Arrays
E. W. Weisstein, MathWorld: Lehmer Number
Index entries for "core" sequences
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-1).
Index entries for sequences related to Chebyshev polynomials.

Cf. A002531 (numerators of convergents to sqrt(3)), A048788, A003297.
Bisections: A001353 and A001835.
Cf. A152063.
Cf. A108412, A049310.
Analog for sqrt(m): A000129 (m=2), A001076 (m=5), A041007 (m=6), A041009 (m=7), A041011 (m=8), A005668 (m=10), A041015 (m=11), A041017 (m=12), ..., A042935 (m=999), A042937 (m=1000).

I:=[0,1,1,3]; [n le 4 select I[n] else 4*Self(n-2) - Self(n-4): n in [1..50]]; // G. C. Greubel, Feb 25 2019

a := proc(n) option remember; if n=0 then 0 elif n=1 then 1 elif n=2 then 1 elif n=3 then 3 else 4*a(n-2)-a(n-4) fi end; [ seq(a(i),i=0..50) ];
A002530:=-(-1-z+z**2)/(1-4*z**2+z**4); # conjectured (correctly) by Simon Plouffe in his 1992 dissertation

Join[{0},Table[Denominator[FromContinuedFraction[ContinuedFraction[Sqrt[3],n]]], {n,1,50}]] (* Stefan Steinerberger, Apr 01 2006 *)
Join[{0},Denominator[Convergents[Sqrt[3],50]]] (* or *) LinearRecurrence[ {0,4,0,-1},{0,1,1,3},50] (* Harvey P. Dale, Jan 29 2013 *)
a[ n_] := If[n<0, -(-1)^n, 1] SeriesCoefficient[ x*(1+x-x^2)/(1-4*x^2+x^4), {x, 0, Abs@n}]; (* Michael Somos, Apr 18 2019 *)
a[ n_] := ChebyshevU[n-1, Sqrt[-1/2]]*Sqrt[2]^(Mod[n, 2]-1)/I^(n-1) //Simplify; (* Michael Somos, Nov 29 2022 *)

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

{ for (n=0, 50, a=contfracpnqn(vector(n, i, 1+(i>1)*(i%2)))[2, 1]; write("b002530.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 01 2009

my(w=quadgen(12)); A002530(n)=real((2+w)^(n\/2)*if(bittest(n,0),1-w/3,w/3));
apply(A002530, [0..30]) \\ M. F. Hasler, Nov 04 2019

from functools import cache
@cache
def a(n): return [0, 1, 1, 3][n] if n < 4 else 4*a(n-2) - a(n-4)
print([a(n) for n in range(36)]) # Michael S. Branicky, Nov 13 2022

(x*(1+x-x^2)/(1-4*x^2+x^4)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Feb 25 2019

G.f.: x*(1 + x - x^2)/(1 - 4*x^2 + x^4).
a(n) = 4*a(n-2) - a(n-4). [Corrected by László Szalay, Feb 21 2014]
a(n) = -(-1)^n * a(-n) for all n in Z, would satisfy the same recurrence relation. - Michael Somos, Jun 05 2003
a(2*n) = a(2*n-1) + a(2*n-2), a(2*n+1) = 2*a(2*n) + a(2*n-1).
From Benoit Cloitre, Dec 15 2002: (Start)
a(2*n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(2*sqrt(3)).
a(2*n) = A001353(n).
a(2*n-1) = ceiling((1 + 1/sqrt(3))/2*(2 + sqrt(3))^n) = ((3 + sqrt(3))^(2*n - 1) + (3 - sqrt(3))^(2*n - 1))/6^n.
a(2*n-1) = A001835(n). (End)
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n - k, k) * 2^floor((n - 2*k)/2). - Paul Barry, Jul 13 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(floor(n/2) + k, floor((n - 1)/2 - k))*2^k. - Paul Barry, Jun 22 2005
G.f.: (sqrt(6) + sqrt(3))/12*Q(0), where Q(k) = 1 - a/(1 + 1/(b^(2*k) - 1 - b^(2*k)/(c + 2*a*x/(2*x - g*m^(2*k)/(1 + a/(1 - 1/(b^(2*k + 1) + 1 - b^(2*k + 1)/(h - 2*a*x/(2*x + g*m^(2*k + 1)/Q(k + 1)))))))))). - Sergei N. Gladkovskii, Jun 21 2012
a(n) = (alpha^n - beta^n)/(alpha - beta) for n odd, and a(n) = (alpha^n - beta^n)/(alpha^2 - beta^2) for n even, where alpha = 1/2*(sqrt(2) + sqrt(6)) and beta = (1/2)*(sqrt(2) - sqrt(6)). Cf. A108412. - Peter Bala, Apr 18 2014
a(n) = (-sqrt(2)*i)^n*S(n, sqrt(2)*i)*2^(-floor(n/2)) = A002605(n)*2^(-floor(n/2)), n >= 0, with i = sqrt(-1) and S the Chebyshev polynomials (A049310). - Wolfdieter Lang, Feb 10 2018
a(n+1)*a(n+2) - a(n+3)*a(n) = (-1)^n, n >= 0. - Kai Wang, Feb 06 2020
E.g.f.: sinh(sqrt(3/2)*x)*(sinh(x/sqrt(2)) + sqrt(2)*cosh(x/sqrt(2)))/sqrt(3). - Stefano Spezia, Feb 07 2020
a(n) = ((1 + sqrt(3))^n - (1 - sqrt(3))^n)/(2*2^floor(n/2))/sqrt(3) = A002605(n)/2^floor(n/2). - Robert FERREOL, Apr 13 2023

Definition edited by M. F. Hasler, Nov 04 2019

A073133 Table by antidiagonals of T(n,k) = n*T(n,k-1) + T(n,k-2) starting with T(n,1) = 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 3, 1, 4, 10, 12, 5, 1, 5, 17, 33, 29, 8, 1, 6, 26, 72, 109, 70, 13, 1, 7, 37, 135, 305, 360, 169, 21, 1, 8, 50, 228, 701, 1292, 1189, 408, 34, 1, 9, 65, 357, 1405, 3640, 5473, 3927, 985, 55, 1, 10, 82, 528, 2549, 8658, 18901, 23184, 12970, 2378, 89

Offset: 1

Henry Bottomley, Jul 16 2002

Columns of the array are generated from Fibonacci polynomials f(x). They are: (1), (x), (x^2 + 1), (x^3 + 2x), (x^4 + 3x^2 + 1), (x^5 + 4x^3 + 3x), (x^6 + 5x^4 + 6x^2 +1), ... If column headings start 0, 1, 2, ... then the terms in the n-th column are generated from the n-th degree Fibonacci polynomial. For example, column 5 (8, 70, 360, ...) is generated from f(x), x = 1,2,3,...; fifth-degree polynomial x^5 + 4x^3 + 3x; e.g., f(2) = 70 = 2^5 + 4*8 + 3*2. - Gary W. Adamson, Apr 02 2006
The ratio of two consecutive entries of the sequence in the n-th row approaches (n + sqrt(n^2 + 4))/2. Example: The sequence beginning (1, 3, 10, 33, ...) tends to 3.302775... = (3 + sqrt(13))/2. - Gary W. Adamson, Aug 12 2013
As to the array sequences, (n+1)-th sequence is the INVERT transform of the n-th sequence. - Gary W. Adamson, Aug 20 2013
The array can be extended infinitely above the Fibonacci row by taking successive INVERTi transforms, resulting in:
  ...
  1,  -2,   5, -12,  29, -70, ...
  1,  -1,   2,  -3,   5,  -8, ...
  l,   0,   1,   0,   1,   0, ...
  1,   1,   2,   3,   5,   8, ...
  1,   2,   5,  12,  29,  70, ...
  ...
  This results in an infinite array in which sequences above the (1, 0, 1, 0, ...) are reflections of the sequences below, except for the alternate signs. Any sequence in the (+ sign) row starting (1, n, ...) is the (2*n-th) INVERT transform of the same sequence but with alternate signs.  Example: (1, 2, 5, 12, ...) is the (2*2) = fourth INVERT transform of (1, -2, 5, -12, ...) by inspection. Conjecture:  This "reflection" principle will result from taking successive INVERT transforms of any aerated sequence starting 1, ... and with positive signs. Likewise, the rows above the aerated sequence are successive INVERTi transforms of the aerated sequence. - Gary W. Adamson, Jul 14 2019
From Michael A. Allen, Feb 21 2023: (Start)
Row n is the n-metallonacci sequence.
T(n,k) is the number of tilings of a (k-1)-board (a board with dimensions (k-1) X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are n kinds of squares available. (End)

			Table begins:
  1, 1,  2,  3,   5,    8,   13, ...
  1, 2,  5, 12,  29,   70,  169, ...
  1, 3, 10, 33, 109,  360, 1189, ...
  1, 4, 17, 72, 305, 1292, 5473, ... etc.

G. C. Greubel, Antidiagonals n = 1..100, flattened
Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.

Rows are A000045, A000129, A006190, A001076, A052918, A005668, A054413, A041025, A099371, A041041, A049666, A041061, A140455, A041085, etc.
Columns are A000012, A000027, A002522, A054602, A057721, A124152, etc.
Different from A081572.

T:= function(n,k)
    if k<0 then return 0;
    elif k=1 then return 1;
    else return n*T(n,k-1) + T(n,k-2);
    fi;
  end;
Flat(List([1..15], n-> List([1..n], k-> T(n-k+1,k) ))); # G. C. Greubel, Aug 12 2019

A073133 := proc(n,k)
    option remember;
    if k <= 1 then
        k;
    else
        n*procname(n,k-1)+procname(n,k-2) ;
    end if;
end proc:
seq(seq( A073133(d-k,k),k=1..d-1),d=2..13) ; # R. J. Mathar, Aug 16 2019

T[n_, 1]:= 1; T[n_, k_]:= T[n, k] = If[k<0, 0, n*T[n, k-1] + T[n, k-2]]; Table[T[n-k+1, k], {n, 15}, {k, n}]//Flatten (* G. C. Greubel, Aug 12 2019 *)

T(n,k) = if(k==1, 1, k<0, 0, n*T(n,k-1)+T(n,k-2));
for(n=1,15, for(k=1,n, print1(T(n-k+1,k), ", "))) \\ G. C. Greubel, Aug 12 2019

def T(n, k):
    if (k<0): return 0
    elif (k==1): return 1
    else: return n*T(n, k-1) + T(n, k-2)
[[T(n-k+1, k) for k in (1..n)] for n in (1..15)] # G. C. Greubel, Aug 12 2019

T(n, k) = A073134(n, k) + 2*A073135(n, k-2) = Sum_{j=0..k-1} abs(A049310(k-1, j)*n^j).
T(n,k) = [[0,1; 1,n]^{k+1}]{1,1}, n,k in {1,2,...}. - _L. Edson Jeffery, Sep 23 2012
G.f. for row n: x/(1-n*x-x^2). - L. Edson Jeffery, Aug 28 2013

A037027 Skew Fibonacci-Pascal triangle read by rows.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 5, 3, 1, 5, 10, 9, 4, 1, 8, 20, 22, 14, 5, 1, 13, 38, 51, 40, 20, 6, 1, 21, 71, 111, 105, 65, 27, 7, 1, 34, 130, 233, 256, 190, 98, 35, 8, 1, 55, 235, 474, 594, 511, 315, 140, 44, 9, 1, 89, 420, 942, 1324, 1295, 924, 490, 192, 54, 10, 1, 144, 744, 1836

Offset: 0

Floor van Lamoen, Jan 01 1999

T(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (0,1), (1,0), (2,0). - Joerg Arndt, Jun 30 2011
T(n,k) is the number of lattice paths of length n, starting from the origin and ending at (n,k), using horizontal steps H=(1,0), up steps U=(1,1) and down steps D=(1,-1), never containing UUU, DD, HD. For instance, for n=4 and k=2, we have the paths; HHUU, HUHU, HUUH, UHHU, UHUH, UUHH, UUDU, UDUU, UUUD. - Emanuele Munarini, Mar 15 2011
Row sums form Pell numbers A000129, T(n,0) forms Fibonacci numbers A000045, T(n,1) forms A001629. T(n+k,n-k) is polynomial sequence of degree k.
T(n,k) gives a convolved Fibonacci sequence (A001629, A001872, etc.).
As a Riordan array, this is (1/(1-x-x^2),x/(1-x-x^2)). An interesting factorization is (1/(1-x^2),x/(1-x^2))*(1/(1-x),x/(1-x)) [abs(A049310) times A007318]. Diagonal sums are the Jacobsthal numbers A001045(n+1). - Paul Barry, Jul 28 2005
T(n,k) = T'(n+1,k+1), T' given by [0, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 19 2005
Equals A049310 * A007318 as infinite lower triangular matrices. - Gary W. Adamson, Oct 28 2007
This triangle may also be obtained from the coefficients of the Morgan-Voyce polynomials defined by: Mv(x, n) = (x + 1)*Mv(x, n - 1) + Mv(x, n - 2). - Roger L. Bagula, Apr 09 2008
Row sums are A000129. - Roger L. Bagula, Apr 09 2008
Absolute value of coefficients of the characteristic polynomial of tridiagonal matrices with 1's along the main diagonal, and i's along the superdiagonal and the subdiagonal (where i=sqrt(-1), see Mathematica program). - John M. Campbell, Aug 23 2011
A037027 is jointly generated with A122075 as an array of coefficients of polynomials v(n,x): initially, u(1,x)=v(1,x)=1; for n>1, u(n,x)=u(n-1,x)+(x+1)*v(n-1)x and v(n,x)=u(n-1,x)+x*v(n-1,x). See the Mathematica section at A122075. - Clark Kimberling, Mar 05 2012
For a closed-form formula for arbitrary left and right borders of Pascal like triangle see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 09 2013
Row n, for n>=0, shows the coefficients of the polynomial u(n) = c(0) + c(1)*x + ... + c(n)*x^n which is the denominator of the n-th convergent of the continued fraction [x+1, x+1, x+1, ...]; see A230000. - Clark Kimberling, Nov 13 2013
T(n,k) is the number of ternary words of length n having k letters 2 and avoiding a runs of odd length for the letter 0. - Milan Janjic, Jan 14 2017
Let T(m, n, k) be an m-bonacci Pascal's triangle, where T(m, n, 0) gives the values of F(m, n), the n-th m-bonacci number, and T(m, n, k) gives the values for the k-th convolution of F(m, n). Then the classic Pascal triangle is T(1, n, k) and this sequence is T(2, n, k). T(m, n, k) is the number of compositions of n using only the positive integers 1, 1' and 2 through m, with the part 1' used exactly k times. G.f. for k-th column of T(m, n, k): x/(1 - x - x^2 - ... - x^m)^k. The row sum for T(m, n, k) is the number of compositions of n using only the positive integers 1, 1' and 2 through m. G.f. for row sum of T(m, n, k): 1/(1 - 2x - x^2 - ... - x^m). - Gregory L. Simay, Jul 24 2021

			Ratio of row polynomials R(3)/R(2) = (3 + 5*x + 3*x^2 + x^3)/(2 + 2*x + x^2) = [1+x; 1+x, 1+x].
Triangle begins:
                                 1;
                              1,    1;
                           2,    2,    1;
                        3,    5,    3,    1;
                     5,   10,    9,    4,    1;
                  8,   20,   22,   14,    5,    1;
              13,   38,   51,   40,   20,    6,    1;
           21,   71,  111,  105,   65,   27,    7,    1;
        34,  130,  233,  256,  190,   98,   35,    8,    1;
     55,  235,  474,  594,  511,  315,  140,   44,    9,    1;
  89,  420,  942, 1324, 1295,  924,  490,  192,   54,   10,    1;

Reinhard Zumkeller, Rows n = 0..150 of triangle, flattened
Harlan J. Brothers, Pascal's Prism: Supplementary Material
Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.
T. Mansour, Generalization of some identities involving the Fibonacci numbers, arXiv:math/0301157 [math.CO], 2003.
P. Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.
Yidong Sun, Numerical Triangles and Several Classical Sequences, Fib. Quart. 43, no. 4, Nov. 2005, pp. 359-370.
Eric Weisstein's World of Mathematics, Morgan-Voyce Polynomials.

A038112(n) = T(2n, n). A038137 is reflected version. Maximal row entries: A038149.
Diagonal differences are in A055830. Vertical sums are in A091186.
Cf. A007318, A049310, A000129, A155161, A122542, A059283, A228196, A228576.
Some other Fibonacci-Pascal triangles: A027926, A036355, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

a037027 n k = a037027_tabl !! n !! k
a037027_row n = a037027_tabl !! n
a037027_tabl = [1] : [1,1] : f [1] [1,1] where
   f xs ys = ys' : f ys ys' where
     ys' = zipWith3 (\u v w -> u + v + w) (ys ++ [0]) (xs ++ [0,0]) ([0] ++ ys)
-- Reinhard Zumkeller, Jul 07 2012

T := (n,k) -> `if`(n=0,1,binomial(n,k)*hypergeom([(k-n)/2, (k-n+1)/2], [-n], -4)): seq(seq(simplify(T(n,k)), k=0..n), n=0..10); # Peter Luschny, Apr 25 2016
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> combinat:-fibonacci(n)); # Peter Luschny, Oct 07 2022

Mv[x, -1] = 0; Mv[x, 0] = 1; Mv[x, 1] = 1 + x; Mv[x_, n_] := Mv[x, n] = ExpandAll[(x + 1)*Mv[x, n - 1] + Mv[x, n - 2]]; Table[ CoefficientList[ Mv[x, n], x], {n, 0, 10}] // Flatten (* Roger L. Bagula, Apr 09 2008 *)
Abs[Flatten[Table[CoefficientList[CharacteristicPolynomial[Array[KroneckerDelta[#1,#2]+KroneckerDelta[#1,#2+1]*I+KroneckerDelta[#1,#2-1]*I&,{n,n}],x],x],{n,1,20}]]] (* John M. Campbell, Aug 23 2011 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[(k-n)/2, (k-n+1)/2, -n, -4];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 16 2019, after Peter Luschny *)

{T(n, k) = if( k<0 || k>n, 0, if( n==0 && k==0, 1, T(n-1, k) + T(n-1, k-1) + T(n-2, k)))}; /* Michael Somos, Sep 29 2003 */

PARI
```
T(n,k)=if(nPaul D. Hanna, Feb 27 2004
```

T(n, m) = T'(n-1, m) + T'(n-2, m) + T'(n-1, m-1), where T'(n, m) = T(n, m) for n >= 0 and 0< = m <= n and T'(n, m) = 0 otherwise.
G.f.: 1/(1 - y - y*z - y^2).
G.f. for k-th column: x/(1-x-x^2)^k.
T(n, m) = Sum_{k=0..n-m} binomial(m+k, m)*binomial(k, n-k-m), n >= m >= 0, otherwise 0. - Wolfdieter Lang, Jun 17 2002
T(n, m) = ((n-m+1)*T(n, m-1) + 2*(n+m)*T(n-1, m-1))/(5*m), n >= m >= 1; T(n, 0)= A000045(n+1); T(n, m)= 0 if n < m. - Wolfdieter Lang, Apr 12 2000
Chebyshev coefficient triangle (abs(A049310)) times Pascal's triangle (A007318) as product of lower triangular matrices. T(n, k) = Sum_{j=0..n} binomial((n+j)/2, j)*(1+(-1)^(n+j))*binomial(j, k)/2. - Paul Barry, Dec 22 2004
Let R(n) = n-th row polynomial in x, with R(0)=1, then R(n+1)/R(n) equals the continued fraction [1+x;1+x, ...(1+x) occurring (n+1) times ..., 1+x] for n >= 0. - Paul D. Hanna, Feb 27 2004
T(n,k) = Sum_{j=0..n} binomial(n-j,j)*binomial(n-2*j,k); in Egorychev notation, T(n,k) = res_w(1-w-w^2)^(-k-1)*w^(-n+k+1). - Paul Barry, Sep 13 2006
Sum_{k=0..n} T(n,k)*x^k = A000045(n+1), A000129(n+1), A006190(n+1), A001076(n+1), A052918(n), A005668(n+1), A054413(n), A041025(n), A099371(n+1), A041041(n), A049666(n+1), A041061(n), A140455(n+1), A041085(n), A154597(n+1), A041113(n) for x = 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 29 2009
T((m+1)*n+r-1, m*n+r-1)*r/(m*n+r) = Sum_{k=1..n} k/n*T((m+1)*n-k-1, m*n-1)*(r+k,r), n >= m > 1.
T(n-1,m-1) = (m/n)*Sum_{k=1..n-m+1} k*A000045(k)*T(n-k-1,m-2), n >= m > 1. - Vladimir Kruchinin, Mar 17 2011
T(n,k) = binomial(n,k)*hypergeom([(k-n)/2, (k-n+1)/2], [-n], -4) for n >= 1. - Peter Luschny, Apr 25 2016

Examples from Paul D. Hanna, Feb 27 2004

A172236 Array A(n,k) = n*A(n,k-1) + A(n,k-2) read by upward antidiagonals, starting A(n,0) = 0, A(n,1) = 1.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 5, 3, 0, 1, 4, 10, 12, 5, 0, 1, 5, 17, 33, 29, 8, 0, 1, 6, 26, 72, 109, 70, 13, 0, 1, 7, 37, 135, 305, 360, 169, 21, 0, 1, 8, 50, 228, 701, 1292, 1189, 408, 34, 0, 1, 9, 65, 357, 1405, 3640, 5473, 3927, 985, 55, 0, 1, 10, 82, 528, 2549, 8658, 18901, 23184, 12970, 2378, 89, 0, 1, 11, 101, 747, 4289, 18200, 53353, 98145, 98209, 42837, 5741, 144

Offset: 1

Roger L. Bagula, Jan 29 2010

Equals A073133 with an additional column A(.,0).
If the first column and top row are deleted, antidiagonal reading yields A118243.
Adding a top row of 1's and antidiagonal reading downwards yields A157103.
Antidiagonal sums are 0, 1, 2, 5, 12, 32, 93, 297, 1035, 3911, 15917, 69350, ....
From Jianing Song, Jul 14 2018: (Start)
All rows have strong divisibility, that is, gcd(A(n,k_1), A(n,k_2)) = A(n,gcd(k_1,k_2)) holds for all k_1, k_2 >= 0.
Let E(n,m) be the smallest number l such that m divides A(n,l), we have: for odd primes p that are not divisible by n^2 + 4, E(n,p) divides p - ((n^2+4)/p) if p == 3 (mod 4) and (p - ((n^2+4)/p))/2 if p == 1 (mod 4). E(n,p) = p for odd primes p that are divisible by n^2 + 4. E(n,2) = 2 for even n and 3 for odd n. Here ((n^2+4)/p) is the Legendre symbol. A prime p such that p^2 divides T(n,E(n,p)) is called an n-Wall-Sun-Sun prime.
E(n,p^e) <= p^(e-1)*E(n,p) for all primes p. If p^2 does not divide A(n, E(n,p)), then E(n,p^e) = p^(e-1)*E(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 + 4, p^2 is never divisible by A(n,p), so E(n,p^e) = p^e as described above. E(n,m_1*m_2) = lcm(E(n,m_1),E(n,m_2)) if gcd(m_1,m_2) = 1.
Let pi(n,m) be the Pisano period of A(n, k) modulo m, i.e, the smallest number l such that A(n, k+1) == T(n,k) (mod m) holds for all k >= 0, we have: for odd primes p that are not divisible by n^2 - 4, pi(n,p) divides p - 1 if ((n^2+4)/p) = 1 and 2(p+1) if ((n^2+4)/p) = -1. pi(n,p) = 4p for odd primes p that are divisible by n^2 + 4. pi(n,2) = 2 even n and 3 for odd n.
pi(n,p^e) <= p^(e-1)*pi(n,p) for all primes p. If p^2 does not divide A(n, E(n,p)), then pi(n,p^e) = p^(e-1)*pi(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 + 4, p^2 is never divisible by A(n, p), so pi(n,p^e) = 4p^e as described above. pi(n,m_1*m_2) = lcm(pi(n,m_1), pi(n,m_2)) if gcd(m_1,m_2) = 1.
If n != 2, the largest possible value of pi(n,m)/m is 4 for even n and 6 for odd n. For even n, pi(n,p^e) = 4p^e; for odd n, pi(n,2p^e) = 12p^e, where p is any odd prime factor of n^2 + 4. For n = 2 it is 8/3, obtained by m = 3^e.
Let z(n,m) be the number of zeros in a period of A(n, k) modulo m, i.e., z(n,m) = pi(n,m)/E(n,m), then we have: z(n,p) = 4 for odd primes p that are divisible by n^2 + 4. For other odd primes p, z(n,p) = 4 if E(n,p) is odd; 1 if E(n,p) is even but not divisible by 4; 2 if E(n,p) is divisible by 4; see the table below. z(n,2) = z(n,4) = 1.
Among all values of z(n,p) when p runs through all odd primes that are not divisible by n^2 + 4, we have:
((n^2+4)/p)...p mod 8....proportion of 1.....proportion of 2.....proportion of 4
......1..........1......1/6 (conjectured)...2/3 (conjectured)...1/6 (conjectured)*
......1..........5......1/2 (conjectured)...........0...........1/2 (conjectured)*
......1.........3,7.............1...................0...................0
.....-1.........1,5.............0...................0...................1
.....-1.........3,7.............0...................1...................0
* The result is that among all odd primes that are not divisible by n^2 + 4, 7/24 of them are with z(n,p) = 1, 5/12 are with z(n,p) = 2 and 7/24 are with z(n,p) = 4 if n^2 + 4 is a twice a square; 1/3 of them are with z(n,p) = 1, 1/3 are with z(n,p) = 2 and 1/3 are with z(n,p) = 4 otherwise. [Corrected by Jianing Song, Jul 06 2019]
z(n,p^e) = z(n,p) for all odd primes p; z(n,2^e) = 1 for even n and 2 for odd n, e >= 3.
(End)
From Michael A. Allen, Mar 06 2023: (Start)
Removing the first (n=0) row of A352361 gives this sequence.
Row n is the n-metallonacci sequence.
A(n,k) is (for k>0) the number of tilings of a (k-1)-board (a board with dimensions (k-1) X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are n kinds of squares available. (End)

			The array, A(n, k), starts in row n = 1 with columns k >= 0 as
  0      1      1      2      3      5      8
  0      1      2      5     12     29     70
  0      1      3     10     33    109    360
  0      1      4     17     72    305   1292
  0      1      5     26    135    701   3640
  0      1      6     37    228   1405   8658
  0      1      7     50    357   2549  18200
  0      1      8     65    528   4289  34840
  0      1      9     82    747   6805  61992
  0      1     10    101   1020  10301 104030
  0      1     11    122   1353  15005 166408
Antidiagonal triangle, T(n, k), begins as:
  0;
  0, 1;
  0, 1, 1;
  0, 1, 2,  2;
  0, 1, 3,  5,   3;
  0, 1, 4, 10,  12,   5;
  0, 1, 5, 17,  33,  29,    8;
  0, 1, 6, 26,  72, 109,   70,   13;
  0, 1, 7, 37, 135, 305,  360,  169,  21;
  0, 1, 8, 50, 228, 701, 1292, 1189, 408, 34;

Jianing Song, Antidiagonals n = 1..100, flattened (the first 30 antidiagonals from Vincenzo Librandi)
Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.

Rows n include: A000045 (n=1), A000129 (n=2), A006190 (n=3), A001076 (n=4), A052918 (n=5), A005668 (n=6), A054413 (n=7), A041025 (n=8), A099371 (n=9), A041041 (n=10), A049666 (n=11), A041061 (n=12), A140455 (n=13), A041085 (n=14), A154597 (n=15), A041113 (n=16), A178765 (n=17), A041145 (n=18), A243399 (n=19), A041181 (n=20). (Note that there are offset shifts for rows n = 5, 7, 8, 10, 12, 14, 16..20.)
Columns k include: A000004 (k=0), A000012 (k=1), A000027 (k=2), A002522 (k=3), A054602 (k=4), A057721 (k=5), A124152 (k=6).
Entry points for A(n,k) modulo m: A001177 (n=1), A214028 (n=2), A322907 (n=3).
Pisano period for A(n,k) modulo m: A001175 (n=1), A175181 (n=2), A175182 (n=3), A175183 (n=4), A175184 (n=5), A175185 (n=6).
Number of zeros in a period for A(n,k) modulo m: A001176 (n=1), A214027 (n=2), A322906 (n=3).
Cf. A084844, A084845, A118243, A157103, A271782, A316269.
Sums include: A304357, A304359.
Similar to: A073133.

A172236:= func< n,k | k le 1 select k else Evaluate(DicksonSecond(k-1,-1), n-k) >;
[A172236(n,k): k in [0..n-1], n in [1..13]]; // G. C. Greubel, Sep 29 2024

A172236[n_,k_]:=Fibonacci[k, n-k];
Table[A172236[n, k], {n,15}, {k,0,n-1}]//Flatten

A(n, k) = if (k==0, 0, if (k==1, 1, n*A(n, k-1) + A(n, k-2)));
tabl(nn) = for(n=1, nn, for (k=0, nn, print1(A(n, k), ", ")); print); \\ Jianing Song, Jul 14 2018 (program from Michel Marcus; see also A316269)

A(n, k) = ([n, 1; 1, 0]^k)[2, 1] \\ Jianing Song, Nov 10 2018

def A172236(n,k): return sum(binomial(k-j-1,j)*(n-k)^(k-2*j-1) for j in range(1+(k-1)//2))
flatten([[A172236(n,k) for k in range(n)] for n in range(1,14)]) # G. C. Greubel, Sep 29 2024

A(n,k) = (((n + sqrt(n^2 + 4))/2)^k - ((n-sqrt(n^2 + 4))/2)^k)/sqrt(n^2 + 4), n >= 1, k >= 0. - Jianing Song, Jun 27 2018
For n >= 1, Sum_{i=1..k} 1/A(n,2^i) = ((u^(2^k-1) + v^(2^k-1))/(u + v)) * (1/A(n,2^k)), where u = (n + sqrt(n^2 + 4))/2, v = (n - sqrt(n^2 + 4))/2 are the two roots of the polynomial x^2 - n*x - 1. As a result, Sum_{i>=1} 1/A(n,2^i) = (n^2 + 4 - n*sqrt(n^2 + 4))/(2*n). - Jianing Song, Apr 21 2019
From G. C. Greubel, Sep 29 2024: (Start)
A(n, k) = F_{k}(n) (Fibonacci polynomials F_{n}(x)) (array).
T(n, k) = F_{k}(n-k) (antidiagonal triangle).
Sum_{k=0..n-1} T(n, k) = A304357(n) - (1-(-1)^n)/2.
Sum_{k=0..n-1} (-1)^k*T(n, k) = (-1)*A304359(n) + (1-(-1)^n)/2.
T(2*n, n) = A084844(n).
T(2*n+1, n+1) = A084845(n). (End)

More terms from Jianing Song, Jul 14 2018

A352361 Array read by ascending antidiagonals. A(n, k) = Fibonacci(k, n), where Fibonacci(n, x) are the Fibonacci polynomials.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 2, 2, 0, 0, 1, 3, 5, 3, 1, 0, 1, 4, 10, 12, 5, 0, 0, 1, 5, 17, 33, 29, 8, 1, 0, 1, 6, 26, 72, 109, 70, 13, 0, 0, 1, 7, 37, 135, 305, 360, 169, 21, 1, 0, 1, 8, 50, 228, 701, 1292, 1189, 408, 34, 0, 0, 1, 9, 65, 357, 1405, 3640, 5473, 3927, 985, 55, 1

Offset: 0

Peter Luschny, Mar 18 2022

From Michael A. Allen, Mar 26 2023: (Start)
Row n is the n-metallonacci sequence for n>0.
A(n,k), for n > 0 and k > 0, is the number of tilings of a (k-1)-board (a board with dimensions (k-1) X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are n kinds of squares available. (End)

			Array, A(n,k), starts:
  n\k 0, 1, 2,  3,   4,    5,     6,      7,       8,        9, ...
  -------------------------------------------------------------------------
  [0] 0, 1, 0,  1,   0,    1,     0,      1,       0,        1, ... A000035;
  [1] 0, 1, 1,  2,   3,    5,     8,     13,      21,       34, ... A000045;
  [2] 0, 1, 2,  5,  12,   29,    70,    169,     408,      985, ... A000129;
  [3] 0, 1, 3, 10,  33,  109,   360,   1189,    3927,    12970, ... A006190;
  [4] 0, 1, 4, 17,  72,  305,  1292,   5473,   23184,    98209, ... A001076;
  [5] 0, 1, 5, 26, 135,  701,  3640,  18901,   98145,   509626, ... A052918;
  [6] 0, 1, 6, 37, 228, 1405,  8658,  53353,  328776,  2026009, ... A005668;
  [7] 0, 1, 7, 50, 357, 2549, 18200, 129949,  927843,  6624850, ... A054413;
  [8] 0, 1, 8, 65, 528, 4289, 34840, 283009, 2298912, 18674305, ... A041025;
  [9] 0, 1, 9, 82, 747, 6805, 61992, 564733, 5144589, 46866034, ... A099371;
      |  |  |  | A054602 |   A124152;
      |  |  |  A002522   A057721;
      |  |  A001477;
      |  A000012;
      A000004;
Antidiagonals, T(n, k), begin as:
  0;
  0, 1;
  0, 1, 0;
  0, 1, 1,  1;
  0, 1, 2,  2,   0;
  0, 1, 3,  5,   3,   1;
  0, 1, 4, 10,  12,   5,   0;
  0, 1, 5, 17,  33,  29,   8,   1;
  0, 1, 6, 26,  72, 109,  70,  13,  0;
  0, 1, 7, 37, 135, 305, 360, 169, 21, 1;

G. C. Greubel, Antidiagonals n = 0..50, flattened
Michael A. Allen and Kenneth Edwards, Fence tiling derived identities involving the metallonacci numbers squared or cubed, Fib. Q. 60:5 (2022) 5-17.

Other versions of this array are A073133, A157103, A172236.
Rows n: A000035 (n=0), A000045 (n=1), A000129 (n=2), A006190 (n=3), A001076 (n=4), A052918 (n=5), A005668 (n=6), A054413 (n=7), A041025 (n=8), A099371 (n=9).
Columns k: A000004 (k=0), A000012 (k=1), A001477 (k=2), A002522 (k=3), A054602 (k=4), A057721 (k=5), A124152 (k=6).
Cf. A084844 (main diagonal), A352362 (Lucas polynomials), A350470 (Jacobsthal polynomials).
Sums include: A304357 (row sums), A304359.
Cf. A084845.

A352361:= func< n, k | k le 1 select k else Evaluate(DicksonSecond(k-1, -1), n-k) >;
[A352361(n, k): k in [0..n], n in [0..13]]; // G. C. Greubel, Sep 29 2024

seq(seq(combinat:-fibonacci(k, n - k), k = 0..n), n = 0..11);

Table[Fibonacci[k, n - k], {n, 0, 9}, {k, 0, n}] // Flatten
(* or *)
A[n_, k_] := With[{s = Sqrt[n^2 + 4]}, ((n + s)^k - (n - s)^k) / (2^k*s)];
Table[Simplify[A[n, k]], {n, 0, 9}, {k, 0, 9}] // TableForm

A(n, k) = ([1, k; 1, k-1]^n)[2, 1] ;
export(A)
for(k = 0, 9, print(parvector(10, n, A(n - 1, k))))

def A352361(n, k): return lucas_number1(k,n-k,-1)
flatten([[A352361(n, k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Sep 29 2024

A(n, k) = Sum_{j=0..floor((k-1)/2)} binomial(k-j-1, j)*n^(k-2*j-1).
A(n, k) = ((n + s)^k - (n - s)^k) / (2^k*s) where s = sqrt(n^2 + 4).
A(n, k) = [x^k] (x / (1 - n*x - x^2)).
A(n, k) = n^(k-1)*hypergeom([1 - k/2, 1/2 - k/2], [1 - k], -4/n^2) for n,k >= 1.
A(n, n) = T(2*n, n) = A084844(n).
From G. C. Greubel, Sep 29 2024: (Start)
T(n, k) = A(n-k, k) (antidiagonal triangle).
T(2*n+1, n+1) = A084845(n).
Sum_{k=0..n} T(n, k) = A304357(n) (row sums).
Sum_{k=0..n} (-1)^k*T(n, k) = (-1)*A304359(n). (End)

cp's OEIS Frontend

A175185 Pisano period of the 6-Fibonacci numbers A005668.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A099366 Squares of A005668.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A338080 Odd composite integers such that A005668(m)^2 == 1 (mod m).

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

Maxima

PARI

PARI

PARI

PARI

PARI

Python

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

A002530 a(n) = 4*a(n-2) - a(n-4) for n > 1, a(n) = n for n = 0, 1.

Views

Author