## 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.