only use what is given or suggested in the problem no formul

only use what is given or suggested in the problem. no formulas unless they were mentioned in the problem.

Solution

Let P(n) be the proposition that each integer r with 1 <= r <= n can be represented as the sum of one of more
distinct Fibonacci numbers, with the sum not including any two consecutive numbers.
Base case The true of P(1) is clear, since r = n = 1 is a Fibonacci number.
Induction hypothesis Now suppose that P(k) is true for some k =1. That is, for every positive integer r with
1 <= r <= k can be represented as the sum of distinct Fibonacci numbers and the sum does not include any
two consecutive Fibonacci numbers.
Induction step We need to show that P(k+1) is true. That is, for every positive interger r with 1 <= r <= k+1 can be
represented as the sum of distinct Fibonacci numbers and the sum does not include any two consecutive
Fibonacci numbers. Clearly, we just need to check the case r = k +1 (the induction hypothesis deals with
the other cases.)
If k +1 is a Fibonacci number then we are done and P(k +1) is true. Now suppose k +1 is not a Fibonacci
number, then there exists i such that Fi < k +1 < Fi+1.
Now k+1 = Fi +n for some positive integer n. If we can show that n is the sum of distinct Fibonacci numbers
that do not include Fi1 then we are done.
Now n = k+1Fi . The largest that n can be is k, so 0 < n < k. (If n = 0, then k+1 = Fi and if n = k, then Fi = 1
and so k +1 = 2 and the proposition is clearly two.) So we may now assume n = k +1Fi < k. But by the
induction hypothesis we know that n is the sum of distinct Fibonacci numbers with the sum not including
two consecutive Fibonacci numbers.
We finally need to check that the sum n does not include Fi1 for otherwise k +1 = Fi +n would contain the
consecutive Fibonacci numbers Fi and Fi1.
Suppose Fi1 was contained in the representation of n, then since Fi+1 = Fi +Fi1 we have
k +1 = Fi +n = Fi +Fi1 +m = Fi+1 +m > Fi+1.
This is a contraction, therefore, the representation of n does not contain Fi1. Therefore P(k +1) is true.
Conclusion Since P(1) is true and the truth of P(k) implies the truth of P(k +1) the principle of mathematical
induction implies that P(n) holds for all natural numbers n.