|
|
A000285
|
|
a(0) = 1, a(1) = 4, and a(n) = a(n-1) + a(n-2) for n >= 2.
(Formerly M3246 N1309)
|
|
47
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
G.f.: (1+3*x)/(1-x-x^2). - Simon Plouffe in his 1992 dissertation
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) = Fibonacci(n) + Lucas(n+1), see Mathematica field. (End)
|
|
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)
(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 */
(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.
|
|
KEYWORD
|
nonn,easy,nice,changed
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|