A033887 -id:A033887 - cp's OEIS frontend

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

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

A015448 a(0) = 1, a(1) = 1, and a(n) = 4*a(n-1) + a(n-2) for n >= 2.

Original entry on oeis.org

1, 1, 5, 21, 89, 377, 1597, 6765, 28657, 121393, 514229, 2178309, 9227465, 39088169, 165580141, 701408733, 2971215073, 12586269025, 53316291173, 225851433717, 956722026041, 4052739537881, 17167680177565, 72723460248141, 308061521170129, 1304969544928657, 5527939700884757

Offset: 0

Olivier Gérard

If one deletes the leading 0 in A084326, takes the inverse binomial transform, and adds a(0)=1 in front, one obtains this sequence here. - Al Hakanson (hawkuu(AT)gmail.com), May 02 2009
For n >= 1, row sums of triangle
  m |k=0     1     2     3     4     5     6     7
====+=============================================
  0 |  1
  1 |  1     4
  2 |  1     4    16
  3 |  1     8    16    64
  4 |  1     8    48    64   256
  5 |  1    12    48   256   256  1024
  6 |  1    12    96   256  1280  1024  4096
  7 |  1    16    96   640  1280  6144  4096 16384
which is triangle for numbers 4^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012
a(n) = a(n;-2) = 3^n*Sum_{k=0..n} binomial(n,k)*F(k+1)*(-2/3)^k, where a(n;d), n=0,1,...,d, denotes the delta-Fibonacci numbers defined in comments to A000045 (see also the papers of Witula et al.). We note that (see A033887) F(3n+1) = 3^n*a(n,2/3) = Sum_{k=0..n} binomial(n,k)*F(k-1)*(-2/3)^k, which implies F(3n+1) + 3^(-n)*a(n) = Sum_{k=0..n} binomial(n,k)*L(k)*(-2/3)^k, where L(k) denotes the k-th Lucas number. - Roman Witula, Jul 12 2012
a(n+1) is (for n >= 0) the number of length-n strings of 5 letters {0,1,2,3,4} with no two adjacent nonzero letters identical. The general case (strings of L letters) is the sequence with g.f. (1+x)/(1-(L-1)*x-x^2). - Joerg Arndt, Oct 11 2012
Starting with offset 1 the sequence is the INVERT transform of (1, 4, 4*3, 4*3^2, 4*3^3, ...); i.e., of A003946: (1, 4, 12, 36, 108, ...). - Gary W. Adamson, Aug 06 2016
a(n+1) equals the number of quinary sequences of length n such that no two consecutive terms differ by 3. - David Nacin, May 31 2017

T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt, Matters Computational (The Fxtbook), pp. 313-315.
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 (vi)).
Gary Detlefs and Wolfdieter Lang, Improved Formula for the Multi-Section of the Linear Three-Term Recurrence Sequence, arXiv:2304.12937 [math.CO], 2023.
Amelia Gilson, Hadley Killen, Steven J. Miller, Nadia Razek, Joshua M. Siktar, and Liza Sulkin, Zeckendorf's Theorem Using Indices in an Arithmetic Progression, arXiv:2005.10396 [math.NT], 2020.
Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Math. 15 (2017), 477-485.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
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
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.
Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Math. 46 (2013), 15-27.
R. Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009) 310-329, MR2555042
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A001076, A147722 (INVERT transform), A109499 (INVERTi transform), A154626 (Binomial transform), A086344 (inverse binomial transform), A003946, A049310.

Cf. A000032, A000045, A014445, A014448, A033887, A046854, A055830, A055870, A084326, A167808.

[Fibonacci(3*n-1): n in [0..40]]; // Vincenzo Librandi, Jul 04 2015

with(combinat): a:=n->fibonacci(n,4)-3*fibonacci(n-1,4): seq(a(n), n=1..23); # Zerinvary Lajos, Apr 04 2008

Fibonacci/@(3*Range[0,30]-1) (* Vladimir Joseph Stephan Orlovsky, Mar 01 2010 *)
LinearRecurrence[{4,1},{1,1},30] (* Harvey P. Dale, May 15 2019 *)

a[0]:1$
a[1]:1$
a[n]:=4*a[n-1]+a[n-2]$
A015448(n):=a[n]$
makelist(A015448(n),n,0,30); /* Martin Ettl, Nov 03 2012 */

a(n) = fibonacci(3*n-1); \\ Altug Alkan, Dec 10 2015

