A015448 -id:A015448 - cp's OEIS frontend

A003946 Expansion of (1+x)/(1-3*x).

1, 4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, 6377292, 19131876, 57395628, 172186884, 516560652, 1549681956, 4649045868, 13947137604, 41841412812, 125524238436, 376572715308, 1129718145924

Offset: 0

N. J. A. Sloane

Coordination sequence for infinite tree with valency 4.
The n-th term of the coordination sequence of the infinite tree with valency 2m is the same as the number of reduced words of size n in the free group on m generators. In the five sequences A003946, A003948, A003950, A003952, A003954 m is 2, 3, 4, 5, 6. - Avi Peretz (njk(AT)netvision.net.il), Feb 23 2001 and Ola Veshta (olaveshta(AT)my-deja.com), Mar 30 2001
a(n) is the number of nonreversing random walks of the length of n edges on a two-dimensional square lattice, all beginning at a fixed point P. - Pawel P. Mazur (Pawel.Mazur(AT)pwr.wroc.pl), Apr 06 2005
Binomial transform of {1, 3, 5, 11, 21, 43, ...}, see A001045. Binomial transform is {1, 5, 21, 85, 341, 1365, ...}, see A002450. - Philippe Deléham, Jul 22 2005
For n >= 2, a(n) is equal to the number of functions f:{1,2,...,n+1}->{1,2,3} such that for fixed, different x_1, x_2 in {1,2,...,n} and fixed y_1, y_2 in {1,2,3} we have f(x_1) <> y_1 and f(x_2) <> y_2. - Milan Janjic, Apr 19 2007
Equals row sums of triangle A143865. - Gary W. Adamson, Sep 04 2008
Equals INVERT transform of the odd integers = 1/(1 - x - 3x^2 - 5x^3 - ...). - Gary W. Adamson, Jul 27 2009
a(n) is the number of generalized compositions of n+1 when there are 2 *i-1 different types of the part i, (i=1,2,...). - Milan Janjic, Aug 26 2010
Number of length-n strings of 4 letters with no two adjacent letters identical. The general case (strings of r letters) is the sequence with g.f. (1+x)/(1-(r-1)*x). - Joerg Arndt, Oct 11 2012
The sequence is the INVERTi transform of A015448: (1, 5, 21, 89, 377, ...). - Gary W. Adamson, Aug 06 2016
Let D(m) = {d(m,i)}, i = 1..q, denote the set of the q divisors of a number m, and consider s1(m) and s2(m) the sums of the divisors that are congruent to 1 and 2 (mod 3) respectively. For n > 0, the sequence a(n) lists the numbers m such that s1(m) = 5 and s2(m) = 2. - Michel Lagneau, Feb 09 2017
a(n) is the number of quaternary sequences of length n such that no two consecutive terms have distance 2. - David Nacin, May 31 2017
Also the number of maximal cliques in the n-Sierpinski gasket graph. - Eric W. Weisstein, Dec 01 2017
Number of 3-permutations of n elements avoiding the patterns 231, 321. See Bonichon and Sun. - Michel Marcus, Aug 19 2022

			G.f. = 1 + 4*x + 12*x^2 + 36*x^3 + 108*x^4 + 324*x^5 + 972*x^6 + 2916*x^7 + ...

T. D. Noe, Table of n, a(n) for n = 0..200
Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, (an + b)-color compositions, arXiv:1707.07798 [math.CO], 2017.
Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
John Elias, Illustration: Sierpinski Hexagrams
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 305
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 3.
A. M. Nemirovsky et al., Marriage of exact enumeration and 1/d expansion methods: lattice model of dilute polymers, J. Statist. Phys., 67 (1992), 1083-1108.
Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
Eric Weisstein's World of Mathematics, Maximal Clique.
Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph.
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (3).
Index entries for sequences related to trees

Cf. A029653, A143865, column 4 in A265583, A015448.

[1] cat [4*3^(n-1): n in [1..25]]; // Vincenzo Librandi, Dec 11 2012

Maple
```
if n = 0 then 1 else 4*3^(n-1); fi;
```

