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,2

Links

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

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

Example

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

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 *)

Crossrefs

Cf. A000045, A076739.

Sequence in context: A077939 A077986 A007020 * A052988 A001429 A148288

Adjacent sequences: A080885 A080886 A080887 * A080889 A080890 A080891

Keyword

nonn

Author

Vladeta Jovovic, Mar 30 2003

Status

approved