a(n) = Fibonacci(3n-1) = ( (1+sqrt(5))*(2-sqrt(5))^n - (1-sqrt(5))*(2+sqrt(5))^n )/ (2*sqrt(5)).
O.g.f.: (1-3*x)/(1-4*x-x^2). - Len Smiley, Dec 09 2001
a(n) = Sum_{k=0..n} 3^k*A055830(n,k). - Philippe Deléham, Oct 18 2006
a(n) = upper left term in the 2 X 2 matrix [1,2; 2,3]^n. - Gary W. Adamson, Mar 02 2008
[a(n), A001076(n)] = [1,4; 1,3]^n * [1,0]. - Gary W. Adamson, Mar 21 2008
a(n) = A167808(3*n-1) for n > 0. - Reinhard Zumkeller, Nov 12 2009
a(n) = Fibonacci(3n+1) mod Fibonacci(3n), n > 0.
a(n) = (A000032(3*n)-Fibonacci(3*n))/2 = (A014448(n)-A014445(n))/2.
For n >= 2, a(n) = F_n(4) + F_(n+1)(4), where F_n(x) is a Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i)*x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
a(n) = A001076(n+1) - 3*A001076(n). - R. J. Mathar, Jul 12 2012
From Gary Detlefs and Wolfdieter Lang, Aug 20 2012: (Start)
a(n) = (5*F(n)^3 + 5*F(n-1)^3 + 3*(-1)^n*F(n-2))/2,
a(n) = (F(n+1)^3 + 2*F(n)^3 - F(n-2)^3)/2, n >= 0, with F(-1) = 1 and F(-2) = -1. Second line from first one with 3*(-1)^n* F(n-2) = F(n-1)^3 - 4*F(n-2)^3 - F(n-3)^3 (in Koshy's book, p. 89, 32. (with a - sign) and 33. For the Koshy reference see A000045) and the F^3 recurrence (see row n=4 of A055870, or Koshy p. 87, 1.). First line from the preceding R. J. Mathar formula with F(3*n) = 5*F(n)^3 + 3*(-1)^n*F(n) (Koshy p. 89, 46.) and the above mentioned formula, Koshy's 32. and 33., with n -> n+2 in order to eliminate F(n+1)^3. (End)
For n > 0, a(n) = L(n-1)*L(n)*F(n) + F(n+1)*(-1)^n with L(n)=A000032(n). - J. M. Bergot, Dec 10 2015
For n > 1, a(n)^2 is the denominator of continued fraction [4,4,...,4, 6, 4,4,...4], which has n-1 4's before, and n-1 4's after, the middle 6. - Greg Dresden, Sep 18 2019
From Gary Detlefs and Wolfdieter Lang, Mar 06 2023: (Start)
a(n) = A001076(n) + A001076(n-1), with A001076(-1) = 1. See the R. J. Mathar formula above.
a(n+1) = i^n*(S(n-1,-4*i) - i*S(n-2,-4*i)), for n >= 0, with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. From the simplified Fibonacci trisection formula for {F(3*n+2)}_{n>=0}. (End)
a(n) = Sum_{k=0..n} A046854(n-1,k)*4^k. - R. J. Mathar, Feb 10 2024
E.g.f.: exp(2*x)*(5*cosh(sqrt(5)*x) - sqrt(5)*sinh(sqrt(5)*x))/5. - Stefano Spezia, Jun 03 2024

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

A005054 a(0) = 1; a(n) = 4*5^(n-1) for n >= 1.

Original entry on oeis.org

1, 4, 20, 100, 500, 2500, 12500, 62500, 312500, 1562500, 7812500, 39062500, 195312500, 976562500, 4882812500, 24414062500, 122070312500, 610351562500, 3051757812500, 15258789062500, 76293945312500, 381469726562500, 1907348632812500, 9536743164062500

Offset: 0

N. J. A. Sloane

Consider the sequence formed by the final n decimal digits of {2^k: k >= 0}. For n=1 this is 1, 2, 4, 8, 6, 2, 4, ... (A000689) with period 4. For any n this is periodic with period a(n). Cf. A000855 (n=2), A126605 (n=3, also n=4). - N. J. A. Sloane, Jul 08 2022
First differences of A000351.
Length of repeating cycle of the final n+1 digits in Fermat numbers. - Lekraj Beedassy, Robert G. Wilson v and Eric W. Weisstein, Jul 05 2004
Number of n-digit endings for a power of 2 whose exponent is greater than or equal to n. - J. Lowell
For n>=1, a(n) is equal to the number of functions f:{1,2,...,n}->{1,2,3,4,5} such that for a fixed x in {1,2,...,n} and a fixed y in {1,2,3,4,5} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007
Equals INVERT transform of A033887: (1, 3, 13, 55, 233, ...) and INVERTi transform of A001653: (1, 5, 29, 169, 985, 5741, ...). - Gary W. Adamson, Jul 22 2010
a(n) = (n+1) terms in the sequence (1, 3, 4, 4, 4, ...) dot (n+1) terms in the sequence (1, 1, 4, 20, 100, ...). Example: a(4) = 500 = (1, 3, 4, 4, 4) dot (1, 1, 4, 20, 100) = (1 + 3 + 16, + 80 + 400), where (1, 3, 16, 80, 400, ...) = A055842, finite differences of A005054 terms. - Gary W. Adamson, Aug 03 2010
a(n) is the number of compositions of n when there are 4 types of each natural number. - Milan Janjic, Aug 13 2010
Apart from the first term, number of monic squarefree polynomials over F_5 of degree n. - Charles R Greathouse IV, Feb 07 2012
For positive integers that can be either of two colors (designated by ' or ''), a(n) is the number of compositions of 2n that are cardinal palindromes; that is, palindromes that only take into account the cardinality of the numbers and not their colors. Example: 3', 2'', 1', 1, 2', 3'' would count as a cardinal palindrome. - Gregory L. Simay, Mar 01 2020
a(n) is the length of the period of the sequence Fibonacci(k) (mod 5^(n-1)) (for n>1) and the length of the period of the sequence Lucas(k) (mod 5^n) (Kramer and Hoggatt, 1972). - Amiram Eldar, Feb 02 2022

T. Koshy, "The Ends Of A Fermat Number", pp. 183-4 Journal Recreational Mathematics, vol. 31(3) 2002-3 Baywood NY.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 458.
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets.
Judy Kramer and V. E. Hoggatt, Jr., Special Cases of Fibonacci Periodicity (Part 1, Part 2), The Fibonacci Quarterly, Vol. 10, No. 5 (1972), pp. 519-522, 530.
Eric Weisstein's World of Mathematics, Fermat Number.
Index entries for linear recurrences with constant coefficients, signature (5).

Cf. A000010, A000032, A000045, A000351, A000215, A055842.
Cf. A001653, A033887. - Gary W. Adamson, Jul 22 2010
See also A000689, A000855, A126605, A216099, A216164. - N. J. A. Sloane, Jul 08 2022

[(4*5^n+0^n)/5: n in [0..30]]; // Vincenzo Librandi, Jun 08 2013

a:= n-> ceil(4*5^(n-1)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 08 2022

CoefficientList[Series[(1 - x) / (1 - 5 x), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 08 2013 *)

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

a(n) = (4*5^n + 0^n) / 5. - R. J. Mathar, May 13 2008
G.f.: (1-x)/(1-5*x). - Philippe Deléham, Nov 02 2009
G.f.: 1/(1 - 4*Sum_{k>=1} x^k).
a(n) = 5*a(n-1) for n>=2. - Vincenzo Librandi, Dec 31 2010
a(n) = phi(5^n) = A000010(A000351(n)).
E.g.f.: (4*exp(5*x)+1)/5. - Paul Barry, Apr 20 2003
a(n + 1) = (((1 + sqrt(-19))/2)^n + ((1 - sqrt(-19))/2)^n)^2 - (((1 + sqrt(-19))/2)^n - ((1 - sqrt(-19))/2)^n)^2. - Raphie Frank, Dec 07 2015

Better definition from R. J. Mathar, May 13 2008

Edited by N. J. A. Sloane, Jul 08 2022

A048876 a(n) = 4*a(n-1) + a(n-2); a(0)=1, a(1)=7.

Original entry on oeis.org

1, 7, 29, 123, 521, 2207, 9349, 39603, 167761, 710647, 3010349, 12752043, 54018521, 228826127, 969323029, 4106118243, 17393796001, 73681302247, 312119004989, 1322157322203, 5600748293801, 23725150497407, 100501350283429, 425730551631123, 1803423556807921

Offset: 0

Barry E. Williams

Generalized Pell equation with second term of 7.

T. D. Noe, Table of n, a(n) for n = 0..200
M. Bicknell, A Primer on the Pell Sequence and related sequences, Fibonacci Quarterly, Vol. 13, No. 4, 1975, pp. 345-349.
L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Pellian Representations, Fib. Quart. Vol. 10, No. 5, (1972), pp. 449-488.
Tanya Khovanova, Recursive Sequences
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A001076, A001077, A015448, A033887.

with(combinat): a:=n->3*fibonacci(n-1,4)+fibonacci(n,4): seq(a(n), n=1..16); # Zerinvary Lajos, Apr 04 2008

f[n_] := Block[{s = Sqrt@ 5}, Simplify[((1 + s)(2 + s)^n + (1 - s)(2 - s)^n)/2]]; (* Or *)
f[n_] := Fibonacci[3 n + 3] - Fibonacci[3 n - 1]; (* Or *)
f[n_] := Mod[ Fibonacci[3n + 7], Fibonacci[3n + 3]]; Array[f, 22, 0]
a[n_] := 4a[n - 1] + a[n - 2]; a[0] = 1; a[1] = 7; Array[a, 22, 0] (* Or *)
CoefficientList[ Series[(1 + 3x)/(1 - 4x - x^2), {x, 0, 21}], x] (* Robert G. Wilson v *)
LinearRecurrence[{4,1},{1,7},30] (* Harvey P. Dale, Jun 13 2015 *)
Table[LucasL[3*n + 1], {n, 0, 20}] (* Rigoberto Florez, Apr 04 2019 *)

Vec((1+3*x)/(1-4*x-x^2) + O(x^30)) \\ Altug Alkan, Oct 07 2015

G.f.: (1+3*x)/(1-4*x-x^2). - Philippe Deléham, Nov 03 2008
a(n) = ((1+sqrt(5))*(2+sqrt(5))^n + (1-sqrt(5))*(2-sqrt(5))^n )/2.
a(n) = A000032(3*n+1). - Thomas Baruchel, Nov 26 2003
From Gary Detlefs, Mar 06 2011: (Start)
a(n) = Fibonacci(3*n+7) mod Fibonacci(3*n+3), n > 0.
a(n) = Fibonacci(3*n+3) - Fibonacci(3*n-1). (End)
a(n) = A001076(n+1)+3*A001076(n). - R. J. Mathar, Oct 22 2013
a(n) = 5*F(2*n)*F(n+1) - L(n-1)*(-1)^n. - J. M. Bergot, Mar 22 2016
a(n) = Sum_{k=0..n} binomial(n,k)*5^floor((k+1)/2)*2^(n-k). - Tony Foster III, Sep 03 2017

A104934 Expansion of (1-x)/(1 - 3x - 2x^2).

Original entry on oeis.org

1, 2, 8, 28, 100, 356, 1268, 4516, 16084, 57284, 204020, 726628, 2587924, 9217028, 32826932, 116914852, 416398420, 1483024964, 5281871732, 18811665124, 66998738836, 238619546756, 849856117940, 3026807447332, 10780134577876, 38394018628292, 136742325040628, 487015012378468, 1734529687216660

Offset: 0

Creighton Dement, Mar 29 2005

A floretion-generated sequence relating A007482, A007483, A007484. Inverse is A046717. Inverse of Fibonacci(3n+1), A033887. Binomial transform is A052984. Inverse binomial transform is A006131. Note: the conjectured relation 2*a(n) = A007482(n) + A007483(n-1) is a result of the FAMP identity dia[I] + dia[J] + dia[K] = jes + fam
Floretion Algebra Multiplication Program, FAMP Code: 1dia[I]tesseq[A*B] with A = - .25'i + .25'j + .25'k - .25i' + .25j' + .25k' - .25'ii' + .25'jj' + .25'kk' + .25'ij' + .25'ik' + .25'ji' + .25'jk' + .25'ki' + .25'kj' - .25e and B = + 'i + i' + 'ji' + 'ki' + e
a(n) is also the number of ways to build a (2 x 2 x n)-tower using (2 X 1 X 1)-bricks (see Exercise 3.15 in Aigner's book). - Vania Mascioni (vmascioni(AT)bsu.edu), Mar 09 2009
a(n) is the number of compositions of n when there are 2 types of 1 and 4 types of other natural numbers. - Milan Janjic, Aug 13 2010
Pisano period lengths: 1, 1, 4, 1, 24, 4, 48, 1, 12, 24, 30, 4, 12, 48, 24, 1,272, 12, 18, 24, ... - R. J. Mathar, Aug 10 2012

M. Aigner, A Course in Enumeration, Springer, 2007, p.103.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
Index entries for linear recurrences with constant coefficients, signature (3,2)

Cf. A006131, A007482 (partial sums), A007483, A007484, A033887, A046717, A052984, A055099, A104935, A122542.

# Following the Pari implementation.
function a(n)
   F = BigInt[0 1; 2 3]
   Fn = F^n * [1; 2]
   Fn[1, 1]
end # Peter Luschny, Jan 06 2019

m:=35; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1 - x)/(1 - 3*x - 2*x^2)); // Vincenzo Librandi, Jul 13 2018

a := proc(n) option remember; `if`(n < 2, [1, 2][n+1], (3*a(n-1) + 2*a(n-2))) end:
seq(a(n), n=0..28); # Peter Luschny, Jan 06 2019

LinearRecurrence[{3, 2}, {1, 2}, 40] (* Vincenzo Librandi, Jul 13 2018 *)
CoefficientList[Series[(1-x)/(1-3x-2x^2),{x,0,40}],x] (* Harvey P. Dale, May 02 2019 *)

a(n)=([0,1; 2,3]^n*[1;2])[1,1] \\ Charles R Greathouse IV, Jun 20 2015

[(i*sqrt(2))^(n-1)*(i*sqrt(2)*chebyshev_U(n, -3*i/(2*sqrt(2))) - chebyshev_U(n-1, -3*i/(2*sqrt(2))) ) for n in (0..40)] # G. C. Greubel, Jun 27 2021

Define A007483(-1) = 1. Then 2*a(n) = A007482(n) + A007483(n-1) (conjecture);
  a(n+2) = 4*A007484(n) (thus 8*A007484(n) = A007482(n+2) + A007483(n+1));
  a(n+1) = 2*A055099(n);
  a(n+2) - a(n+1) - a(n) = A007484(n+1) - A007484(n).
a(0)=1, a(1)=2, a(n) = 3*a(n-1) + 2*a(n-2) for n > 1. - Philippe Deléham, Sep 19 2006
a(n) = Sum_{k=0..n} 2^k*A122542(n,k). - Philippe Deléham, Oct 08 2006
a(n) = ((17+sqrt(17))/34)*((3+sqrt(17))/2)^n + ((17-sqrt(17))/34)*((3-sqrt(17))/2)^n. - Richard Choulet, Nov 19 2008
a(n) = 2*a(n-1) + 4*Sum_{k=0..n-2} a(k) for n > 0. - Vania Mascioni (vmascioni(AT)bsu.edu), Mar 09 2009
G.f.: (1-x)/(1-3*x-2*x^2). - M. F. Hasler, Jul 12 2018
a(n) = (i*sqrt(2))^(n-1)*( i*sqrt(2)*ChebyshevU(n, -3*i/(2*sqrt(2))) - ChebyshevU(n-1, -3*i/(2*sqrt(2))) ). - G. C. Greubel, Jun 27 2021
E.g.f.: exp(3*x/2)*(sqrt(17)*cosh(sqrt(17)*x/2) + sinh(sqrt(17)*x/2))/sqrt(17). - Stefano Spezia, May 24 2024

A048875 Generalized Pellian with second term of 6.

Original entry on oeis.org

1, 6, 25, 106, 449, 1902, 8057, 34130, 144577, 612438, 2594329, 10989754, 46553345, 197203134, 835365881, 3538666658, 14990032513, 63498796710, 268985219353, 1139439674122, 4826743915841, 20446415337486, 86612405265785, 366896036400626, 1554196550868289

Offset: 0

Barry E. Williams

			G.f. = 1 + 6*x + 25*x^2 + 106*x^3 + 449*x^4 + 1902*x^5 + 8057*x^6 + 34130*x^7 + ...

T. D. Noe, Table of n, a(n) for n = 0..200
M. Bicknell, A Primer on the Pell Sequence and related sequences, Fibonacci Quarterly, Vol. 13, No. 4, 1975, pp. 345-349.
L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Pellian Representations, Fib. Quart. Vol. 10, No. 5, (1972), pp. 449-488.
Tanya Khovanova, Recursive Sequences
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A015448, A001076, A001077, A033887, A134418, A097924, A374439.

with(combinat): a:=n->2*fibonacci(n-1,4)+fibonacci(n,4): seq(a(n), n=1..17); # Zerinvary Lajos, Apr 04 2008

LinearRecurrence[{4,1},{1,6},40] (* Harvey P. Dale, Nov 30 2011 *)
a[ n_] := (4 I ChebyshevT[ n + 1, -2 I] - 3 ChebyshevT[ n, -2 I]) I^n / 5; (* Michael Somos, Feb 23 2014 *)
a[ n_] := If[ n < 0, SeriesCoefficient[ (1 + 6 x) / (1 + 4 x - x^2), {x, 0, -n}], SeriesCoefficient[ (1 + 2 x) / (1 - 4 x - x^2), {x, 0, n}]]; (* Michael Somos, Feb 23 2014 *)

a[0]:1$ a[1]:6$ a[n]:=4*a[n-1]+a[n-2]$ makelist(a[n], n, 0, 30); /* Martin Ettl, Nov 03 2012 */

{a(n) = ( 4*I*polchebyshev( n+1, 1, -2*I) - 3*polchebyshev( n, 1, -2*I)) * I^n / 5}; /* Michael Somos, Feb 23 2014 */

{a(n) = if( n<0, polcoeff( (1 + 6*x) / (1 + 4*x - x^2) + x * O(x^-n), -n), polcoeff( (1 + 2*x) / (1 - 4*x - x^2) + x * O(x^n), n))}; \\ Michael Somos, Feb 23 2014

a(n) = ((4+sqrt(5))*(2+sqrt(5))^n - (4-sqrt(5))*(2-sqrt(5))^n)*sqrt(5)/2.
a(n) = 4a(n-1) + a(n-2); a(0)=1, a(1)=6.
Binomial transform of A134418: (1, 5, 14, 48, 152, ...). - Gary W. Adamson, Nov 23 2007
G.f.: (1+2*x)/(1-4*x-x^2). - Philippe Deléham, Nov 03 2008
a(-1 - n) = (-1)^n * A097924(n) for all n in Z. - Michael Somos, Feb 23 2014
a(n) = A001076(n+1) + 2*A001076(n). - R. J. Mathar, Sep 11 2019
a(n) = 4^n*Sum_{k=0..n} A374439(n, k)*(1/4)^k. - Peter Luschny, Jul 26 2024

Corrected by T. D. Noe, Nov 07 2006

A066258 a(n) = Fibonacci(n)^2 * Fibonacci(n+1).

Original entry on oeis.org

0, 1, 2, 12, 45, 200, 832, 3549, 14994, 63580, 269225, 1140624, 4831488, 20466953, 86698690, 367262700, 1555747893, 6590256856, 27916771136, 118257348165, 500946152850, 2122041977276, 8989114033297, 38078498156832, 161303106585600, 683290924620625, 2894466804871682

Offset: 0

Len Smiley, Dec 09 2001

From Feryal Alayont, Apr 27 2023: (Start)
a(n) is the number of edge covers of a caterpillar graph with spine P_(3n-2), one pendant attached at vertex n counting from the left end of the spine and another pendant at vertex 2n-1. The caterpillar graph for n=3 is as follows:
        *     *
        |     |
  *--*--*--*--*--*--*
           v
Each pendant edge must be included in an edge cover. Every vertex except v is then incident with at least one edge. Therefore, of the remaining four edges in the spine, only two in the middle have restrictions. At least one of those two has to be in the edge cover to ensure v is incident with one edge in the edge cover, leaving us with 3*2*2 total edge covers. (End)

Harry J. Smith, 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.
David Zeitlin, Generating Functions for Products of Recursive Sequences, Transactions A.M.S., 116, Apr. 1965, p. 304.
Index entries for linear recurrences with constant coefficients, signature (3,6,-3,-1).

Cf. A000045, A033887, A056570, A065563, A066259.

First differences of A001655.

[Fibonacci(n)^2*Fibonacci(n+1): n in [0..30]]; // G. C. Greubel, Feb 12 2024

#[[1]]^2 #[[2]]&/@Partition[Fibonacci[Range[0,30]],2,1] (* or *) LinearRecurrence[ {3,6,-3,-1},{0,1,2,12},30] (* Harvey P. Dale, Jul 28 2018 *)

a(n) = { fibonacci(n)^2 * fibonacci(n+1) } \\ Harry J. Smith, Feb 07 2010

[fibonacci(n)^2*fibonacci(n+1) for n in range(31)] # G. C. Greubel, Feb 12 2024

O.g.f.: x*(1-x) / ( (1-4*x-x^2)*(1+x-x^2) ).
a(n) = second term from right in M^(n+1) * [1 0 0 0], where M = the 4 X 4 upper Pascal's triangular matrix [1 3 3 1 / 1 2 1 0 / 1 1 0 0 / 1 0 0 0]. E.g., a(3) = 45 since M^4 * [1 0 0 0] = [125 75 45 27] where 125 = A056570(5), 75 = A066259(4) and 27 = A056570(4). - Gary W. Adamson, Oct 31 2004
a(n) = (1/5)*(Fibonacci(3n+1) - (-1)^n*Fibonacci(n+2)). - Ralf Stephan, Jul 26 2005
a(n) = 3*a(n-1) + 6*a(n-2) - 3*a(n-3) - a(n-4). - Zak Seidov, May 07 2015

A103134 a(n) = Fibonacci(6n+4).

Original entry on oeis.org

3, 55, 987, 17711, 317811, 5702887, 102334155, 1836311903, 32951280099, 591286729879, 10610209857723, 190392490709135, 3416454622906707, 61305790721611591, 1100087778366101931, 19740274219868223167, 354224848179261915075, 6356306993006846248183

Offset: 0

Creighton Dement, Jan 24 2005

Gives those numbers which are Fibonacci numbers in A103135.
Generally, for any sequence where a(0)= Fibonacci(p), a(1) = F(p+q) and Lucas(q)*a(1) +- a(0) = F(p+2q), then a(n) = L(q)*a(n-1) +- a(n-2) generates the following Fibonacci sequence: a(n) = F(q(n)+p). So for this sequence, a(n) = 18*a(n-1) - a(n-2) = F(6n+4): q=6, because 18 is the 6th Lucas number (L(0) = 2, L(1)=1); F(4)=3, F(10)=55 and F(16)=987 (F(0)=0 and F(1)=1). See Lucas sequence A000032. This is a special case where a(0) and a(1) are increasing Fibonacci numbers and Lucas(m)*a(1) +- a(0) is another Fibonacci. - Bob Selcoe, Jul 08 2013
a(n) = x + y where x and y are solutions to x^2 = 5*y^2 - 1. (See related sequences with formula below.) - Richard R. Forberg, Sep 05 2013

Colin Barker, Table of n, a(n) for n = 0..750
Tanya Khovanova, Recursive Sequences
Index entries for linear recurrences with constant coefficients, signature (18,-1).
Index entries for sequences related to Chebyshev polynomials.

Subsequence of A033887.
Cf. A000032, A000045, A001906, A001519, A015448, A014445, A033888, A033889, A033890, A033891, A049310, A049660, A102312, A099100, A134490, A134491, A134492, A134493, A134494, A134495, A103134, A134497, A134498, A134499, A134500, A134501, A134502, A134503, A134504.
Cf. A103135.

[Fibonacci(6*n +4): n in [0..100]]; // Vincenzo Librandi, Apr 17 2011

Table[Fibonacci[6n+4], {n, 0, 30}]
LinearRecurrence[{18,-1},{3,55},20] (* Harvey P. Dale, Mar 29 2023 *)
Table[ChebyshevU[3*n+1, 3/2], {n, 0, 20}] (* Vaclav Kotesovec, May 27 2023 *)

a(n)=fibonacci(6*n+4) \\ Charles R Greathouse IV, Feb 05 2013

G.f.: (x+3)/(x^2-18*x+1).
a(n) = 18*a(n-1) - a(n-2) for n>1; a(0)=3, a(1)=55. - Philippe Deléham, Nov 17 2008
a(n) = A007805(n) + A075796(n), as follows from comment above. - Richard R. Forberg, Sep 05 2013
a(n) = ((15-7*sqrt(5)+(9+4*sqrt(5))^(2*n)*(15+7*sqrt(5))))/(10*(9+4*sqrt(5))^n). - Colin Barker, Jan 24 2016
a(n) = S(3*n+1, 3) = 3*S(n,18) + S(n-1,18), with the Chebyshev S polynomials (A049310), S(-1, x) = 0, and S(n, 18) = A049660(n+1). - Wolfdieter Lang, May 08 2023

Edited by N. J. A. Sloane, Aug 10 2010

A082761 Trinomial transform of the Fibonacci numbers (A000045).

Original entry on oeis.org

1, 4, 20, 104, 544, 2848, 14912, 78080, 408832, 2140672, 11208704, 58689536, 307302400, 1609056256, 8425127936, 44114542592, 230986743808, 1209462292480, 6332826779648, 33159111507968, 173623361929216, 909103725543424, 4760128905543680, 24924358531088384, 130505635564355584

Offset: 0

Emanuele Munarini, May 21 2003

Hankel transform of Sum_{k=0..n} (-1)^k*C(2k, k) (see A054108). - Paul Barry, Jan 13 2009
Hankel transform of A046748. - Paul Barry, Apr 14 2010
For positive n, a(n) equals the permanent of the (2n) X (2n) tridiagonal matrix with sqrt(2)'s along the three central diagonals. - John M. Campbell, Jul 12 2011
The limiting ratio is: Lim_{n -> oo} a(n)/a(n-1) = 1 + phi^3. - Bob Selcoe, Mar 18 2014
Invert transform of A052984. Invert transform is A083066. Binomial transform of A033887. Binomial transform is A163073. - Michael Somos, May 26 2014

			a(5) = 2848 = 5*(544) + 4 + 20 + 104.
G.f. = 1 + 4*x + 20*x^2 + 104*x^3 + 544*x^4 + 2848*x^5 + 14912*x^6 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..150
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.
Index entries for linear recurrences with constant coefficients, signature (6,-4).

Cf. A000045, A001519, A027907, A033887, A046748, A052984, A054108, A069429, A083066, A147703, A163073.

[2^n * Fibonacci(2*n+1): n in [0..40]]; // Vincenzo Librandi, Jul 15 2011

a[ n_] := 2^n Fibonacci[ 2 n + 1]; (* Michael Somos, May 26 2014 *)
a[ n_] := If[ n < 0, SeriesCoefficient[ (2 - x) / (4 - 6 x + x^2), {x, 0, -1 - n}], SeriesCoefficient[ (1 - 2 x) / (1 - 6 x + 4 x^2), {x, 0, n}]]; (* Michael Somos, Oct 22 2017 *)
LinearRecurrence[{6,-4},{1,4},30] (* Harvey P. Dale, Jul 11 2014 *)

a(n)=fibonacci(2*n+1)<Charles R Greathouse IV, Jul 15 2011

{a(n) = if( n<0, n = -1 - n; 2^(-1-2*n), 1) * polcoeff( (1 - 2*x) / (1 - 6*x + 4*x^2) + x * O(x^n), n)}; /* Michael Somos, Oct 22 2017 */

[2^n*fibonacci(2*n+1) for n in range(41)] # G. C. Greubel, Jul 28 2024

a(n) = Sum_{k=0..2*n} A027907(n, k)*A000045(k+1).
From Paul Barry, Jul 16 2003: (Start)
Third binomial transform of (1, 1, 5, 5, 25, 25, ....).
a(n) = ((1+sqrt(5))(3+sqrt(5))^n-(1-sqrt(5))*(3-sqrt(5))^n)/(2*sqrt(5)). (End)
From R. J. Mathar, Nov 04 2008: (Start)
G.f.: (1-2*x)/(1-6*x+4*x^2).
a(n) = 6*a(n-1) - 4*a(n-2). (End)
a(n) = Sum_{k=0..n} A147703(n,k)*3^k. - Philippe Deléham, Nov 14 2008
For n>=2: a(n) = 5*a(n-1) + Sum_{i=1..n-2} a(i). - Bob Selcoe, Mar 18 2014
a(n) = a(-1-n) * 2^(2*n+1) for all n in Z. - Michael Somos, Mar 18 2014
a(n) = 2^n*Fibonacci(2*n+1), or 2^n*A001519(n+1). - Bob Selcoe, May 25 2014
From Michael Somos, May 26 2014: (Start)
a(n) - a(n-1) = A069429(n).
a(n+1) * a(n-1) - a(n)^2 = 4^n.
G.f.: 1 / (1 - 4*x / (1 - x / (1 - x))). (End)
E.g.f.: exp(3*x)*(5*cosh(sqrt(5)*x) + sqrt(5)*sinh(sqrt(5)*x))/5. - Stefano Spezia, May 24 2024

cp's OEIS Frontend

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

A015448 a(0) = 1, a(1) = 1, and a(n) = 4*a(n-1) + a(n-2) for n >= 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

MuPAD

PARI

Sage

Formula

A005054 a(0) = 1; a(n) = 4*5^(n-1) for n >= 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A048876 a(n) = 4*a(n-1) + a(n-2); a(0)=1, a(1)=7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A104934 Expansion of (1-x)/(1 - 3x - 2x^2).