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

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

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

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

Cf. A013655, A131775.

Sequence in context: A120740 A274282 A347553 * A042031 A041493 A352321

Adjacent sequences: A000282 A000283 A000284 * A000286 A000287 A000288

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved