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 Fi appears in the sum, it appears exactly once, and its neighbors Fi-1 and Fi+1 do not appear at all. As always, F,-0, Fi = 1 and Fn-Fn-1 + F,,-2 For example: (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 F2. (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. 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 Fi appears in the sum, it appears exactly once, and its neighbors Fi-1 and Fi+1 do not appear at all. As always, F,-0, Fi = 1 and Fn-Fn-1 + F,,-2 For example: (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 F2. (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