Voozh

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

(list; graph; refs; listen; history; text; internal format)

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

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]];