A099919 -id:A099919 - cp's OEIS frontend

A000071 a(n) = Fibonacci(n) - 1.

0, 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168, 63245985, 102334154

Offset: 1

N. J. A. Sloane

a(n) is the number of allowable transition rules for passing from one change to the next (on n-1 bells) in the English art of bell-ringing. This is also the number of involutions in the symmetric group S_{n-1} which can be represented as a product of transpositions of consecutive numbers from {1, 2, ..., n-1}. Thus for n = 6 we have a(6) from (12), (12)(34), (12)(45), (23), (23)(45), (34), (45), for instance. See my 1983 Math. Proc. Camb. Phil. Soc. paper. - Arthur T. White, letter to N. J. A. Sloane, Dec 18 1986
Number of permutations p of {1, 2, ..., n-1} such that max|p(i) - i| = 1. Example: a(4) = 2 since only the permutations 132 and 213 of {1, 2, 3} satisfy the given condition. - Emeric Deutsch, Jun 04 2003 [For a(5) = 4 we have 2143, 1324, 2134 and 1243. - Jon Perry, Sep 14 2013]
Number of 001-avoiding binary words of length n-3. a(n) is the number of partitions of {1, ..., n-1} into two blocks in which only 1- or 2-strings of consecutive integers can appear in a block and there is at least one 2-string. E.g., a(6) = 7 because the enumerated partitions of {1, 2, 3, 4, 5} are 124/35, 134/25, 14/235, 13/245, 1245/3, 145/23, 125/34. - Augustine O. Munagi, Apr 11 2005
Numbers for which only one Fibonacci bit-representation is possible and for which the maximal and minimal Fibonacci bit-representations (A104326 and A014417) are equal. For example, a(12) = 10101 because 8 + 3 + 1 = 12. - Casey Mongoven, Mar 19 2006
Beginning with a(2), the "Recamán transform" (see A005132) of the Fibonacci numbers (A000045). - Nick Hobson, Mar 01 2007
Starting with nonzero terms, a(n) gives the row sums of triangle A158950. - Gary W. Adamson, Mar 31 2009
a(n+2) is the minimum number of elements in an AVL tree of height n. - Lennert Buytenhek (buytenh(AT)wantstofly.org), May 31 2010
a(n) is the number of branch nodes in the Fibonacci tree of order n-1. A Fibonacci tree of order n (n >= 2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417). - Emeric Deutsch, Jun 14 2010
a(n+3) is the number of distinct three-strand positive braids of length n (cf. Burckel). - Maxime Bourrigan, Apr 04 2011
a(n+1) is the number of compositions of n with maximal part 2. - Joerg Arndt, May 21 2013
a(n+2) is the number of leafs of great-grandparent DAG (directed acyclic graph) of height n. A great-grandparent DAG of height n is a single node for n = 1; for n > 1 each leaf of ggpDAG(n-1) has two child nodes where pairs of adjacent new nodes are merged into single node if and only if they have disjoint grandparents and same great-grandparent. Consequence: a(n) = 2*a(n-1) - a(n-3). - Hermann Stamm-Wilbrandt, Jul 06 2014
2 and 7 are the only prime numbers in this sequence. - Emmanuel Vantieghem, Oct 01 2014
From Russell Jay Hendel, Mar 15 2015: (Start)
We can establish Gerald McGarvey's conjecture mentioned in the Formula section, however we require n > 4. We need the following 4 prerequisites.
(1) a(n) = F(n) - 1, with {F(n)}A000045.%20(2)%20(Binet%20form)%20F(n)%20=%20(d%5En%20-%20e%5En)/sqrt(5)%20with%20d%20=%20phi%20and%20e%20=%201%20-%20phi,%20de%20=%20-1%20and%20d%20+%20e%20=%201.%20It%20follows%20that%20a(n)%20=%20(d(n)%20-%20e(n))/sqrt(5)%20-%201.%20(3)%20To%20prove%20floor(x)%20=%20y%20is%20equivalent%20to%20proving%20that%20x%20-%20y%20lies%20in%20the%20half-open%20interval%20%5B0,%201).%20(4)%20The%20series%20%7Bs(n)%20=%20c1%20x%5En%20+%20c2%7D">{n >= 1} the Fibonacci numbers A000045. (2) (Binet form) F(n) = (d^n - e^n)/sqrt(5) with d = phi and e = 1 - phi, de = -1 and d + e = 1. It follows that a(n) = (d(n) - e(n))/sqrt(5) - 1. (3) To prove floor(x) = y is equivalent to proving that x - y lies in the half-open interval [0, 1). (4) The series {s(n) = c1 x^n + c2}{n >= 1}, with -1 < x < 0, and c1 and c2 positive constants, converges by oscillation with s(1) < s(3) < s(5) < ... < s(6) < s(4) < s(2). If follows that for any odd n, the open interval (s(n), s(n+1)) contains the subsequence {s(t)}_{t >= n + 2}. Using these prerequisites we can analyze the conjecture.
Using prerequisites (2) and (3) we see we must prove, for all n > 4, that d((d^(n-1) - e^(n-1))/sqrt(5) - 1) - (d^n - e^n)/sqrt(5) + 1 + c lies in the interval [0, 1). But de = -1, implying de^(n-1) = -e^(n-2). It follows that we must equivalently prove (for all n > 4) that E(n, c) = (e^(n-2) + e^n)/sqrt(5) + 1 - d + c = e^(n-2) (e^2 + 1)/sqrt(5) + e + c lies in [0, 1). Clearly, for any particular n, E(n, c) has extrema (maxima, minima) when c = 2*(1-d) and c = (1+d)*(1-d). Therefore, the proof is completed by using prerequisite (4). It suffices to verify E(5, 2*(1-d)) = 0, E(6, 2*(1-d)) = 0.236068, E(5, (1-d)*(1+d)) = 0.618034, E(6, (1-d)*(1+d)) = 0.854102, all lie in [0, 1).
(End)
a(n) can be shown to be the number of distinct nonempty matchings on a path with n vertices. (A matching is a collection of disjoint edges.) - Andrew Penland, Feb 14 2017
Also, for n > 3, the lexicographically earliest sequence of positive integers such that {phi*a(n)} is located strictly between {phi*a(n-1)} and {phi*a(n-2)}. - Ivan Neretin, Mar 23 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) <= e(k). [Martinez and Savage, 2.5]
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) <= e(k) and e(i) != e(k). [Martinez and Savage, 2.5]
(End)
Numbers whose Zeckendorf (A014417) and dual Zeckendorf (A104326) representations are the same: alternating digits of 1 and 0. - Amiram Eldar, Nov 01 2019
a(n+2) is the length of the longest array whose local maximum element can be found in at most n reveals. See link to the puzzle by Alexander S. Kulikov. - Dmitry Kamenetsky, Aug 08 2020
a(n+2) is the number of nonempty subsets of {1,2,...,n} that contain no consecutive elements. For example, the a(6)=7 subsets of {1,2,3,4} are {1}, {2}, {3}, {4}, {1,3}, {1,4} and {2,4}. - Muge Olucoglu, Mar 21 2021
a(n+3) is the number of allowed patterns of length n in the even shift (that is, a(n+3) is the number of binary words of length n in which there are an even number of 0s between any two occurrences of 1). For example, a(7)=12 and the 12 allowed patterns of length 4 in the even shift are 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1100, 1110, 1111. - Zoran Sunic, Apr 06 2022
Conjecture: for k a positive odd integer, the sequence {a(k^n): n >= 1} is a strong divisibility sequence; that is, for n, m >= 1, gcd(a(k^n), a(k^m)) = a(k^gcd(n,m)). - Peter Bala, Dec 05 2022
In general, the sum of a second-order linear recurrence having signature (c,d) will be a third-order recurrence having a signature (c+1,d-c,-d). - Gary Detlefs, Jan 05 2023
a(n) is the number of binary strings of length n-2 whose longest run of 1's is of length 1, for n >= 3. - Félix Balado, Apr 03 2025

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 1.
GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 28.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 64.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
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).
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Christian G. Bower, Table of n, a(n) for n = 1..500
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See pp. 6-7.
Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023. See p. 15.
Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
J.-L. Baril and J.-M. Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.
Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See pp. 1-2.
Andrew M. Baxter and Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014.
Serge Burckel, Syntactical methods for braids of three strands, J. Symbolic Comput. 31 (2001), no. 5, 557-564.
Alexander Burstein and Toufik Mansour, Counting occurrences of some subword patterns, arXiv:math/0204320 [math.CO], 2002-2003.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.
Ligia Loretta Cristea, Ivica Martinjak, and Igor Urbiha, Hyperfibonacci Sequences and Polytopic Numbers, arXiv:1606.06228 [math.CO], 2016.
Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013
Emeric Deutsch, Problem Q915, Math. Magazine, vol. 74, No. 5, 2001, p. 404.
Christian Ennis, William Holland, Omer Mujawar, Aadit Narayanan, Frank Neubrander, Marie Neubrander, and Christina Simino, Words in Random Binary Sequences I, arXiv:2107.01029 [math.GM], 2021.
Taras Goy and Mark Shattuck, Toeplitz-Hessenberg determinant formulas for the sequence F_n-1, Online J. Anal. Comb. 19 (2024), no. 19, Paper #1, 27 pp.
Fumio Hazama, Spectra of graphs attached to the space of melodies, Discrete Math., 311 (2011), 2368-2383. See Table 2.1.
Yasuichi Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178. [From _Emeric Deutsch_, Jun 14 2010]
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 384
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 96.
Scott O. Jones and P. Mark Kayll, Constructing Edge-labellings of K_n, with Constant-length Hamilton Cycles, J. Comb. Math. Comb. Comp. (2006) Vol. 57, pp. 83-95. See p. 92.
Tamara Kogan, L. Sapir, A. Sapir, and A. Sapir, The Fibonacci family of iterative processes for solving nonlinear equations, Applied Numerical Mathematics 110 (2016) 148-158.
Alexander S. Kulikov, Find Local Maximum in an Integer Sequence, Puzzling Stack Exchange, 2020.
René Lagrange, Quelques résultats dans la métrique des permutations, Annales Scientifiques de l'Ecole Normale Supérieure, Paris, 79 (1962), 199-241.
D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.
Rui Liu and Feng-Zhen Zhao, On the Sums of Reciprocal Hyperfibonacci Numbers and Hyperlucas Numbers, Journal of Integer Sequences, Vol. 15 (2012), #12.4.5. - From _N. J. A. Sloane_, Oct 05 2012
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
El-Mehdi Mehiri, Saad Mneimneh, and Hacène Belbachir, The Towers of Fibonacci, Lucas, Pell, and Jacobsthal, arXiv:2502.11045 [math.CO], 2025. See p. 12.
Augustine O. Munagi, Set Partitions with Successions and Separations,IJMMS 2005:3 (2005), 451-463.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117 (7), pp. 581-598, 2010.
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
Lara Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012.
Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
Stacey Wagner, Enumerating Alternating Permutations with One Alternating Descent, DePaul Discoveries: Vol. 2: Iss. 1, Article 2.
Hsin-Po Wang and Chi-Wei Chin, On Counting Subsequences and Higher-Order Fibonacci Numbers, arXiv:2405.17499 [cs.IT], 2024. See p. 2.
Arthur T. White, Ringing the changes, Math. Proc. Cambridge Philos. Soc. 94 (1983), no. 2, 203-215.
Peijun Xu, Growth of positive braids semigroups, Journal of Pure and Applied Algebra, 1992.
J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29. (Annotated scanned copy)
Jianqiang Zhao, Uniform Approach to Double Shuffle and Duality Relations of Various q-Analogs of Multiple Zeta Values via Rota-Baxter Algebras, arXiv preprint arXiv:1412.8044 [math.NT], 2014. See Table 9, line 1.
Li-Na Zheng, Rui Liu, and Feng-Zhen Zhao, On the Log-Concavity of the Hyperfibonacci Numbers and the Hyperlucas Numbers, Journal of Integer Sequences, Vol. 17 (2014), #14.1.4.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000032, A000045, A000119, A001611, A001654, A001911, A005968, A005969.
Cf. A006327, A014417, A054761, A081006, A081007, A081008, A081009, A083368.
Cf. A098531, A098532, A098533, A101220, A104326, A105488, A105489, A119282.
Cf. A128697, A157725, A157726, A157727, A157728, A157729, A158950, A167616.
Cf. A001622, A228074.
Antidiagonal sums of array A004070.
Right-hand column 2 of triangle A011794.
Related to sum of Fibonacci(kn) over n. Cf. A099919, A058038, A138134, A053606.
Subsequence of A226538. Also a subsequence of A061489.

a000071 n = a000071_list !! n
a000071_list = map (subtract 1) $ tail a000045_list
-- Reinhard Zumkeller, May 23 2013

[Fibonacci(n)-1: n in [1..60]]; // Vincenzo Librandi, Apr 04 2011

A000071 := proc(n) combinat[fibonacci](n)-1 ; end proc; # R. J. Mathar, Apr 07 2011
a:= n-> (Matrix([[1, 1, 0], [1, 0, 0], [1, 0, 1]])^(n-1))[3, 2]; seq(a(n), n=1..50); # Alois P. Heinz, Jul 24 2008

Fibonacci[Range[40]] - 1 (* or *) LinearRecurrence[{2, 0, -1}, {0, 0, 1}, 40] (* Harvey P. Dale, Aug 23 2013 *)
Join[{0}, Accumulate[Fibonacci[Range[0, 39]]]] (* Alonso del Arte, Oct 22 2017, based on Giorgi Dalakishvili's formula *)

PARI
```
{a(n) = if( n<1, 0, fibonacci(n)-1)};
```

[fibonacci(n)-1 for n in range(1,60)] # G. C. Greubel, Oct 21 2024

a(n) = A000045(n) - 1.
a(0) = -1, a(1) = 0; thereafter a(n) = a(n-1) + a(n-2) + 1.
a(n) = A101220(1, 1, n-2), for n > 1.
G.f.: x^3/((1-x-x^2)*(1-x)). - Simon Plouffe in his 1992 dissertation, dropping initial 0's
a(n) = 2*a(n-1) - a(n-3). - R. H. Hardin, Apr 02 2011
Partial sums of Fibonacci numbers. - Wolfdieter Lang
a(n) = -1 + (A*B^n + C*D^n)/10, with A, C = 5 +- 3*sqrt(5), B, D = (1 +- sqrt(5))/2. - Ralf Stephan, Mar 02 2003
a(1) = 0, a(2) = 0, a(3) = 1, then a(n) = ceiling(phi*a(n-1)) where phi is the golden ratio (1 + sqrt(5))/2. - Benoit Cloitre, May 06 2003
Conjecture: for all c such that 2*(2 - Phi) <= c < (2 + Phi)*(2 - Phi) we have a(n) = floor(Phi*a(n-1) + c) for n > 4. - Gerald McGarvey, Jul 22 2004. This is true provided n > 3 is changed to n > 4, see proof in Comments section. - Russell Jay Hendel, Mar 15 2015
a(n) = Sum_{k = 0..floor((n-2)/2)} binomial(n-k-2, k+1). - Paul Barry, Sep 23 2004
a(n+3) = Sum_{k = 0..floor(n/3)} binomial(n-2*k, k)*(-1)^k*2^(n-3*k). - Paul Barry, Oct 20 2004
a(n+1) = Sum(binomial(n-r, r)), r = 1, 2, ... which is the case t = 2 and k = 2 in the general case of t-strings and k blocks: a(n+1, k, t) = Sum(binomial(n-r*(t-1), r)*S2(n-r*(t-1)-1, k-1)), r = 1, 2, ... - Augustine O. Munagi, Apr 11 2005
a(n) = Sum_{k = 0..n-2} k*Fibonacci(n - k - 3). - Ross La Haye, May 31 2006
a(n) = term (3, 2) in the 3 X 3 matrix [1, 1, 0; 1, 0, 0; 1, 0, 1]^(n-1). - Alois P. Heinz, Jul 24 2008
For n >= 4, a(n) = ceiling(phi*a(n-1)), where phi is the golden ratio. - Vladimir Shevelev, Jul 04 2010
Closed-form without two leading zeros g.f.: 1/(1 - 2*x - x^3); ((5 + 2*sqrt(5))*((1 + sqrt(5))/2)^n + (5 - 2*sqrt(5))*((1 - sqrt(5))/2)^n - 5)/5; closed-form with two leading 0's g.f.: x^2/(1 - 2*x - x^3); ((5 + sqrt(5))*((1 + sqrt(5))/2)^n + (5 - sqrt(5))*((1 - sqrt(5))/2)^n - 10)/10. - Tim Monahan, Jul 10 2011
A000119(a(n)) = 1. - Reinhard Zumkeller, Dec 28 2012
a(n) = A228074(n - 1, 2) for n > 2. - Reinhard Zumkeller, Aug 15 2013
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 - x^2)/( x*(4*k + 4 - x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
A083368(a(n+3)) = n. - Reinhard Zumkeller, Aug 10 2014
E.g.f.: 1 - exp(x) + 2*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5). - Ilya Gutkovskiy, Jun 15 2016
a(n) = A000032(3+n) - 1 mod A000045(3+n). - Mario C. Enriquez, Apr 01 2017
a(n) = Sum_{i=0..n-2} Fibonacci(i). - Giorgi Dalakishvili (mcnamara_gio(AT)yahoo.com), Apr 02 2005 [corrected by Doug Bell, Jun 01 2017]
a(n+2) = Sum_{j = 0..floor(n/2)} Sum_{k = 0..j} binomial(n - 2*j, k+1)*binomial(j, k). - Tony Foster III, Sep 08 2017
From Peter Bala, Nov 12 2021: (Start)
a(4*n) = Fibonacci(2*n+1)*Lucas(2*n-1) = A081006(n);
a(4*n+1) = Fibonacci(2*n)*Lucas(2*n+1) = A081007(n);
a(4*n+2) = Fibonacci(2*n)*Lucas(2*n+2) = A081008(n);
a(4*n+3) = Fibonacci(2*n+2)*Lucas(2*n+1) = A081009(n). (End)
G.f.: x^3/((1 - x - x^2)*(1 - x)) = Sum_{n >= 0} (-1)^n * x^(n+3) *( Product_{k = 1..n} (k - x)/Product_{k = 1..n+2} (1 - k*x) )  (a telescoping series). - Peter Bala, May 08 2024
Product_{n>=4} (1 + (-1)^n/a(n)) = 3*phi/4, where phi is the golden ratio (A001622). - Amiram Eldar, Nov 28 2024

Edited by N. J. A. Sloane, Apr 04 2011

A027941 a(n) = Fibonacci(2*n + 1) - 1.

Original entry on oeis.org

0, 1, 4, 12, 33, 88, 232, 609, 1596, 4180, 10945, 28656, 75024, 196417, 514228, 1346268, 3524577, 9227464, 24157816, 63245985, 165580140, 433494436, 1134903169, 2971215072, 7778742048, 20365011073, 53316291172, 139583862444, 365435296161, 956722026040

Offset: 0

Clark Kimberling

Also T(2n+1,n+1), T given by A027935. Also first row of Inverse Stolarsky array.
Third diagonal of array defined by T(i, 1)=T(1, j)=1, T(i, j)=Max(T(i-1, j)+T(i-1, j-1); T(i-1, j-1)+T(i, j-1)). - Benoit Cloitre, Aug 05 2003
Number of Schroeder paths of length 2(n+1) having exactly one up step starting at an even height (a Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis). Schroeder paths are counted by the large Schroeder numbers (A006318). Example: a(1)=4 because among the six Schroeder paths of length 4 only the paths (U)HD, (U)UDD, H(U)D, (U)DH have exactly one U step that starts at an even height (shown between parentheses). - Emeric Deutsch, Dec 19 2004
Also: smallest number not writeable as the sum of fewer than n positive Fibonacci numbers. E.g., a(5)=88 because it is the smallest number that needs at least 5 Fibonacci numbers: 88 = 55 + 21 + 8 + 3 + 1. - Johan Claes, Apr 19 2005 [corrected for offset and clarification by Mike Speciner, Sep 19 2023] In general, a(n) is the sum of n positive Fibonacci numbers as a(n) = Sum_{i=1..n} A000045(2*i). See A001076 when negative Fibonacci numbers can be included in the sum. - Mike Speciner, Sep 24 2023
Except for first term, numbers a(n) that set a new record in the number of Fibonacci numbers needed to sum up to n. Position of records in sequence A007895. - Ralf Stephan, May 15 2005
Successive extremal petal bends beta(n) = a(n-2). See the Ring Lemma of Rodin and Sullivan in K. Stephenson, Introduction to Circle Packing (Cambridge U. P., 2005), pp. 73-74 and 318-321. - David W. Cantrell (DWCantrell(AT)sigmaxi.net)
a(n+1)= AAB^(n)(1), n>=1, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 4=`110`, 12=`1100`, 33=`11000`, 88=`110000`, ..., in Wythoff code. AA(1)=1=a(1) but for uniqueness reason 1=A(1) in Wythoff code. - N. J. A. Sloane, Jun 29 2008
Start with n. Each n generates a sublist {n-1,n-1,n-2,..,1}. Each element of each sublist also generates a sublist. Add numbers in all terms. For example, 3->{2,2,1} and both 2->{1,1}, so a(3) = 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 12. - Jon Perry, Sep 01 2012
For n>0: smallest number such that the inner product of Zeckendorf binary representation and its reverse equals n: A216176(a(n)) = n, see also A189920. - Reinhard Zumkeller, Mar 10 2013
Also, numbers m such that 5*m*(m+2)+1 is a square. - Bruno Berselli, May 19 2014
Also, number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
From Robert K. Moniot, Oct 04 2020: (Start)
Including a(-1):=0, consecutive terms (a(n-1),a(n))=(u,v) or (v,u) give all points on the hyperbola u^2-u+v^2-v-4*u*v=0 with both coordinates nonnegative integers.  Note that this follows from identifying (1,u+1,v+1) with the Markov triple (1,Fibonacci(2n-1),Fibonacci(2n+1)).  See A001519 (comments by Robert G. Wilson, Oct 05 2005, and Wolfdieter Lang, Jan 30 2015).
Let T(n) denote the n-th triangular number. If i, j are any two successive elements of the above sequence then (T(i-1) + T(j-1))/T(i+j-1) = 3/5. (End)

			a(5) = 88 = 2*33 + 12 + 4 + 1 + 5. a(6) = 232 = 2*88 + 33 + 12 + 4 + 1 + 6. - _Jon Perry_, Sep 01 2012
a(4) = 33 counts all nonempty submultisets of the last row: [1][2][3][4], [11][12][13][14][22][23][24][33][34], [111][112][113][122][123][124][133][134][222][223][233][234], [1111][1112][1122][1123][1222][1223][1233][1234]. - _Gus Wiseman_, Feb 10 2015

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

T. D. Noe, Table of n, a(n) for n = 0..200
R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., Vol. 58, No. 2 (2020), 140-142.
Russ Euler and Jawad Sadek, Problem B-912, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 39, No. 1 (2001), p. 85; From a Product to a Sum, Solution to Problem B-912 by Charles K. Cook, ibid., Vol. 39, No. 5 (2001), pp. 468-469.
Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 7.
Clark Kimberling, Interspersions.
Clark Kimberling, Interspersions and dispersions, Proceedings of the American Mathematical Society, 117 (1993) 313-321.
Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
R. J. Mathar, Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings, arXiv:1311.6135 [math.CO], 2013, Table 60 (doubled).
Luis A. Medina and Armin Straub, On multiple and infinite log-concavity, Annals of Combinatorics, Vol. 20, No. 1 (2016), pp. 125-138; arXiv preprint, arXiv:1405.1765 [math.CO], 2014; preprint, 2014.
László Németh, Hyperbolic Pascal pyramid, arXiv:1511.02067 [math.CO], 2015 (2nd line of Table 1 is 3*a(n-2)).
László Németh, Pascal pyramid in the space H^2×R, arXiv:1701.06022 [math.CO], 2016. See bn in Table 1 p.10.
N. J. A. Sloane, Classic Sequences.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,-4,1).

Cf. A000045, A035507, A001906, A006318, A000032.
Related to partial sums of Fibonacci(k*n) over n: A000071, A099919, A058038, A138134, A053606; this sequence is the case k=2.
Cf. A212336 for more sequences with g.f. of the type 1/(1 - k*x + k*x^2 - x^3).
Cf. A000225 (sublist connection).
Cf. A258993 (row sums, n > 0), A000967.

a027941 = (subtract 1) . a000045 . (+ 1) . (* 2)
-- Reinhard Zumkeller, Mar 10 2013

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

with(combinat): seq(fibonacci(2*n+1)-1,n=1..27); # Emeric Deutsch, Dec 19 2004
a:=n->sum(binomial(n+k+1,2*k), k=0..n): seq(a(n), n=-1..26); # Zerinvary Lajos, Oct 02 2007

Table[Fibonacci[2*n+1]-1,{n,0,17}] (* Vladimir Joseph Stephan Orlovsky, Jul 21 2008 *)
LinearRecurrence[{4,-4,1},{0,1,4},40] (* Harvey P. Dale, Aug 17 2021 *)

a(n):=sum(binomial(n+1,k+1)*fib(k),k,0,n); /* Vladimir Kruchinin, Oct 14 2016 */

a(n)=fibonacci(2*n+1)-1 \\ Charles R Greathouse IV, Nov 20 2012

concat(0, Vec(x/((1-x)*(1-3*x+x^2)) + O(x^40))) \\ Colin Barker, Jun 03 2016

a(n) = Sum_{i=1..n} binomial(n+i, n-i). - Benoit Cloitre, Oct 15 2002
G.f.: Sum_{k>=1} x^k/(1-x)^(2*k+1). - Benoit Cloitre, Apr 21 2003
a(n) = Sum_{k=1..n} F(2*k), i.e., partial sums of A001906. - Benoit Cloitre, Oct 27 2003
a(n) = Sum_{k=0..n-1} U(k, 3/2) = Sum_{k=0..n-1} S(k, 3), with S(k, 3) = A001906(k+1). - Paul Barry, Nov 14 2003
G.f.: x/((1-x)*(1-3*x+x^2)) = x/(1-4*x+4*x^2-x^3).
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3) with n>=2, a(-1)=0, a(0)=0, a(1)=1.
a(n) = 3*a(n-1) - a(n-2) + 1 with n>=1, a(-1)=0, a(0)=0.
a(n) = Sum_{k=1..n} F(k)*L(k), where L(k) = Lucas(k) = A000032(k) = F(k-1) + F(k+1). - Alexander Adamchuk, May 18 2007
a(n) = 2*a(n-1) + (Sum_{k=1..n-2} a(k)) + n. - Jon Perry, Sep 01 2012
Sum {n >= 1} 1/a(n) = 3 - phi, where phi = 1/2*(1 + sqrt(5)) is the golden ratio. The ratio of adjacent terms r(n) := a(n)/a(n-1) satisfies the recurrence r(n+1) = (4*r(n) - 1)/(r(n) + 1) for n >= 2. - Peter Bala, Dec 05 2013
a(n) = S(n, 3) - S(n-1, 3) - 1, n >= 0, with Chebyshev's S-polynomials (see A049310), where S(-1, x) = 0. - Wolfdieter Lang, Aug 28 2014
a(n) = -1 + (2^(-1-n)*((3-sqrt(5))^n*(-1+sqrt(5)) + (1+sqrt(5))*(3+sqrt(5))^n)) / sqrt(5). - Colin Barker, Jun 03 2016
E.g.f.: (sqrt(5)*sinh(sqrt(5)*x/2) + 5*cosh(sqrt(5)*x/2))*exp(3*x/2)/5 - exp(x). - Ilya Gutkovskiy, Jun 03 2016
a(n) = Sum_{k=0..n} binomial(n+1,k+1)*Fibonacci(k). - Vladimir Kruchinin, Oct 14 2016
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i+1,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n)*a(n-2) = a(n-1)*(a(n-1) - 1) for n>1. - Robert K. Moniot, Aug 23 2020
a(n) = Sum_{k=1..n} C(2*n-k,k). - Wesley Ivan Hurt, Dec 22 2020
a(n) = Sum_{k = 1..2*n+2} (-1)^k*Fibonacci(k). - Peter Bala, Nov 14 2021
a(n) = (2*cosh((1 + 2*n)*arccsch(2)))/sqrt(5) - 1. - Peter Luschny, Nov 21 2021
a(n) = F(n + (n mod 2)) * L(n+1 - (n mod 2)), where L(n) = A000032(n) and F(n) = A000045(n) (Euler and Sadek, 2001). - Amiram Eldar, Jan 13 2022

More terms from James Sellers, Sep 08 2000

Paul Barry's Nov 14 2003 formula, recurrences and g.f. corrected for offset 0 and index link for Chebyshev polynomials added by Wolfdieter Lang, Aug 28 2014

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

A053606 a(n) = (Fibonacci(6*n+3) - 2)/4.

Original entry on oeis.org

0, 8, 152, 2736, 49104, 881144, 15811496, 283725792, 5091252768, 91358824040, 1639367579960, 29417257615248, 527871269494512, 9472265593285976, 169972909409653064, 3050040103780469184, 54730748958638792256, 982103441151717791432

Offset: 0

N. J. A. Sloane, James Sellers, Jan 20 2000

Define a(1)=0, a(2)=8 with 5*(a(1)^2) + 5*a(1) + 1 = j(1)^2 = 1^2 and 5*(a(2)^2) + 5*a(2) + 1 = j(2)^2 = 19^2. Then a(n) = a(n-2) + 8*sqrt(5*(a(n-1)^2) + 5*a(n-1)+1). Another definition: a(n) such that 5*(a(n)^2) + 5*a(n) + 1 = j(n)^2. - Pierre CAMI, Mar 30 2005
It appears this sequence gives all nonnegative m such that 5*m^2 + 5*m + 1 is a square. - Gerald McGarvey, Apr 03 2005
sqrt(5*a(n)^2+5*a(n)+1) = A049629(n). - Gerald McGarvey, Apr 19 2005
a(n) is such that 5*a(n)^2 + 5*a(n) + 1 = j^2 = the square of A049629(n). Also A049629(n)/a(n) tends to sqrt(5) as n increases. - Pierre CAMI, Apr 21 2005
From Russell Jay Hendel, Apr 25 2015: (Start)
We prove the two McGarvey-CAMI conjectures mentioned at the beginning of the Comments section. Let, as usual, F(n) = A000045(n), the Fibonacci numbers. In the sequel we indicate equations with upper case letters ((A), (B), (C), (D)) for ease of reference.
Then we must prove (A), 5*((F(6*n+3)-2)/4)^2 + 5*((F(6*n+3)-2)/4) + 1 = ((F(6*n+5)-F(6*n+1))/4)^2. Let m = 3*n+1 so that 6*n+1, 6*n+3, and 6*n+5 are 2*m-1, 2*m+1, and 2*m+3 respectively. Define G(m) = F(6*n+3) = F(2*m+1) = A001519(m+1), the bisected Fibonacci numbers. We can now simplify equation (A) by i) multiplying the LHS and RHS by 16, ii) expanding squares, and iii) gathering like terms. This shows proof of (A) equivalent to proving (B), 5*G(m)^2-4 = (G(m+1)-G(m-1))^2.
By Jarden's theorem (D. Jarden, Recurring sequences, 2nd ed. Jerusalem, Riveon Lematematika, (1966)), if {H(n)}{n >=1} is any recursive sequence satisfying (C), H(n)=3H(n-1)-H(n-2), then {H(n)}^2{n >=1} is also a recursive sequence satisfying (D), H(n)^2=8H(n-1)^2-8H(n-2)^2+H(n-3)^2. As noted in the Formula section of A001519, {G(m)}_{m >= 1} satisfies (C).
Proof of (B) is now straightforward. Since {G(m)}{m >=1} satisfies (C), it follows that {G(m)^2}{m >=1} satisfies (D), and therefore, {5G(m)^2-4}_{m >=1} also satisfies (D).
Similarly, since {G(m)}{m >=1} satisfies (C), it follows that both {G(m+1)}{m >=1}, {G(m-1)}{m >=1} and their difference {G(m+1)-G(m-1)}{m >=1} satisfy (C), and therefore {G(m+1)-G(m-1)}^2_{m >=1} satisfies (D).
But then the LHS and RHS of (B) are equal for m=1,2,3 and satisfy the same recursion, (D). Hence the LHS and RHS of (B) are equal for all m. This completes the proof. (End)

