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.

  • $\begingroup$ Indeed, your correction is much better and readable than mine. Thanks a lot for remark :) $\endgroup$ – ZFR Nov 29 '17 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.