2. In this problem, we will prove that every non-negative integer can be written

ID: 3167974 • Letter: 2

Question

2. In this problem, we will prove that every non-negative integer can be written as the sum of one or more distinct, nonconsecutive Fibonacci numbers. That is, if the Fibonacci number F, appears in the sum, it appears exactly once, and its neighbors F-1 and Fi+1 do not appear at all. As always, Fo = 0, Fi = 1 and Fn-Fn-1 +Fn-2 For example: 17=B+A+F2 42 = F, + F (a) Prove that if a non-negative integer can be written as the sum of one or more distinct, noncon- secutive Fibonacci numbers, then it can be written in such a way that Fi is not used in the sum. Note that it is not enough to say that F1 = F2, and therefore we can swap F1 if used for Fa. (b) Give an algorithm that takes a non-negative integer parameter n and returns the representation of n as the sum of one or more distinct, nonconsecutive Fibonacci numbers. Your algorithm must use recursion as appropriate. You may use the fact stated in (a) if you would like. Your algorithm does not need to be in C++ or even in pseudo-code. (c) Prove using induction that every non-negative integer can be written as the sum of one or more distinct, nonconsecutive Fibonacci numbers.

Explanation / Answer

2 = F3, and 3 = F4, which we may consider as single term sums.

Suppose that the statement is true for all n <= m (this is the

induction hypothesis for strong induction, while n = m is used for

standard induction). We will prove that the statement is true for

n = m+1.

If m+1 = Ft for some t, then it is trivially correct. In other

cases we find the t such that Ft < m+1 < Ft+1.

Let q = m+1-Ft; then we can write q as sum of nonconsecutive

Fibonacci numbers according to the induction hypothesis. We also

note that this sum does not contain Ft-1 because:

q = m+1-Ft < Ft+1 - Ft = Ft-1

So if we add Ft to the sum of nonconsecutive Fibonacci numbers for

q, we have such a sum for m+1 as well. And the statement is true

for n = m+1.

The statement is clearly true for n = 1, 2, and 3 since 1 = F1,