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

%I #23 Oct 27 2023 19:33:26

%S 1,2,5,13,33,85,218,559,1435,3682,9448,24244,62210,159633,409622,

%T 1051099,2697145,6920936,17759282,45570729,116935544,300059313,

%U 769959141,1975732973,5069776531,13009163899,33381815615,85658511370,219801722429,564016306267

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

%H 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 G.f.: 1/(1-Sum_{k>0} x^Fibonacci(k)).

%F a(n) ~ c * d^n, where d=2.5660231413698319379867000009313373339800958659676443846860312096..., c=0.7633701399876743973524738479037760170533154734693438061127686049... - _Vaclav Kotesovec_, May 01 2014

%e a(2) = 5 since 2 = 1+1 = 1+1' = 1'+1 = 1'+1'.

%p a:= proc(n) option remember; local r, f;

%p if n=0 then 1 else r, f:= 0, [0, 1];

%p while f[2] <= n do r:= r+a(n-f[2]);

%p f:= [f[2], f[1]+f[2]]

%p od; r

%p fi

%p end:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Feb 20 2017

%t 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 a /@ Range[0, 35] (* _Jean-François Alcover_, Nov 07 2020, after _Alois P. Heinz_ *)

%Y Cf. A000045, A076739.

%K nonn

%O 0,2

%A _Vladeta Jovovic_, Mar 30 2003