cp's OEIS Frontend

A166106 a(n) = a(n-1) + a(n-2) + F(n), with a(0) = 0, a(1) = 1, a(2) = a(1) + a(0), a(3) = a(2) + a(1), a(4) = a(3) + a(2) + 2.

%I A166106 #30 Jul 26 2024 22:10:43
%S A166106 0,1,1,2,5,12,25,50,96,180,331,600,1075,1908,3360,5878,10225,17700,
%T A166106 30509,52390,89664,153000,260375,442032,748775,1265832,2136000,
%U A166106 3598250,6052061,10164540,17048641,28559450,47786400,79870428,133359715,222457608,370747675
%N A166106 a(n) = a(n-1) + a(n-2) + F(n), with a(0) = 0, a(1) = 1, a(2) = a(1) + a(0), a(3) = a(2) + a(1), a(4) = a(3) + a(2) + 2.
%C A166106 Consider the recursive call tree for Fibonacci numbers shown in the Wilson, Abelson et al., and Bloch links. This type of tree is a variant of Fibonacci trees shown/defined elsewhere. Here, let us refer it as a recursive Fibonacci tree. A Fibonacci number F(n) is the weight of the root of a weighted recursive Fibonacci tree of order n in which the leafs have a weight of 1, and the weight of a node equals the sum of the weights of its two children. If instead we weight each leaf by the number of nodes above it (considering the root as the topmost node), then for n > 2, a(n) is the weight of the root of such a weighted tree of order n. For example, a(5) = 2+2+2+3+3.
%H A166106 G. C. Greubel, <a href="/A166106/b166106.txt">Table of n, a(n) for n = 0..1000</a>
%H A166106 Harold Abelson and Gerald Jay Sussman with Julie Sussman, <a href="http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html">Tree Recursion</a> from "Structure and Interpretation of Computer Programs", MIT Press, 1996, LaTeX2HTML translation by Ryan Bender.
%H A166106 Laurent Bloch, <a href="http://www.laurentbloch.org/spip.php?article76">Analyse de l'algorithme de Fibonacci</a>
%H A166106 Bill Wilson, <a href="http://www.cse.unsw.edu.au/~billw/prologdict.html#memoisation">The Prolog Dictionary - memoisation</a> (shows Recursive call tree for Fibonacci number f_6).
%H A166106 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).
%F A166106 For n > 1, a(n) = A067331(n-2).
%F A166106 From _Colin Barker_, May 25 2014: (Start)
%F A166106 a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4) for n > 6.
%F A166106 G.f.: x*(x^5 + 3*x^4 + 2*x^3 - x^2 - x + 1) / (x^2+x-1)^2. (End)
%F A166106 a(n) = (1/25)*2^(-n-1)*(5*((1 - sqrt(5))^(n+1) + (1 + sqrt(5))^(n+1))*n - (25 + sqrt(5))*(1 + sqrt(5))^n + (sqrt(5) - 25)*(1 - sqrt(5))^n), n > 2. - _Ilya Gutkovskiy_, Apr 26 2016
%t A166106 a[n_] := a[n] = a[n-1] + a[n-2] + Fibonacci[n]; a[0] = 0; a[1] = 1; a[2] = 1; a[3] = 2; a[4] = 5; Table[a[n], {n, 0, 32}] (* _Jean-François Alcover_, Oct 03 2011 *)
%o A166106 (PARI) s = 33; a = concat([0,1,1,2,5],vector(s-5)); for(n=6,s,a[n]=a[n-1]+a[n-2]+fibonacci(n)); for(n=1,s,print1(a[n],", "))
%o A166106 (PARI) concat(0, Vec(x*(x^5+3*x^4+2*x^3-x^2-x+1)/(x^2+x-1)^2 + O(x^100))) \\ _Colin Barker_, May 25 2014
%Y A166106 Cf. A000045.
%K A166106 nonn,easy
%O A166106 0,4
%A A166106 _Gerald McGarvey_, Oct 06 2009
%E A166106 More terms from _Colin Barker_, May 25 2014