cp's OEIS Frontend

A019274 Number of recursive calls needed to compute the n-th Fibonacci number F(n), starting with F(1) = F(2) = 1.

%I A019274 #48 Jul 01 2025 09:27:52
%S A019274 0,0,2,4,8,14,24,40,66,108,176,286,464,752,1218,1972,3192,5166,8360,
%T A019274 13528,21890,35420,57312,92734,150048,242784,392834,635620,1028456,
%U A019274 1664078,2692536,4356616,7049154,11405772,18454928,29860702,48315632
%N A019274 Number of recursive calls needed to compute the n-th Fibonacci number F(n), starting with F(1) = F(2) = 1.
%C A019274 Let g = F(2) + F(3) + ... + F(n) = F(n+2) - 2. Some numbers in the range [0,g] have unique representations of the form Sum_{i=1..n} a(i)*F(i) where each a(i) is 1 or -1. These numbers have the form g-k for k in the sequence. - Louis ten Bosch (louis_ten_bosch(AT)hotmail.com), Jan 01 2003
%H A019274 Harvey P. Dale, <a href="/A019274/b019274.txt">Table of n, a(n) for n = 1..1000</a>
%H A019274 Kassie Archer and Noel Bourne, <a href="https://arxiv.org/abs/2505.05218">Pattern avoidance in compositions and powers of permutations</a>, arXiv:2505.05218 [math.CO], 2025. See p. 6.
%H A019274 Elisa Heinrich Mora and Noah A. Rosenberg, <a href="https://arxiv.org/abs/2506.16577">An nth-cousin mating model and the n-anacci numbers</a>, arXiv:2506.16577 [q-bio.PE], 2025. See p. 7.
%H A019274 Kim Trammell, <a href="http://groups.google.com/groups?hl=en&amp;lr=&amp;ie=UTF-8&amp;selm=323ba24c.80516659%40usenet">sci.math article</a> [Broken link]
%H A019274 Mike Winkler, <a href="http://arxiv.org/abs/1412.0519">On the structure and the behaviour of Collatz 3n+1 sequences-Finite subsequences and the role of the Fibonacci sequence</a>, arXiv preprint arXiv:1412.0519 [math.GM], 2014.
%H A019274 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).
%F A019274 a(n) = a(n-1) + a(n-2) + 2. a(n) = 2*F(n) - 2 = 2*A000071(n).
%F A019274 a(n+2) = Sum_{k=0..n} Fibonacci(n-k) + k*Fibonacci(n-k).
%F A019274 a(n) = Sum_{k=0..n} (2 - 2*0^(n-k))*F(k). - _Paul Barry_, Oct 24 2007
%F A019274 a(n) = F(n) + F(n+3) - 2, n>=-1 (where F(n) is the n-th Fibonacci number). - _Zerinvary Lajos_, Jan 31 2008
%F A019274 G.f.: 2*x^3 / ( (x-1)*(x^2+x-1) ). - _R. J. Mathar_, Jul 01 2012
%F A019274 a(1)=0, a(2)=0, a(3)=2, a(n) = 2*a(n-1) - a(n-3). - _Harvey P. Dale_, Oct 16 2012
%p A019274 with(combinat): seq(fibonacci(n-2)+fibonacci(n+1)-2, n=1..35); # _Zerinvary Lajos_, Jan 31 2008
%t A019274 Fibonacci[Range[5! ]]*2-2 (* _Vladimir Joseph Stephan Orlovsky_, Mar 19 2010 *)
%t A019274 LinearRecurrence[{2,0,-1},{0,0,2},40] (* _Harvey P. Dale_, Oct 16 2012 *)
%Y A019274 Cf. A000045.
%Y A019274 Antidiagonal sums of array A017125.
%K A019274 nonn,easy,nice
%O A019274 1,3
%A A019274 Kim Trammell (kim(AT)coc.com) and others