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

1, 2, 5, 13, 33, 85, 218, 559, 1435, 3682, 9448, 24244, 62210, 159633, 409622, 1051099, 2697145, 6920936, 17759282, 45570729, 116935544, 300059313, 769959141, 1975732973, 5069776531, 13009163899, 33381815615, 85658511370, 219801722429, 564016306267

Offset: 0

Author

Vladeta Jovovic, Mar 30 2003

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2443 (first 301 terms from T. D. Noe)

Crossrefs

Cf. A000045, A076739.

Programs

Maple

a:= proc(n) option remember; local r, f;
      if n=0 then 1 else r, f:= 0, [0, 1];
        while f[2] <= n do r:= r+a(n-f[2]);
          f:= [f[2], f[1]+f[2]]
        od; r
      fi
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Feb 20 2017

Mathematica

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]];
a /@ Range[0, 35] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

Formula

G.f.: 1/(1-Sum_{k>0} x^Fibonacci(k)).

a(n) ~ c * d^n, where d=2.5660231413698319379867000009313373339800958659676443846860312096..., c=0.7633701399876743973524738479037760170533154734693438061127686049... - Vaclav Kotesovec, May 01 2014