|
%I M3246 N1309 #178 Mar 29 2024 11:44:16
%S 1,4,5,9,14,23,37,60,97,157,254,411,665,1076,1741,2817,4558,7375,
%T 11933,19308,31241,50549,81790,132339,214129,346468,560597,907065,
%U 1467662,2374727,3842389,6217116,10059505,16276621,26336126,42612747,68948873,111561620,180510493,292072113,472582606
%N a(0) = 1, a(1) = 4, and a(n) = a(n-1) + a(n-2) for n >= 2.
%C 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.
%C 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
%C 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
%C 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.
%C 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
%C 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
%C 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
%D Richard E. Merrifield and Howard E. Simmons, Topological Methods in Chemistry, Wiley, New York, 1989. pp. 131.
%D Joe Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 224.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000285/b000285.txt">Table of n, a(n) for n = 0..500</a>
%H Ben Adenbaum, Jennifer Elder, Pamela E. Harris, and J. Carlos Martínez Mori, <a href="https://arxiv.org/abs/2403.07989">Boolean intervals in the weak Bruhat order of a finite Coxeter group</a>, arXiv:2403.07989 [math.CO], 2024. See pp. 2, 10.
%H Brandon Avila and Tanya Khovanova, <a href="http://arxiv.org/abs/1403.4614">Free Fibonacci Sequences</a>, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Avila/avila4.html">J. Int. Seq. 17 (2014) # 14.8.5</a>.
%H Alfred Brousseau, <a href="http://www.fq.math.ca/Scanned/3-2/alfred1.pdf">Seeking the lost gold mine or exploring Fibonacci factorizations</a>, Fib. Quart., 3 (1965), 129-130.
%H Alfred Brousseau, <a href="http://www.fq.math.ca/fibonacci-tables.html">Fibonacci and Related Number Theoretic Tables</a>, Fibonacci Association, San Jose, CA, 1972. See p. 53.
%H A. Eswarathasan, <a href="https://www.fq.math.ca/Scanned/16-4/eswarathasan.pdf">On Square Pseudo-Fibonacci Numbers</a>, Fibonacci Quarterly, Vol. 16, No. 4 (1978), pp. 310-314.
%H A. Eswarathasan, <a href="https://www.fq.math.ca/Scanned/17-2/eswarathasan.pdf">On Pseudo-Fibonacci Numbers of the Form 2S^2, Where S is an Integer</a>, Fibonacci Quarterly, Vol. 17, No. 2 (1979), pp. 142-147.
%H Jia Huang, <a href="https://arxiv.org/abs/1405.1636">Hecke algebras with independent parameters</a>, arXiv preprint arXiv:1405.1636 [math.RT], 2014; Journal of Algebraic Combinatorics 43 (2016) 521-551.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, <a href="http://arxiv.org/abs/1212.1368">A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake</a>, arXiv preprint arXiv:1212.1368 [cs.DM], 2012.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,1).
%F G.f.: (1+3*x)/(1-x-x^2). - _Simon Plouffe_ in his 1992 dissertation
%F Row sums of A131775 starting (1, 4, 5, 9, 14, 23, ...). - _Gary W. Adamson_, Jul 14 2007
%F a(n) = 2*Fibonacci(n) + Fibonacci(n+2). - _Zerinvary Lajos_, Oct 05 2007
%F 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
%F a(n) = 3*Fibonacci(n+2) - 2*Fibonacci(n+1). - _Gary Detlefs_, Dec 21 2010
%F a(n) = A104449(n+1). - _Michael Somos_, Apr 07 2012
%F From _Michael Somos_, May 28 2014: (Start)
%F a(n) = A101220(3, 0, n+1).
%F a(n) = A109754(3, n+1).
%F a(k) = A090888(2, k-1), for k > 0.
%F a(-1 - n) = (-1)^n * A013655(n).
%F a(n) = Fibonacci(n) + Lucas(n+1), see Mathematica field. (End)
%F 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
%F a(n) = (9*F(n) + F(n-3))/2. - _J. M. Bergot_, Jul 15 2017
%F a(n-1) = 3 * A000045(n) + A000045(n+1). - _R. J. Mathar_, Feb 14 2024
%e G.f. = 1 + 4*x + 5*x^2 + 9*x^3 + 14*x^4 + 23*x^5 + 37*x^6 + 60*x^7 + ...
%p with(combinat):a:=n->2*fibonacci(n)+fibonacci(n+2): seq(a(n), n=0..34);
%t LinearRecurrence[{1,1},{1,4},40] (* or *) Table[(3*LucasL[n]- Fibonacci[n])/2,{n,40}] (* _Harvey P. Dale_, Jul 18 2011 *)
%t a[ n_]:= Fibonacci[n] + LucasL[n+1]; (* _Michael Somos_, May 28 2014 *)
%o (Haskell)
%o a000285 n = a000285_list !! n
%o a000285_list = 1 : 4 : zipWith (+) a000285_list (tail a000285_list)
%o -- _Reinhard Zumkeller_, Apr 28 2011
%o (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 */
%o (PARI) Vec((1+3*x)/(1-x-x^2)+O(x^40)) \\ _Charles R Greathouse IV_, Nov 20 2012
%o (Magma) a0:=1; a1:=4; [GeneralizedFibonacciNumber(a0,a1,n): n in [0..30]]; // _Bruno Berselli_, Feb 12 2013
%o (Sage) f=fibonacci; [f(n+2) +2*f(n) for n in (0..40)] # _G. C. Greubel_, Nov 08 2019
%o (GAP) F:=Fibonacci;; List([0..40], n-> F(n+2) +2*F(n) ); // _G. C. Greubel_, Nov 08 2019
%Y Essentially the same as A104449, which only has A104449(0)=3 prefixed.
%Y Cf. A090888, A101220, A109754, A091157 (subsequence of primes).
%Y Cf. A013655, A131775.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
|
