Ile jest różnych zapisów liczby w postaci sumy pewnych liczb

[msq93]

Jeśli\(\displaystyle{ f_{n}}\) oznacza liczbę różnych zapisów liczby naturalnej \(\displaystyle{ n}\) w postaci sumy składników będących liczbami ze zbioru \(\displaystyle{ \left\{ 1,2,4\right\}}\), to
A) \(\displaystyle{ f_{1}=1, f_{2} =2, f_{3} =3, f_{4} =6, f_{5} =10, f_{6} =18;}\)
B) \(\displaystyle{ f_{8} =55;}\)
C) \(\displaystyle{ f_{10} =169}\)

Próbowałem z Dwumianem Newtona, dla \(\displaystyle{ f_{4}}\) i \(\displaystyle{ f_{5}}\) to działa, ale to bardzo luźny pomysł bo dla reszty niestety nie.

Próbowałem z podzielnością, widzę że \(\displaystyle{ 6}\) dzieli się przez \(\displaystyle{ 1, 2}\) bez reszty, i wtedy \(\displaystyle{ 6:1 = 6}\) i \(\displaystyle{ 6:2 = 3}\), wtedy \(\displaystyle{ 6 \cdot 3 = 18}\). Znowu luźny pomysł, ale chyba już bliższy prawdy.

Oczywiście można ręcznie to obliczać ale to bardzo mozolny i bezsensowny sposób dla dużych liczb.
Więc drodzy forumowicze, jak się za to zabrać?

Pozdrawiam

[p-adyczny Leo]

Rekurencja \(\displaystyle{ a_n = a_{n-1} + a_{n-2} + a_{n-4}}\) prowadzi do funkcji tworzącej

\(\displaystyle{ A(x) = \frac{1}{1-x-x^2-x^4}.}\)