# Fibonacci coding

Show that every positive integer can be written as a sum of distinct terms of the Fibonacci sequence. (The Fibonacci sequence $\{F_n\}_n$ is defined by $F_0=0, \ F_1=1,$ and $F_{n+1}=F_n+F_{n-1}, \ n\geqslant 1$.)

My proof: We'll prove that statement via the strong mathematical induction.

We see that for $n=1$ it is true since in that case $n=F_1$ or we can take $n=F_0$.

Suppose that our statement is true for $1\leqslant n \leqslant k$ and let's prove this for $n=k+1$.

Then $\exists m\in \mathbb{N}: \ F_m\leqslant k+1<F_{m+1}$.

If $k+1=F_m$ then we are done.

If $F_m<k+1<F_{m+1}$ then $0<(k+1)-F_m\leqslant k$ and here we can apply the assumption of our induction and also $0<(k+1)-F_m<F_{m+1}-F_m=F_{m-1}$ and this guarantees that there is no more $F_{m}$ in $(k+1)-F_m$.

Thus, we have proven out statement.

Is my reasoning correct?

Your argument is correct in essence. I'd say something like: "If $F_m < k+1 < F_{m+1}$, then $k+1 = F_m+j$, where $0 < j < F_{m+1}-F_m = F_{m-1}$. By strong induction, $j$ can be expressed as the sum of distinct Fibonacci terms, none of which can be as great as $F_{m-1}$, which is less than $F_m$, $k+1$ can likewise be expressed as a sum of distinct Fibonacci terms." But that's a matter of personal preference.