cp's OEIS Frontend

A080888 Number of compositions into Fibonacci numbers (1 counted as two distinct Fibonacci numbers).

%I A080888 #23 Oct 27 2023 19:33:26
%S A080888 1,2,5,13,33,85,218,559,1435,3682,9448,24244,62210,159633,409622,
%T A080888 1051099,2697145,6920936,17759282,45570729,116935544,300059313,
%U A080888 769959141,1975732973,5069776531,13009163899,33381815615,85658511370,219801722429,564016306267
%N A080888 Number of compositions into Fibonacci numbers (1 counted as two distinct Fibonacci numbers).
%H A080888 Alois P. Heinz, <a href="/A080888/b080888.txt">Table of n, a(n) for n = 0..2443</a> (first 301 terms from T. D. Noe)
%F A080888 G.f.: 1/(1-Sum_{k>0} x^Fibonacci(k)).
%F A080888 a(n) ~ c * d^n, where d=2.5660231413698319379867000009313373339800958659676443846860312096..., c=0.7633701399876743973524738479037760170533154734693438061127686049... - _Vaclav Kotesovec_, May 01 2014
%e A080888 a(2) = 5 since 2 = 1+1 = 1+1' = 1'+1 = 1'+1'.
%p A080888 a:= proc(n) option remember; local r, f;
%p A080888       if n=0 then 1 else r, f:= 0, [0, 1];
%p A080888         while f[2] <= n do r:= r+a(n-f[2]);
%p A080888           f:= [f[2], f[1]+f[2]]
%p A080888         od; r
%p A080888       fi
%p A080888     end:
%p A080888 seq(a(n), n=0..35);  # _Alois P. Heinz_, Feb 20 2017
%t A080888 a[n_] := a[n] = Module[{r, f}, If[n == 0, 1, {r, f} = {0, {0, 1}}; While[f[[2]] <= n, r = r + a[n - f[[2]]]; f = {f[[2]], f[[1]] + f[[2]]}]; r]];
%t A080888 a /@ Range[0, 35] (* _Jean-François Alcover_, Nov 07 2020, after _Alois P. Heinz_ *)
%Y A080888 Cf. A000045, A076739.
%K A080888 nonn
%O A080888 0,2
%A A080888 _Vladeta Jovovic_, Mar 30 2003