---

Problem 755

---

Not Zeckendorf

Consider the Fibonacci sequence $1,2,3,5,8,13,21,\dots$.

We let $f(n)$ be the number of ways of representing an integer $n\ge 0$ as the sum of different Fibonacci numbers.
For example, $16=3+13=1+2+13=3+5+8=1+2+5+8$ and hence $f(16)=4$. By convention $f(0)=1$.

Further we define
$${\displaystyle S(n)=\sum _{k=0}^{n}f(k)}$$
You are given $S(100)=415$ and $S({10}^4)=312807$.

Find ${\displaystyle S({10}^{13})}$.

---

非齐肯多夫表示

考虑斐波那契数列$1,2,3,5,8,13,21,\dots$。

记$f(n)$为将整数$n\ge 0$表示为不同斐波那契数之和的方法数。
例如，$16=3+13=1+2+13=3+5+8=1+2+5+8$，因此$f(16)=4$。按照惯例，记$f(0)=1$。

我们进一步定义
$${\displaystyle S(n)=\sum _{k=0}^{n}f(k)}$$
已知$S(100)=415$，$S({10}^4)=312807$。

求${\displaystyle S({10}^{13})}$。

译注：齐肯多夫表示是指将一个整数表示为不连续的不同斐波那契数之和，根据齐肯多夫定理可知该表示唯一；而本题不要求不连续。

---