## Every Positive Integer Can Be Written as a Sum of Distinct Fibonacci Numbers

Theorem>br /> Every positive integer can be written as a sum of distinct Fibonacci numbers. More precisely each integer from
$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 Proof is by induction. Let
$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.