The hint for part a is to use induction Prove that every pos

The hint for part (a) is to use induction.

Prove that every positive integer can be written as the sum of different Fibonacci numbers. Prove even more: every positive integer can be written as the sum of different Fibonacci numbers, so that no two consecutive Fibonacci numbers are used. Show by an example that the representation in (a) is not unique, but also prove that the more restrictive representation in (b) is.

Solution

every Fibonacci number can itself be written as the sum of one or more (in this case just one) Fibonacci numbers. therefore involves proving that non-Fibonacci numbers can also be so written Here is a list of a few such integers. Note that these representations are not unique; for example 6 = 5 + 1 and 6 = 3 + 2 + 1. 1 = 1 2 = 2 3 = 3 4 = 3 + 1 5 = 5 6 = 5 + 1 7 = 5 + 2 8 = 8 9 = 8 + 1 10 = 8 + 2 11 = 8 + 3 12 = 8 + 3 + 1 Suppose we wanted to show that the number 62 (which is not a Fibonacci number) could be written as a sum of distinct Fibonacci numbers. We could begin by looking for the largest Fibonacci number that is less than 62, in this case 55, and writing 62 as 55 + 7. Since the difference between 62 and 55 (i.e. 7) must be smaller than 55, then if we know how to decompose it into a sum of distinct Fibonacci numbers (7 = 5 + 2), then we can add 55 to this sum and write 62 = 55 + 5 + 2, where we have now expressed 62 as a sum of distinct Fibonacci numbers. We will use this idea when establishing the inductive step of our induction argument. We need Strong Induction because we are using the fact that 7, rather than 61, can be expressed as a sum of distinct Fibonacci numbers in order to prove the same about 62.

Proof: If n = 1, then 1 = f1. (Inductive Step) Suppose that every integer 1, 2, 3, . . . , k can be written as the sum of one or more distinct Fibonacci numbers, where k 1. Consider the integer n = k + 1. If it is a Fibonacci number, then there is nothing further to show, so suppose it is not. Let fj denote the largest Fibonacci number that is less than k + 1. In other words fj < k + 1 < fj+1. Subtracting fj gives 0 < (k + 1) fj < fj+1 fj = fj1 fj < k + 1. The integer (k + 1) fj belongs to the set {1, 2, 3, . . . , k} and so by our inductive hypothesis it can be written as the sum of one or more distinct Fibonacci numbers. Since (k + 1) fj is also less than fj , then fj is not part of this sum. By adding fj to (k + 1) fj one gets k + 1 expressed as a sum of distinct Fibonacci numbers. Therefore by Strong Induction we have proven that every positive integer n can be written as the sum of one or more distinct Fibonacci numbers