Join[{1}, 4 3^Range[0, 30]] (* Vladimir Joseph Stephan Orlovsky, Jun 14 2009 *)
Join[{1}, NestList[3# &, 4, 30]] (* Harvey P. Dale, Nov 30 2011 *)
CoefficientList[Series[(1 + x)/(1 - 3 x), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 11 2012 *)
Join[{1}, LinearRecurrence[{3}, {4}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)

A003946[n]:=if n<1 then 1 else 4*3^(n-1)$
makelist(A003946[n],n,0,30); /* Martin Ettl, Oct 29 2012 */

{a(n) = if( n<1, n==0, 4 * 3^(n-1))}; /* Michael Somos, Jun 18 2002 */

Vec((1+x)/(1-3*x) + O(x^100)) \\ Altug Alkan, Dec 07 2015

a(n) = floor(4*3^(n-1)). - Michael Somos, Jun 18 2002
a(n) = Sum_{k=0..n} A029653(n, k)*x^k for x = 2. - Philippe Deléham, Jul 10 2005
The Hankel transform of this sequence is [1,-4,0,0,0,0,0,0,0,0,...]. - Philippe Deléham, Nov 21 2007
a(n + 1) = (((1 + sqrt(-11))/2)^n + ((1 - sqrt(-11))/2)^n)^2 - (((1 + sqrt(-11))/2)^n - ((1 - sqrt(-11))/2)^n)^2. - Raphie Frank, Dec 07 2015
From Mario C. Enriquez, Apr 01 2017: (Start)
(L(a(n+k)) - 1)/a(n) reduces to the form C/a(n-1), where n > 1, k >= 0, L(a(n)) is the a(n)-th Lucas number and C = (L(a(n+k)) - 1)/3.
(L(a(n+k)) - 1)/3 mod (L(a(n)) - 1)/3 = (L(a(n)) - 1)/3 - 1, where n >= 1, k >= 0 and L(a(n)) is the a(n)-th Lucas number. (End)
E.g.f.: (4*exp(3*x) - 1)/3. - Stefano Spezia, Jan 31 2025

Additional comments from Michael Somos, Jun 18 2002

Edited by N. J. A. Sloane, Dec 04 2009

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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

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

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 23.
S. Koshkin, Non-classical linear divisibility sequences ..., Fib. Q., 57 (No. 1, 2019), 68-80. See Table 1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
V. Thébault, Les Récréations Mathématiques. Gauthier-Villars, Paris, 1952, p. 282.

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
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.
Elwyn Berlekamp and Richard K. Guy, Fibonacci Plays Billiards (2003), arXiv:2002.03705 [math.HO], 2020. See p. 5.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 8.
D. W. Boyd, Some integer sequences related to the Pisot sequences, Acta Arithmetica, 34 (1979), 295-305.
D. W. Boyd, Linear recurrence relations for some generalized Pisot sequences, Advances in Number Theory ( Kingston ON, 1991) 333-340, Oxford Sci. Publ., Oxford Univ. Press, New York, 1993.
Latham Boyle and Paul J. Steinhardt, Self-Similar One-Dimensional Quasilattices, arXiv preprint arXiv:1608.08220 [math-ph], 2016.
E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242, Thm. 1, p. 233.
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.
Yixing Fu, E. J. König, J. H. Wilson, Yang-Zhi Chou, and J. H. Pixley, Magic-angle semimetals, arXiv:1809.04604 [cond-mat.str-el], 2018.
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.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 398
Milan Janjic, 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
C. Pita, On s-Fibonomials, J. Int. Seq. 14 (2011) # 11.3.7.
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
Kai Wang, On k-Fibonacci Sequences And Infinite Series List of Results and Examples, 2020.
Shaoxiong (Steven) Yuan, Generalized Identities of Certain Continued Fractions, arXiv:1907.12459 [math.NT], 2019.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,1).

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

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

I:=[0,1]; [n le 2 select I[n] else 4*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 24 2018

A001076:=-1/(-1+4*z+z**2); # conjectured by Simon Plouffe in his 1992 dissertation

Join[{0}, Denominator[Convergents[Sqrt[5], 30]]] (* Harvey P. Dale, Dec 10 2011 *)
a[ n_] := Fibonacci[3*n] / 2; (* Michael Somos, Feb 23 2014 *)
a[ n_] := ((2 + Sqrt[5])^n - (2 - Sqrt[5])^n) /(2 Sqrt[5]) // Simplify; (* Michael Somos, Feb 23 2014 *)
LinearRecurrence[{4, 1}, {0, 1}, 26] (* Jean-François Alcover, Sep 23 2017 *)
a[ n_] := Fibonacci[n, 4]; (* Michael Somos, Nov 02 2021 *)

a(n):=sum(4^(n-1-2*k)*binomial(n-k-1,n-2*k-1),k,0,floor((n)/2));/* Vladimir Kruchinin, Oct 02 2022 */

numlib::fibonacci(3*n)/2 $ n = 0..30; // Zerinvary Lajos, May 09 2008

{a(n) = fibonacci(3*n) / 2}; /* Michael Somos, Aug 11 2009 */

{a(n) = imag( (2 + quadgen(20))^n )}; /* Michael Somos, Feb 23 2014 */

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

[lucas_number1(n,4,-1) for n in range(23)] # Zerinvary Lajos, Apr 23 2009

[fibonacci(3*n)/2 for n in range(23)] # Zerinvary Lajos, May 15 2009

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

A126473 Number of strings over a 5 symbol alphabet with adjacent symbols differing by three or less.

Original entry on oeis.org

1, 5, 23, 107, 497, 2309, 10727, 49835, 231521, 1075589, 4996919, 23214443, 107848529, 501037445, 2327695367, 10813893803, 50238661313, 233396326661, 1084301290583, 5037394142315, 23402480441009, 108722104190981, 505095858086951, 2346549744920747

Offset: 0

R. H. Hardin, Dec 27 2006

[Empirical] a(base,n) = a(base-1,n) + 7^(n-1) for base >= 3n-2; a(base,n) = a(base-1,n) + 7^(n-1)-2 when base = 3n-3.
From Johannes W. Meijer, Aug 01 2010: (Start)
The a(n) represent the number of n-move routes of a fairy chess piece starting in a given side square (m = 2, 4, 6 or 8) on a 3 X 3 chessboard. This fairy chess piece behaves like a king on the eight side and corner squares but on the central square the king goes crazy and turns into a red king, see A179596.
For the side squares the 512 red kings lead to 47 different red king sequences, see the cross-references for some examples.
The sequence above corresponds to four A[5] vectors with the decimal [binary] values 367 [1,0,1,1,0,1,1,1,1], 463 [1,1,1,0,0,1,1,1,1], 487 [1,1,1,1,0,0,1,1,1] and 493 [1,1,1,1,0,1,1,0,1]. These vectors lead for the corner squares to A179596 and for the central square to A179597.
This sequence belongs to a family of sequences with g.f. (1+x)/(1-4*x-k*x^2). Red king sequences that are members of this family are A003947 (k=0), A015448 (k=1), A123347 (k=2), A126473 (k=3; this sequence) and A086347 (k=4). Other members of this family are A000351 (k=5), A001834 (k=-1), A111567 (k=-2), A048473 (k=-3) and A053220 (k=-4)
Inverse binomial transform of A154244. (End)
Equals the INVERT transform of A055099: (1, 4, 14, 50, 178, ...). - Gary W. Adamson, Aug 14 2010
Number of one-sided n-step walks taking steps from {E, W, N, NE, NW}. - Shanzhen Gao, May 10 2011
For n>=1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,2,3,4} containing no subwords 00 and 11. - Milan Janjic, Jan 31 2015

Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Index entries for linear recurrences with constant coefficients, signature (4,3).

Cf. 5 symbol differing by two or less A126392, one or less A057960.
Cf. Red king sequences side squares [numerical value A[5]]: A086347 [495], A179598 [239], A126473 [367], A123347 [335], A179602 [95], A154964 [31], A015448 [327], A152187 [27], A003947 [325], A108981 [11], A007483 [2]. - Johannes W. Meijer, Aug 01 2010
Cf. A055099.

with(LinearAlgebra): nmax:=19; m:=2; A[5]:= [1,0,1,1,0,1,1,1,1]: A:=Matrix([[0,1,0,1,1,0,0,0,0],[1,0,1,1,1,1,0,0,0],[0,1,0,0,1,1,0,0,0],[1,1,0,0,1,0,1,1,0],A[5],[0,1,1,0,1,0,0,1,1],[0,0,0,1,1,0,0,1,0],[0,0,0,1,1,1,1,0,1],[0,0,0,0,1,1,0,1,0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax); # Johannes W. Meijer, Aug 01 2010
# second Maple program:
a:= n-> (M-> M[1,2]+M[2,2])(<<0|1>, <3|4>>^n):
seq(a(n), n=0..24);  # Alois P. Heinz, Jun 28 2021

LinearRecurrence[{4, 3}, {1, 5}, 24] (* Jean-François Alcover, Dec 10 2024 *)

a(n)=([0,1; 3,4]^n*[1;5])[1,1] \\ Charles R Greathouse IV, May 10 2016

From Johannes W. Meijer, Aug 01 2010: (Start)
G.f.: (1+x)/(1-4*x-3*x^2).
a(n) = 4*a(n-1) + 3*a(n-2) with a(0) = 1 and a(1) = 5.
a(n) = ((1+3/sqrt(7))/2)*(A)^(-n) + ((1-3/sqrt(7))/2)*(B)^(-n) with A = (-2 + sqrt(7))/3 and B = (-2-sqrt(7))/3.
Lim_{k->oo} a(n+k)/a(k) = (-1)^(n+1)*A000244(n)/(A015530(n)*sqrt(7)-A108851(n))
(End)
a(n) = A015330(n)+A015330(n+1). - R. J. Mathar, May 09 2023

Edited by Johannes W. Meijer, Aug 10 2010

A049660 a(n) = Fibonacci(6*n)/8.

Original entry on oeis.org

0, 1, 18, 323, 5796, 104005, 1866294, 33489287, 600940872, 10783446409, 193501094490, 3472236254411, 62306751484908, 1118049290473933, 20062580477045886, 360008399296352015, 6460088606857290384, 115921586524134874897, 2080128468827570457762

Offset: 0

Clark Kimberling

For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 18's along the main diagonal, and i's along the superdiagonal and the subdiagonal (i is the imaginary unit). - John M. Campbell, Jul 08 2011
For n >= 2, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,...,17}. - Milan Janjic, Jan 25 2015
10*a(n)^2 = Tri(4)*S(n-1, 18)^2 is the triangular number Tri((T(n, 9) - 1)/2), with Tri, S and T given in A000217, A049310 and A053120. This is instance k = 4 of the k-family of identities given in a comment on A001109. - Wolfdieter Lang, Feb 01 2016
Possible solutions for y in Pell equation x^2 - 80*y^2 = 1. The values for x are given in A023039. - Herbert Kociemba, Jun 05 2022

			a(3) = F(6 * 3) / 8 = F(18) / 8 = 2584 / 8 = 323. - _Indranil Ghosh_, Feb 06 2017

Indranil Ghosh, Table of n, a(n) for n = 0..796 (terms 0..200 from Vincenzo Librandi)
Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, Ellipse Chains and Associated Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
R. Flórez, R. A. Higuita, and A. Mukherjee, Alternating Sums in the Hosoya Polynomial Triangle, Article 14.9.5 Journal of Integer Sequences, Vol. 17 (2014).
Tanya Khovanova, Recursive Sequences
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (18,-1).

Column m=6 of array A028412.
Partial sums of A007805.
Cf. A000045, A001076, A001077, A014445, A014448, A015448, A099843, A134492, A155179.

[Fibonacci(6*n)/8: n in [0..30]]; // G. C. Greubel, Dec 02 2017

with (combinat):seq(fibonacci(2*n,4)/4, n=0..16); # Zerinvary Lajos, Apr 20 2008

Fibonacci[6*Range[0,20]]/8 (* Harvey P. Dale, Nov 23 2011 *)
LinearRecurrence[{18,-1}, {0,1}, 30] (* G. C. Greubel, Dec 02 2017 *)
Table[ChebyshevU[-1 + n, 9], {n, 0, 18}] (* Herbert Kociemba, Jun 05 2022 *)

numlib::fibonacci(6*n)/8 $ n = 0..25; // Zerinvary Lajos, May 09 2008

a(n)=fibonacci(6*n)/8  \\ Charles R Greathouse IV, Apr 17 2012

[lucas_number1(n,18,1) for n in range(0,20)] # Zerinvary Lajos, Jun 25 2008

[fibonacci(6*n)/8 for n in range(0, 17)] # Zerinvary Lajos, May 15 2009

G.f.: x/(1 - 18*x + x^2).
a(n) = A134492(n)/8.
a(n) ~ (1/40)*sqrt(5)*(sqrt(5) + 2)^(2*n). - Joe Keane (jgk(AT)jgk.org), May 15 2002
For all terms k of the sequence, 80*k^2 + 1 is a square. Limit_{n->oo} a(n)/a(n-1) = 8*phi + 5 = 9 + 4*sqrt(5). - Gregory V. Richardson, Oct 14 2002
a(n) = S(n-1, 18) with S(n, x) := U(n, x/2), Chebyshev's polynomials of the second kind. S(-1, x) := 0. See A049310.
a(n) = (((9 + 4*sqrt(5))^n - (9 - 4*sqrt(5))^n))/(8*sqrt(5)).
a(n) = sqrt((A023039(n)^2 - 1)/80) (cf. Richardson comment).
a(n) = 18*a(n-1) - a(n-2). - Gregory V. Richardson, Oct 14 2002
a(n) = A001076(2n)/4.
a(n) = 17*(a(n-1) + a(n-2)) - a(n-3) = 19*(a(n-1) - a(n-2)) + a(n-3). - Mohamed Bouhamida, May 26 2007
a(n+1) = Sum_{k=0..n} A101950(n,k)*17^k. - Philippe Deléham, Feb 10 2012
Product_{n>=1} (1 + 1/a(n)) = (1/2)*(2 + sqrt(5)). - Peter Bala, Dec 23 2012
Product_{n>=2} (1 - 1/a(n)) = (2/9)*(2 + sqrt(5)). - Peter Bala, Dec 23 2012
a(n) = (1/32)*(F(6*n + 3) - F(6*n - 3)).
Sum_{n>=1} 1/(4*a(n) + 1/(4*a(n))) = 1/4. Compare with A001906 and A049670. - Peter Bala, Nov 29 2013
From Peter Bala, Apr 02 2015: (Start)
Sum_{n >= 1} a(n)*x^(2*n) = -G(x)*G(-x), where G(x) = Sum_{n >= 1} A001076(n)*x^n.
1 + 4*Sum_{n >= 1} a(n)*x^(2*n) = (1 + F(x))*(1 + F(-x)) = (1 + 2*x*G(x))*(1 - 2*x*G(-x)), where F(x) = Sum_{n >= 1} Fibonacci(3*n + 3)*x^n.
1 + 7*Sum_{n >= 1} a(n)*x^(2*n) = (1 + G(x))*(1 + G(-x)) = (1 + 7*G(x))*(1 + 7*G(-x)).
1 + 12*Sum_{n >= 1} a(n)*x^(2*n) = (1 + 2*G(x))*(1 + 2*G(-x)) = (1 + 6*G(x))*(1 + 6*G(-x)) = (1 + A(x))*(1 + A(-x)), where A(x) = Sum_{n >= 1} Fibonacci(3*n)*x^n is the o.g.f for A014445.
1 + 15*Sum_{n >= 1} a(n)*x^(2*n) = (1 + 5*G(x))*(1 + 5*G(-x)) = (1 + 3*G(x))*(1 + 3*G(-x)) = H(x)*H(-x), where H(x) = Sum_{n >= 0} A155179(n)*x^n.
1 + 16*Sum_{n >= 1} a(n)*x^(2*n) = (1 + 4*G(x))*(1 + 4*G(-x)) = (1 + 2* Sum_{n >= 1} Fibonacci(3*n - 1)*x^n)*(1 + 2* Sum_{n >= 1} Fibonacci(3*n - 1)*(-x)^n) = (1 + 2* Sum_{n >= 1} Fibonacci(3*n + 1)*x^n)*(1 + 2* Sum_{n >= 1} Fibonacci(3*n + 1)*(-x)^n).
1 + 20*Sum_{n >= 1} a(n)*x^(2*n) = (1 + Sum_{n >= 1} Lucas(3*n)*x^n)*(1 + Sum_{n >= 1} Lucas(3*n)*(-x)^n).
1 - 5*Sum_{n >= 1} a(n)*x^(2*n) = (1 + Sum_{n >= 1} A001077(n+1)*x^n)*(1 + Sum_{n >= 1} A001077(n+1)*(-x)^n).
1 - 9*Sum_{n >= 1} a(n)*x^(2*n) = (1 - G(x))*(1 - G(-x)) = (1 + 9*G(x))*(1 + 9*G(-x)).
1 - 16*Sum_{n >= 1} a(n)*x^(2*n) = (1 + 2*Sum_{n >= 1} A099843(n)*x^n)*(1 + 2*Sum_{n >= 1} A099843(n)*(-x)^n).
1 - 20*Sum_{n >= 1} a(n)*x^(2*n) = (1 - 2*G(x))*(1 - 2*G(-x)) = (1 + 10*G(x))*(1 + 10*G(-x)).
(End)

Chebyshev and other comments from Wolfdieter Lang, Nov 08 2002

A001077 Numerators of continued fraction convergents to sqrt(5).

Original entry on oeis.org

1, 2, 9, 38, 161, 682, 2889, 12238, 51841, 219602, 930249, 3940598, 16692641, 70711162, 299537289, 1268860318, 5374978561, 22768774562, 96450076809, 408569081798, 1730726404001, 7331474697802, 31056625195209

Offset: 0

N. J. A. Sloane

a(2*n+1) with b(2*n+1) := A001076(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 5*b^2 = -1.
a(2*n) with b(2*n) := A001076(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 5*b^2 = +1 (see Emerson reference).
Bisection: a(2*n) = T(n,9) = A023039(n), n >= 0 and a(2*n+1) = 2*S(2*n, 2*sqrt(5)) = A075796(n+1), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.
From Greg Dresden, May 21 2023: (Start)
For n >= 2, 8*a(n) is the number of ways to tile this T-shaped figure of length n-1 with four colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 8*a(6) = 23112 different tilings.
    _
   || _  
   |||_|||
   |_|
(End)

			1  2  9  38  161  (A001077)
-, -, -, --, ---, ...
0  1  4  17   72  (A001076)
1 + 2*x + 9*x^2 + 38*x^3 + 161*x^4 + 682*x^5 + 2889*x^6 + 12238*x^7 + ... - _Michael Somos_, Aug 11 2009

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
V. Thébault, Les Récréations Mathématiques, Gauthier-Villars, Paris, 1952, p. 282.

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
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.
Tanya Khovanova, Recursive Sequences
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
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A000032, A001076, A023039, A049629, A052924, A078343, A164581, A179237, A180148, A329723, A374439.

I:=[1, 2]; [n le 2 select I[n] else 4*Self(n-1) + Self(n-2): n in [1..30]]; // G. C. Greubel, Dec 19 2017

A001077:=(-1+2*z)/(-1+4*z+z**2); # conjectured by Simon Plouffe in his 1992 dissertation
with(combinat): a:=n->fibonacci(n+1, 4)-2*fibonacci(n, 4): seq(a(n), n=0..30); # Zerinvary Lajos, Apr 04 2008

LinearRecurrence[{4, 1}, {1, 2}, 30]
Join[{1},Numerator[Convergents[Sqrt[5],30]]] (* Harvey P. Dale, Mar 23 2016 *)
CoefficientList[Series[(1-2*x)/(1-4*x-x^2), {x, 0, 30}], x] (* G. C. Greubel, Dec 19 2017 *)
LucasL[3*Range[0,30]]/2 (* Rigoberto Florez, Apr 03 2019 *)
a[ n_] := LucasL[n, 4]/2; (* Michael Somos, Nov 02 2021 *)

{a(n) = fibonacci(3*n) / 2 + fibonacci(3*n - 1)}; /* Michael Somos, Aug 11 2009 */

a(n)=if(n<2,n+1,my(t=4);for(i=1,n-2,t=4+1/t);numerator(2+1/t)) \\ Charles R Greathouse IV, Dec 05 2011

x='x+O('x^30); Vec((1-2*x)/(1-4*x-x^2)) \\ G. C. Greubel, Dec 19 2017

[lucas_number2(n,4,-1)/2 for n in range(0, 30)] # Zerinvary Lajos, May 14 2009

G.f.: (1-2*x)/(1-4*x-x^2).
a(n) = 4*a(n-1) + a(n-2), a(0)=1, a(1)=2.
a(n) = ((2 + sqrt(5))^n + (2 - sqrt(5))^n)/2.
a(n) = A014448(n)/2.
Limit_{n->infinity} a(n)/a(n-1) = phi^3 = 2 + sqrt(5). - Gregory V. Richardson, Oct 13 2002
a(n) = ((-i)^n)*T(n, 2*i), with T(n, x) Chebyshev's polynomials of the first kind A053120 and i^2 = -1.
Binomial transform of A084057. - Paul Barry, May 10 2003
E.g.f.: exp(2x)cosh(sqrt(5)x). - Paul Barry, May 10 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)*5^k*2^(n-2k). - Paul Barry, Nov 15 2003
a(n) = 4*a(n-1) + a(n-2) when n > 2; a(1) = 1, a(2) = 2. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 25 2004
a(n) = A001076(n+1) - 2*A001076(n) = A097924(n) - A015448(n+1); a(n+1) = A097924(n) + 2*A001076(n) = A097924(n) + 2(A048876(n) - A048875(n)). - Creighton Dement, Mar 19 2005
a(n) = F(3*n)/2 + F(3*n-1) where F() = Fibonacci numbers A000045. - Gerald McGarvey, Apr 28 2007
a(n) = A000032(3*n)/2.
For n >= 1: a(n) = (1/2)*Fibonacci(6*n)/Fibonacci(3*n) and a(n) = integer part of (2 + sqrt(5))^n. - Artur Jasinski, Nov 28 2011
a(n) = Sum_{k=0..n} A201730(n,k)*4^k. - Philippe Deléham, Dec 06 2011
a(n) = A001076(n) + A015448(n). - R. J. Mathar, Jul 06 2012
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(5*k-4)/(x*(5*k+1) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 27 2013
a(n) is the (1,1)-entry of the matrix W^n with W=[2, sqrt(5); sqrt(5), 2]. - Carmine Suriano, Mar 21 2014
From Rigoberto Florez, Apr 03 2019: (Start)
a(n) = A099919(n) + A049651(n) if n > 0.
a(n) = 1 + Sum_{k=0..n-1} L(3*k + 1) if n >= 0, L(n) = n-th Lucas number (A000032). (End)
From Christopher Hohl, Aug 22 2021: (Start)
For n >= 2, a(2n-1) = A079962(6n-9) + A079962(6n-3).
For n >= 1, a(2n) = sqrt(20*A079962(6n-3)^2 + 1). (End)
a(n) = Sum_{k=0..n-2} A168561(n-2,k)*4^k + 2 * Sum_{k=0..n-1} A168561(n-1,k)*4^k, n>0. - R. J. Mathar, Feb 14 2024
a(n) = 4^n*Sum_{k=0..n} A374439(n, k)*(-1/4)^k. - Peter Luschny, Jul 26 2024
From Peter Bala, Jul 08 2025: (Start)
The following series telescope:
Sum_{n >= 1} 1/(a(n) + 5*(-1)^(n+1)/a(n)) = 3/8, since 1/(a(n) + 5*(-1)^(n+1)/a(n)) = b(n) - b(n+1), where b(n) = (1/4) * (a(n) + a(n-1)) / (a(n)*a(n-1)).
Sum_{n >= 1} (-1)^(n+1)/(a(n) + 5*(-1)^(n+1)/a(n)) = 1/8, since 1/(a(n) + 5*(-1)^(n+1)/a(n)) = c(n) + c(n+1), where c(n) = (1/4) * (a(n) - a(n-1)) / (a(n)*a(n-1)). (End)

Chebyshev comments from Wolfdieter Lang, Jan 10 2003

A014445 Even Fibonacci numbers; or, Fibonacci(3*n).

Original entry on oeis.org

0, 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, 3524578, 14930352, 63245986, 267914296, 1134903170, 4807526976, 20365011074, 86267571272, 365435296162, 1548008755920, 6557470319842, 27777890035288, 117669030460994, 498454011879264, 2111485077978050

Offset: 0

Mohammad K. Azarian

a(n) = 3^n*b(n;2/3) = -b(n;-2), but we have 3^n*a(n;2/3) = F(3n+1) = A033887 and a(n;-2) = F(3n-1) = A015448, where a(n;d) and b(n;d), n=0,1,...,d, denote the so-called delta-Fibonacci numbers (the argument "d" of a(n;d) and b(n;d) is abbreviation of the symbol "delta") defined by the following equivalent relations: (1 + d*((sqrt(5) - 1)/2))^n = a(n;d) + b(n;d)*((sqrt(5) - 1)/2) equiv. a(0;d)=1, b(0;d)=0, a(n+1;d) = a(n;d) + d*b(n;d), b(n+1;d) = d*a(n;d) + (1-d)b(n;d) equiv. a(0;d)=a(1;d)=1, b(0;1)=0, b(1;d)=d, and x(n+2;d) + (d-2)*x(n+1;d) + (1-d-d^2)*x(n;d) = 0 for every n=0,1,...,d, and x=a,b equiv. a(n;d) = Sum_{k=0..n} C(n,k)*F(k-1)*(-d)^k, and b(n;d) = Sum_{k=0..n} C(n,k)*(-1)^(k-1)*F(k)*d^k equiv. a(n;d) = Sum_{k=0..n} C(n,k)*F(k+1)*(1-d)^(n-k)*d^k, and b(n;d) = Sum_{k=1..n} C(n;k)*F(k)*(1-d)^(n-k)*d^k. The sequences a(n;d) and b(n;d) for special values d are connected with many known sequences: A000045, A001519, A001906, A015448, A020699, A033887, A033889, A074872, A081567, A081568, A081569, A081574, A081575, A163073 (see also the papers of Witula et al.). - Roman Witula, Jul 12 2012
For any odd k, Fibonacci(k*n) = sqrt(Fibonacci((k-1)*n) * Fibonacci((k+1)*n) + Fibonacci(n)^2). - Gary Detlefs, Dec 28 2012
The ratio of consecutive terms approaches the continued fraction 4 + 1/(4 + 1/(4 +...)) = A098317. - Hal M. Switkay, Jul 05 2020

			G.f. = 2*x + 8*x^2 + 34*x^3 + 144*x^4 + 610*x^5 + 2584*x^6 + 10946*x^7 + ...

Arthur T. Benjamin and Jennifer J. Quinn,, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, id. 232.

T. D. Noe, Table of n, a(n) for n = 0..200
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38 (2012), pp. 1871-1876 (See Corollary 1 (v)).
H. H. Ferns, Problem B-115, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 5, No. 2 (1967), p. 202; Identities for F_{kn} and L{kn}, Solution to Problem B-115 by Stanley Rabinowitz, ibid., Vol. 6, No. 1 (1968), pp. 92-93.
Ira M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq., Vol. 16 (2013), Article 13.4.5.
Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Math., Vol. 15 (2017), pp. 477-485.
Tanya Khovanova, Recursive Sequences.
Ron Knott, Mathematics of the Fibonacci Series.
Bahar Kuloğlu, Engin Özkan, and Marin Marin, Fibonacci and Lucas Polynomials in n-gon, An. Şt. Univ. Ovidius Constanţa (Romania 2023) Vol. 31, No 2, 127-140.
Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
Roberto Tauraso, Some Congruences for Central Binomial Sums Involving Fibonacci and Lucas Numbers, JIS 19 (2016) # 16.5.4
Roman Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math., Vol. 3, No. 2 (2009), pp. 310-329, MR2555042.
Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Math., Vol. 46 (2013), pp. 15-27.
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A000032, A000045, A001076, A049310, A111125.
Cf. A001519, A001906, A015448, A020699, A033887, A033889, A074872, A081567, A081568, A081569, A081574, A081575, A098317, A163073.
First differences of A099919.
Third column of array A102310.

[Fibonacci(3*n): n in [0..30]]; // Vincenzo Librandi, Apr 18 2011

a:= n-> (<<0|1>, <1|1>>^(3*n))[1,2]:
seq(a(n), n=0..25);  # Alois P. Heinz, Feb 03 2023

Table[Fibonacci[3n], {n,0,30}] (* Stefan Steinerberger, Apr 07 2006 *)
LinearRecurrence[{4,1},{0,2},30] (* Harvey P. Dale, Nov 14 2021 *)
Table[ SeriesCoefficient[2*x/(1 - 4*x - x^2), {x, 0, n}], {n, 0, 20}] (* Nikolaos Pantelidis, Feb 02 2023 *)

numlib::fibonacci(3*n) $ n = 0..30; // Zerinvary Lajos, May 09 2008

a(n)=fibonacci(3*n) \\ Charles R Greathouse IV, Oct 25 2012

[fibonacci(3*n) for n in range(0, 30)] # Zerinvary Lajos, May 15 2009

a(n) = Sum_{k=0..n} binomial(n, k)*F(k)*2^k. - Benoit Cloitre, Oct 25 2003
From Lekraj Beedassy, Jun 11 2004: (Start)
a(n) = 4*a(n-1) + a(n-2), with a(-1) = 2, a(0) = 0.
a(n) = 2*A001076(n).
a(n) = (F(n+1))^3 + (F(n))^3 - (F(n-1))^3. (End)
a(n) = Sum_{k=0..floor((n-1)/2)} C(n, 2*k+1)*5^k*2^(n-2*k). - Mario Catalani (mario.catalani(AT)unito.it), Jul 22 2004
a(n) = Sum_{k=0..n} F(n+k)*binomial(n, k). - Benoit Cloitre, May 15 2005
O.g.f.: 2*x/(1 - 4*x - x^2). - R. J. Mathar, Mar 06 2008
a(n) = second binomial transform of (2,4,10,20,50,100,250). This is 2* (1,2,5,10,25,50,125) or 5^n (offset 0): *2 for the odd numbers or *4 for the even. The sequences are interpolated. Also a(n) = 2*((2+sqrt(5))^n - (2-sqrt(5))^n)/sqrt(20). - Al Hakanson (hawkuu(AT)gmail.com), May 02 2009
a(n) = 3*F(n-1)*F(n)*F(n+1) + 2*F(n)^3, F(n)=A000045(n). - Gary Detlefs, Dec 23 2010
a(n) = (-1)^n*3*F(n) + 5*F(n)^3, n >= 0. See the D. Jennings formula given in a comment on A111125, where also the reference is given. - Wolfdieter Lang, Aug 31 2012
With L(n) a Lucas number, F(3*n) = F(n)*(L(2*n) + (-1)^n) = (L(3*n+1) + L(3*n-1))/5 starting at n=1. - J. M. Bergot, Oct 25 2012
a(n) = sqrt(Fibonacci(2*n)*Fibonacci(4*n) + Fibonacci(n)^2). - Gary Detlefs, Dec 28 2012
For n > 0, a(n) = 5*F(n-1)*F(n)*F(n+1) - 2*F(n)*(-1)^n. - J. M. Bergot, Dec 10 2015
a(n) = -(-1)^n * a(-n) for all n in Z. - Michael Somos, Nov 15 2018
a(n) = (5*Fibonacci(n)^3 + Fibonacci(n)*Lucas(n)^2)/4 (Ferns, 1967). - Amiram Eldar, Feb 06 2022
a(n) = 2*i^(n-1)*S(n-1,-4*i), with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(-1, x) = 0. From the simplified trisection formula. - Gary Detlefs and Wolfdieter Lang, Mar 04 2023
E.g.f.: 2*exp(2*x)*sinh(sqrt(5)*x)/sqrt(5). - Stefano Spezia, Jun 03 2024
a(n) = 2*F(n) + 3*Sum_{k=0..n-1} F(3*k)*F(n-k). - Yomna Bakr and Greg Dresden, Jun 10 2024

A055830 Triangle T read by rows: diagonal differences of triangle A037027.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 3, 3, 1, 0, 5, 7, 4, 1, 0, 8, 15, 12, 5, 1, 0, 13, 30, 31, 18, 6, 1, 0, 21, 58, 73, 54, 25, 7, 1, 0, 34, 109, 162, 145, 85, 33, 8, 1, 0, 55, 201, 344, 361, 255, 125, 42, 9, 1, 0, 89, 365, 707, 850, 701, 413, 175, 52, 10, 1, 0, 144, 655, 1416, 1918, 1806, 1239, 630, 236, 63, 11, 1, 0

Offset: 0

Clark Kimberling, May 28 2000

Or, coefficients of a generalized Lucas-Pell polynomial read by rows. - Philippe Deléham, Nov 05 2006

Equals A046854(shifted) * Pascal's triangle; where A046854 is shifted down one row and "1" inserted at (0,0). - Gary W. Adamson, Dec 24 2008

			Triangle begins:
   1
   1,   0
   2,   1,   0
   3,   3,   1,   0
   5,   7,   4,   1,   0
   8,  15,  12,   5,   1,   0
  13,  30,  31,  18,   6,   1,  0
  21,  58,  73,  54,  25,   7,  1, 0
  34, 109, 162, 145,  85,  33,  8, 1, 0
  55, 201, 344, 361, 255, 125, 42, 9, 1, 0
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Clark Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40 (4) (2002) 328-338, Example 3D.

Left-hand columns include A000045, A023610.
Right-hand columns include A055831, A055832, A055833, A055834, A055835, A055836, A055837, A055838, A055839, A055840.
Row sums: A001333 (numerators of continued fraction convergents to sqrt(2)).
Cf. A122075 (another version).
Cf. A046854. - Gary W. Adamson, Dec 24 2008

function T(n,k)
  if k lt 0 or k gt n then return 0;
  elif k eq 0 then return Fibonacci(n+1);
  elif n eq 1 and k eq 1 then return 0;
  else return T(n-1,k-1) + T(n-1,k) + T(n-2,k);
  end if; return T; end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 21 2020

with(combinat);
T:= proc(n, k) option remember;
      if k<0 or k>n then 0
    elif k=0 then fibonacci(n+1)
    elif n=1 and k=1 then 0
    else T(n-1, k-1) + T(n-1, k) + T(n-2, k)
      fi; end:
seq(seq(T(n, k), k=0..n), n=0..12); # G. C. Greubel, Jan 21 2020

T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==0, Fibonacci[n+1], If[n==1 && k==1, 0, T[n-1, k-1] + T[n-1, k] + T[n-2, k]]]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Dec 19 2017 *)

T(n,k) = if(k<0 || k>n, 0, if(k==0, fibonacci(n+1), if(n==1 && k==1, 0, T(n-1, k-1) + T(n-1, k) + T(n-2, k) )));
for(n=0,12, for(k=0, n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jan 21 2020

@CachedFunction
def T(n, k):
    if (k<0 or k>n): return 0
    elif (k==0): return fibonacci(n+1)
    elif (n==1 and k==1): return 0
    else: return T(n-1, k-1) + T(n-1, k) + T(n-2, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jan 21 2020

G.f.: (1-y*z) / (1-y*(1+y+z)).
T(i, j) = R(i-j, j), where R(0, 0)=1, R(0, j)=0 for j >= 1, R(1, j)=1 for j >= 0, R(i, j) = Sum_{k=0..j} (R(i-2, k) + R(i-1, k)) for i >= 1, j >= 1.
Sum_{k=0..n} x^k*T(n,k) = A039834(n-2), A000012(n), A000045(n+1), A001333(n), A003688(n), A015448(n), A015449(n), A015451(n), A015453(n), A015454(n), A015455(n), A015456(n), A015457(n) for x= -2,-1,0,1,2,3,4,5,6,7,8,9,10. - Philippe Deléham, Oct 22 2006
Sum_{k=0..floor(n/2)} T(n-k,k) = A011782(n). - Philippe Deléham, Oct 22 2006
Triangle T(n,k), 0 <= k <= n, given by [1, 1, -1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 05 2006
T(n,0) = Fibonacci(n+1) = A000045(n+1). Sum_{k=0..n} T(n,k) = A001333(n). T(n,k)=0 if k > n or if k < 0, T(0,0)=1, T(1,1)=0, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-2,k). - Philippe Deléham, Nov 05 2006

Edited by Ralf Stephan, Jan 12 2005

cp's OEIS Frontend

A117647 a(2n) = A014445(n), a(2n+1) = A015448(n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A093123 Third binomial transform of Fibonacci(3n-1) (A015448).

Views

Author

Keywords

Links

Crossrefs

Formula

A003946 Expansion of (1+x)/(1-3*x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Maxima

MuPAD

PARI

PARI

PARI

Sage

Sage

Formula

A126473 Number of strings over a 5 symbol alphabet with adjacent symbols differing by three or less.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A049660 a(n) = Fibonacci(6*n)/8.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs