login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A000285
a(0) = 1, a(1) = 4, and a(n) = a(n-1) + a(n-2) for n >= 2.
(Formerly M3246 N1309)
48
1, 4, 5, 9, 14, 23, 37, 60, 97, 157, 254, 411, 665, 1076, 1741, 2817, 4558, 7375, 11933, 19308, 31241, 50549, 81790, 132339, 214129, 346468, 560597, 907065, 1467662, 2374727, 3842389, 6217116, 10059505, 16276621, 26336126, 42612747, 68948873, 111561620, 180510493, 292072113, 472582606
OFFSET
0,2
COMMENTS
a(n-1) = Sum_{k=0..ceiling((n-1)/2)} P(4;n-1-k,k), n >= 1, with a(-1)=3. These are the sums over the SW-NE diagonals in P(4;n,k), the (4,1) Pascal triangle A093561. Observation by Paul Barry, Apr 29 2004. Proof via recursion relations and comparison of inputs. Also SW-NE diagonal sums in the Pascal (1,3) triangle A095660.
In general, for a Fibonacci sequence beginning with 1,b we have a(n) = (2^(-1-n)*((1-sqrt(5))^n*(1+sqrt(5)-2b) + (1+sqrt(5))^n*(-1+sqrt(5)+2b)))/sqrt(5). In this case we have b=4. - Herbert Kociemba, Dec 18 2011
Pisano period lengths: 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 5, 24, 28, 48, 40, 24, 36, 24, 18, 60, ... - R. J. Mathar, Aug 10 2012
a(n) = number of independent vertex subsets (i.e., the Merrifield-Simmons index) of the tree obtained from the path tree P_{n-1} by attaching two pendant edges to one of its endpoints (n >= 2). Example: if n=3, then we have the star tree with edges ab, ac, ad; it has 9 independent vertex subsets: empty, a, b, c, d, bc, cd, bd, bcd.
For n >= 2, the number a(n-1) is the dimension of a commutative Hecke algebra of type D_n with independent parameters. See Theorem 1.4 and Corollary 1.5 in the link "Hecke algebras with independent parameters". - Jia Huang, Jan 20 2019
For n >= 1, a(n) is the number of edge covers of the tadpole graph T_{3,n-1} with T_{3,0} interpreted as just the cycle C_3. Example: If n=2, we have C_3 and P_1 joined by a bridge, which is just the triangle with a pendant, and this graph has 5 edge covers. In general, because of the path portion of the graph, the number of edge covers of T{3,n-1} satisfies the same recurrence as Fibonacci sequence and it starts with 4,5. - Feryal Alayont, Aug 27 2023
Eswarathasan (1978) called these numbers "pseudo-Fibonacci numbers", and proved that 1, 4, and 9 are the only squares in this sequence. If the recurrence is extended to negative indices, then there is only one more square, a(-9) = 81. Eswarathasan (1979) proved that none of the terms (even with negative indices) are twice a square. - Amiram Eldar, Mar 09 2024
For n>2, a(n) + (-1)^ceiling(n/2) is the number of ways to tile this strip of length n-1, with a central staircase, using unit squares and dominoes:
_
_|_|
_______|_|_|_________
|_|_|_|_|_|_|_|_|_|_|_|. - Greg Dresden and Runhe Zhang, Sep 07 2024
REFERENCES
Richard E. Merrifield and Howard E. Simmons, Topological Methods in Chemistry, Wiley, New York, 1989. pp. 131.
Joe Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Ben Adenbaum, Jennifer Elder, Pamela E. Harris, and J. Carlos Martínez Mori, Boolean intervals in the weak Bruhat order of a finite Coxeter group, arXiv:2403.07989 [math.CO], 2024. See pp. 2, 10.
Brandon Avila and Tanya Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.8.5.
Alfred Brousseau, Seeking the lost gold mine or exploring Fibonacci factorizations, Fib. Quart., 3 (1965), 129-130.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 53.
A. Eswarathasan, On Square Pseudo-Fibonacci Numbers, Fibonacci Quarterly, Vol. 16, No. 4 (1978), pp. 310-314.
A. Eswarathasan, On Pseudo-Fibonacci Numbers of the Form 2S^2, Where S is an Integer, Fibonacci Quarterly, Vol. 17, No. 2 (1979), pp. 142-147.
Jia Huang, Hecke algebras with independent parameters, arXiv preprint arXiv:1405.1636 [math.RT], 2014; Journal of Algebraic Combinatorics 43 (2016) 521-551.
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.
José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368 [cs.DM], 2012.
FORMULA
G.f.: (1+3*x)/(1-x-x^2). - Simon Plouffe in his 1992 dissertation
Row sums of A131775 starting (1, 4, 5, 9, 14, 23, ...). - Gary W. Adamson, Jul 14 2007
a(n) = 2*Fibonacci(n) + Fibonacci(n+2). - Zerinvary Lajos, Oct 05 2007
a(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n*sqrt(5)) + (3/2)* ((1+sqrt(5))^(n-1) - (1-sqrt(5))^(n-1))/(2^(n-2)*sqrt(5)). Offset 1. a(3)=5. - Al Hakanson (hawkuu(AT)gmail.com), Jan 14 2009
a(n) = 3*Fibonacci(n+2) - 2*Fibonacci(n+1). - Gary Detlefs, Dec 21 2010
a(n) = A104449(n+1). - Michael Somos, Apr 07 2012
From Michael Somos, May 28 2014: (Start)
a(n) = A101220(3, 0, n+1).
a(n) = A109754(3, n+1).
a(k) = A090888(2, k-1), for k > 0.
a(-1 - n) = (-1)^n * A013655(n).
a(n) = Fibonacci(n) + Lucas(n+1), see Mathematica field. (End)
11*Fibonacci(n+1) = a(n+3) - a(n-2) = 3*a(n-1) + 2*a(n). - Manfred Arens and Michel Marcus, Jul 14 2014
a(n) = (9*F(n) + F(n-3))/2. - J. M. Bergot, Jul 15 2017
a(n-1) = 3 * A000045(n) + A000045(n+1). - R. J. Mathar, Feb 14 2024
EXAMPLE
G.f. = 1 + 4*x + 5*x^2 + 9*x^3 + 14*x^4 + 23*x^5 + 37*x^6 + 60*x^7 + ...
MAPLE
with(combinat):a:=n->2*fibonacci(n)+fibonacci(n+2): seq(a(n), n=0..34);
MATHEMATICA
LinearRecurrence[{1, 1}, {1, 4}, 40] (* or *) Table[(3*LucasL[n]- Fibonacci[n])/2, {n, 40}] (* Harvey P. Dale, Jul 18 2011 *)
a[ n_]:= Fibonacci[n] + LucasL[n+1]; (* Michael Somos, May 28 2014 *)
PROG
(Haskell)
a000285 n = a000285_list !! n
a000285_list = 1 : 4 : zipWith (+) a000285_list (tail a000285_list)
-- Reinhard Zumkeller, Apr 28 2011
(Maxima) a[0]:1$ a[1]:4$ a[n]:=a[n-1]+a[n-2]$ makelist(a[n], n, 0, 30); /* Martin Ettl, Oct 25 2012 */
(PARI) Vec((1+3*x)/(1-x-x^2)+O(x^40)) \\ Charles R Greathouse IV, Nov 20 2012
(Magma) a0:=1; a1:=4; [GeneralizedFibonacciNumber(a0, a1, n): n in [0..30]]; // Bruno Berselli, Feb 12 2013
(Sage) f=fibonacci; [f(n+2) +2*f(n) for n in (0..40)] # G. C. Greubel, Nov 08 2019
(GAP) F:=Fibonacci;; List([0..40], n-> F(n+2) +2*F(n) ); // G. C. Greubel, Nov 08 2019
CROSSREFS
Essentially the same as A104449, which only has A104449(0)=3 prefixed.
Cf. A090888, A101220, A109754, A091157 (subsequence of primes).
Sequence in context: A120740 A274282 A347553 * A042031 A041493 A352321
KEYWORD
nonn,easy,nice
STATUS
approved