G. C. Greubel, Table of n, a(n) for n = 0..790
F. Ellermann, Illustration of binomial transforms
Index entries for linear recurrences with constant coefficients, signature (19,-19,1).

Cf. A049629.

Related to sum of Fibonacci(kn) over n.. A000071, A027941, A099919, A058038, A138134.

List([0..30], n-> (Fibonacci(6*n+3)-2)/4); # G. C. Greubel, May 16 2019

[(Fibonacci(6*n+3)-2)/4: n in [0..30]]; // Vincenzo Librandi, Apr 20 2011

A053606 := proc(n) add(combinat[fibonacci](6*k),k=0..n) ;end proc:
seq(A053606(n),n=0..30) ;

Table[(Fibonacci[6n+3] -2)/4, {n,0,30}] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)

a(n)=fibonacci(6*n+3)\4 \\ Charles R Greathouse IV, Jul 02 2013

[(fibonacci(6*n+3)-2)/4 for n in (0..30)] # G. C. Greubel, May 16 2019

a(n) = 8*A049664(n).
a(n+1) = 9*a(n) + 2*sqrt(5*(2*a(n)+1)^2-1) + 4. - Richard Choulet, Aug 30 2007
G.f.: 8*x/((1-x)*(1-18*x+x^2)). - Richard Choulet, Oct 09 2007
a(n) = 18*a(n-1) - a(n-2) + 8, n > 1. - Gary Detlefs, Dec 07 2010
a(n) = Sum_{k=0..n} A134492(k). - Gary Detlefs, Dec 07 2010
a(n) = (Fibonacci(6*n+6) - Fibonacci(6*n) - 8)/16. - Gary Detlefs, Dec 08 2010

