Let $(F_n)$ be the Fibonacci numbers ,defined by $F_n=F_{n-1}+F_{n-2}$ where $F_0=0, F_1=1$
My attempt:
Let $F_k$ be the biggest Fibonacci number, such that $F_k \leq n$ still holds. Now we consider $n-F_{k_1}$. We know that $n-F_{k_1}< F_{k_1}$. Now lets assume $F_{k_2}$ is the smallest number such that $F_{k_2} \leq n- F_{k_1}$ Now consider $n-F_{k_1}-F_{k_2}$ ...
Therefore I tried to do
Induction: Let's assume every number up to $n \in \mathbb{N}$ can be written as a sum of distinct Fibonacci numbers. We want to show that this holds for $n+1$: Let $F_k$ be the smallest Fibonacci number such that $F_k < n+1$.
Then $n+1- F_k \leq n$, this means that $n+1- F_k:=m$ can be written as a sum of distinct Fibonacci numbers $m=F_{l_1}+...+F_{l_i}$. But since $n+1-F_k=m \leq F_k$, there can't be $i$ such that $F_{l_i}=F_k$. Thus $n+1=m+F_k=F_{l_1}+...+F_{l_i}+ F_k$ is a sum of distinct Fibonacci numbers.
Question: I am not really sure if my solution is correct, so is it correct? Is there a better way of solving this?