

A166106


a(n) = a(n1) + a(n2) + 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.


4



0, 1, 1, 2, 5, 12, 25, 50, 96, 180, 331, 600, 1075, 1908, 3360, 5878, 10225, 17700, 30509, 52390, 89664, 153000, 260375, 442032, 748775, 1265832, 2136000, 3598250, 6052061, 10164540, 17048641, 28559450, 47786400, 79870428, 133359715, 222457608, 370747675
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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.


LINKS

Harold Abelson and Gerald Jay Sussman with Julie Sussman, Tree Recursion from "Structure and Interpretation of Computer Programs", MIT Press, 1996, LaTeX2HTML translation by Ryan Bender.


FORMULA

a(n) = 2*a(n1) + a(n2)  2*a(n3)  a(n4) for n > 6.
G.f.: x*(x^5 + 3*x^4 + 2*x^3  x^2  x + 1) / (x^2+x1)^2. (End)
a(n) = (1/25)*2^(n1)*(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


MATHEMATICA

a[n_] := a[n] = a[n1] + a[n2] + Fibonacci[n]; a[0] = 0; a[1] = 1; a[2] = 1; a[3] = 2; a[4] = 5; Table[a[n], {n, 0, 32}] (* JeanFrançois Alcover, Oct 03 2011 *)


PROG

(PARI) s = 33; a = concat([0, 1, 1, 2, 5], vector(s5)); for(n=6, s, a[n]=a[n1]+a[n2]+fibonacci(n))); for(n=1, s, print1(a[n], ", "))
(PARI) concat(0, Vec(x*(x^5+3*x^4+2*x^3x^2x+1)/(x^2+x1)^2 + O(x^100))) \\ Colin Barker, May 25 2014


CROSSREFS



KEYWORD

nonn,easy


AUTHOR



EXTENSIONS



STATUS

approved