A058038 a(n) = Fibonacci(2n)Fibonacci(2*n+2).

Original entry on oeis.org

0, 3, 24, 168, 1155, 7920, 54288, 372099, 2550408, 17480760, 119814915, 821223648, 5628750624, 38580030723, 264431464440, 1812440220360, 12422650078083, 85146110326224, 583600122205488, 4000054745112195, 27416783093579880, 187917426909946968

Offset: 0

N. J. A. Sloane, Jun 09 2002

Partial sums of A033888, i.e., a(n) = Sum_{k=0..n} Fibonacci(4*k). - Vladeta Jovovic, Jun 09 2002
From Paul Weisenhorn, May 17 2009: (Start)
a(n) is the solution of the 2 equations a(n)+1=A^2 and 5*a(n)+1=B^2
which are equivalent to the Pell equation (10*a(n)+3)^2-5*(A*B)^2=4.
(End)
Numbers a(n) such as a(n)+1 and 5*a(n)+1 are perfect squares. - Sture Sjöstedt, Nov 03 2011

			G.f. = 3*x + 24*x^2 + 168*x^3 + 1155*x^4 + 7920*x^5 + 54288*x^6 + ... - _Michael Somos_, Jan 23 2025

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 29.
H. J. H. Tuenter, Fibonacci summation identities arising from Catalan's identity, Fib. Q., 60:4 (2022), 312-319.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (8,-8,1).

Cf. A033888, A004187, A094874.
Bisection of A059929, A064831 and A080097.
Related to sum of fibonacci(kn) over n; cf. A000071, A099919, A027941, A138134, A053606.

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

fs4:=n->sum(fibonacci(4*k),k=0..n):seq(fs4(n),n=0..21); # Gary Detlefs, Dec 07 2010

