Every Positive Integer Can Be Written as a Sum of Distinct Fibonacci Numbers
\[n\]
to \[F_{n-1}\]
can be written as a sum of distinct elements of the set \[\{ F_1, \; F_2,...,F_{n-1} \}\]
.Proof
\[P(n)\]
be the statement of the theorem. \[F_1=1\]
so \[P(1)\]
is true.Suppose that
\[P(1), \; P(2),..., \; P(k)\]
are all true. Let \[1 \le m \le F_{k+1} \]
. If \[m \lt F_k\]
then by invoking \[P(k)\]
\[m\]
can be written as a sum of distinct Fibonacci numbers from the set \[\{ F_1, \; F_2,...,F_{n-1} \}\]
.Sup[pose then that
\[m \ge F_k\]
then either \[m=F_k\]
- so \[P(k+1)\]
is true, or \[m \gt F_k\]
. In the latter case write \[m-F_k \lt F_{k+1}-F_k =F_{k-1}\]
, and invoking \[P(k-1)\]
we have \[P(k+1)\]
is true. Hence the theorem is proved. 
