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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

Examples

			G.f. = 1 + 4*x + 5*x^2 + 9*x^3 + 14*x^4 + 23*x^5 + 37*x^6 + 60*x^7 + ...
		

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

• T. D. Noe, Table of n, a(n) for n = 0..500
• 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.
• Index entries for linear recurrences with constant coefficients, signature (1,1).

Crossrefs

Essentially the same as A104449, which only has A104449(0)=3 prefixed.

Cf. A090888, A101220, A109754, A091157 (subsequence of primes).

Cf. A013655, A131775.

Programs

GAP

F:=Fibonacci;; List([0..40], n-> F(n+2) +2*F(n) ); # G. C. Greubel, Nov 08 2019

Haskell

a000285 n = a000285_list !! n
a000285_list = 1 : 4 : zipWith (+) a000285_list (tail a000285_list)
-- Reinhard Zumkeller, Apr 28 2011

Magma

a0:=1; a1:=4; [GeneralizedFibonacciNumber(a0,a1,n): n in [0..30]]; // Bruno Berselli, Feb 12 2013

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

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

Sage

f=fibonacci; [f(n+2) +2*f(n) for n in (0..40)] # G. C. Greubel, Nov 08 2019

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

E.g.f.: (cosh(x/2) + sinh(x/2))*(5*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, Dec 31 2024