Table[Fibonacci[2 n]*Fibonacci[2 n + 2], {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)
Accumulate[Fibonacci[4*Range[0,30]]] (* or *) LinearRecurrence[{8,-8,1},{0,3,24},30] (* Harvey P. Dale, Jul 25 2013 *)

a(n)=fibonacci(2*n)*fibonacci(2*n+2) \\ Charles R Greathouse IV, Jul 02 2013

a(n) = -3/5 + (1/5*sqrt(5)+3/5)*(2*1/(7+3*sqrt(5)))^n/(7+3*sqrt(5)) + (1/5*sqrt(5)-3/5)*(-2*1/(-7+3*sqrt(5)))^n/(-7+3*sqrt(5)). Recurrence: a(n) = 8*a(n-1) - 8*a(n-2) + a(n-3). G.f.: 3*x/(1-7*x+x^2)/(1-x). - Vladeta Jovovic, Jun 09 2002
a(n) = A081068(n) - 1.
a(n) is the next integer from ((3+sqrt(5))*((7+3*sqrt(5))/2)^(n-1)-6)/10. - Paul Weisenhorn, May 17 2009
a(n) = 7*a(n-1) - a(n-2) + 3, n>1. - Gary Detlefs, Dec 07 2010
a(n) = sum_{k=0..n} Fibonacci(4k). - Gary Detlefs, Dec 07 2010
a(n) = (Lucas(4n+2)-3)/5, where Lucas(n)= A000032(n). - Gary Detlefs, Dec 07 2010
a(n) = (1/5)*(Fibonacci(4n+4) - Fibonacci(4n)-3). - Gary Detlefs, Dec 08 2010
a(n) = 3*A092521(n). - R. J. Mathar, Nov 03 2011
a(0)=0, a(1)=3, a(2)=24, a(n) = 8*a(n-1) - 8*a(n-2) + a(n-3). - Harvey P. Dale, Jul 25 2013
a(n) = A001906(n)*A001906(n+1). - R. J. Mathar, Jul 09 2019
Sum_{n>=1} 1/a(n) = 2/(3 + sqrt(5)) = A094874 - 1. - Amiram Eldar, Oct 05 2020
a(n) = a(-1-n) for all n in Z. - Michael Somos, Jan 23 2025

A049652 a(n) = (F(3*n+2) - 1)/4, where F=A000045 (the Fibonacci sequence).

Original entry on oeis.org

0, 1, 5, 22, 94, 399, 1691, 7164, 30348, 128557, 544577, 2306866, 9772042, 41395035, 175352183, 742803768, 3146567256, 13329072793, 56462858429, 239180506510, 1013184884470, 4291920044391, 18180865062035, 77015380292532, 326242386232164, 1381984925221189, 5854182087116921

Offset: 0

Clark Kimberling

From Anant Godbole, Apr 27 2006: (Start)
"a(n) equals the number of 2 by 2 determinants that need to be computed while finding the determinant of an n X n matrix using the method discovered by C. L. Dodgson (Lewis Carroll) in the 19th century.
"To evaluate the determinant of an n X n matrix A, set up a 2 by 2 determinant with entries that equal the determinants of the "northwest, northeast, southwest and southeast" (n-1) by (n-1) submatrices of A. Divide this by determinant of the "central" (n-2) by (n-2) submatrix of A. If the latter is zero, the problem can be fixed by row interchanges.
"The Dodgson method does better than the standard method of using cofactors and an expansion in terms of a row/column if n is 6 or larger. By this we mean that a fewer number of 2 by 2 determinants need to be calculated. Of course, the method of choice is diagonalization which can be achieved in polynomial time. Dodgson's method runs in exponential time, whereas the "standard" method requires one to evaluate n!/2 two by two determinants.
"A beautiful combinatorial proof of Dodgson's result was recently given by Zeilberger and an application is presented by Amdeberhan and Ekhad, where a conjecture of Kuperberg and Propp is proved using Dodgson's formula." (End)
This is the sequence A(0,1;4,1;1)of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010

G. C. Greubel, Table of n, a(n) for n = 0..1000
T. Amdeberhan and S. Ekhad, A condensed condensation proof of a determinant evaluation conjectured by Greg Kuperberg and Jim Propp.
C. L. Dodgson, Condensation of determinants, Proceedings of the Royal Society of London, 15 (1866), 150-155.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Doron Zeilberger, Dodgson's Determinant-Evaluation Rule Proved by Two-Timing Men and Women, Electron. J. Combin. 4 (no. 2, "The Wilf Festschrift") (1997), #R22, 2 pp. (p. 12).
Index entries for linear recurrences with constant coefficients, signature (5,-3,-1).

Cf. A000045, A000071, A048739, A099919.

[(Fibonacci(3*n+2) - 1)/4: n in [0..30]]; // G. C. Greubel, Dec 05 2017

a:= n-> add(fibonacci(i,4), i=0..n): seq(a(n), n=0..22); # Zerinvary Lajos, Mar 20 2008

s = 0; lst = {s}; Do[s += Fibonacci[n, 4]; AppendTo[lst, s], {n, 1, 22, 1}]; lst (* Zerinvary Lajos, Jul 14 2009 *)
LinearRecurrence[{5, -3, -1}, {0, 1, 5}, 30] (* or *) Table[(Fibonacci[ 3*n+2] - 1)/4, {n,0,30}] (* G. C. Greubel, Dec 05 2017 *)

a(n)=fibonacci(3*n+2)\4 \\ Charles R Greathouse IV, Jun 11 2015

a(n) = A099919(n)/2.
From Benoit Cloitre, May 06 2003: (Start)
a(0) = 0, a(1) = 1; a(n) = ceiling(r(4)*a(n-1)) where r(4) = 2+sqrt(5) is the positive root of X^2 = 4*X+1. More generally the sequence a(1) = 1, a(n) = ceiling(r(z)*a(n-1)) where r(z) = (1/2)*(z+sqrt(z^2+4)) is the positive root of X^2 = z*X+1 satisfies the linear recurrence: n > 3, a(n) = (z+1)*a(n-1) - (z-1)*a(n-2) - a(n-3) and the closed form formula: a(n) = floor(t(z)*r(z)^n) where t(z) = (1/(2*z))*(1+(z+2)/sqrt(z^2+4)) is the positive root of z*(z^2+4)*X^2 = (z^2+4)*X+1.
a(0) = 0, a(1) = 1, a(2) = 5, a(3) = 22, a(n) = 5*a(n-1) - 3*a(n-2) - a(n-3); a(n) = floor(t(4)*r(4)^n) where t(4) = (1/8)*(1+3/sqrt(5)) is the positive root of 80*X^2 = 20*X+1. (End)
a(n+2) = 4*a(n+1) + a(n) + 1. - Anant Godbole, Apr 27 2006
G.f.: x/((x-1)*(x^2+4*x-1)). - R. J. Mathar, Nov 23 2007
E.g.f.: exp(x)*(exp(x)*(5*cosh(sqrt(5)*x) + 3*sqrt(5)*sinh(sqrt(5)*x)) - 5)/20. - Stefano Spezia, May 24 2024

cp's OEIS Frontend

A000071 a(n) = Fibonacci(n) - 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A027941 a(n) = Fibonacci(2*n + 1) - 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

MuPAD

PARI

Sage

Formula

A053606 a(n) = (Fibonacci(6*n+3) - 2)/4.

Views

Author

Keywords

Comments

Links

Crossrefs

A058038 a(n) = Fibonacci(2n)Fibonacci(2*n+2).

A015548 Expansion of x/(1 - 5x - 12x^2).