# Proving that every natural number can be expressed as the sum of distinct Fibonacci numbers

The Fibonacci sequence $$f_1, f_2, f_3, \ldots$$ is defined by $$f_1 = 1, f_2 = 2$$, and $$f_m = f_{m−1} + f_{m−2}$$ for each integer $$m \ge 3$$. Prove that every $$n \in \mathbb{N}$$ can be expressed as the sum of distinct integers from the Fibonacci sequence.

Note: You may use without proof that the Fibonacci sequence is an increasing sequence

I am stuck in this question. Are we supposed to use strong induction here? I am trying it but get stuck. Any help would be appreciated!

Use strong induction, assuming this is true up to some $$n-1 \in \mathbb{N}$$. Then, for $$n$$, find the largest Fibonacci member $$f$$ below $$n$$ and apply strong induction to $$n - f$$.