The Fibonacci numbers 1, 1, 2, 3, 5, 8, . . . is a sequence defined by the equation Fn = Fn1 + Fn2 where F1 = 1 and F2 = 1.

Consider a currency system with Fibonacci denominations. In other words, unlike the US currency system which has $1, $5, $10, $20, $50, . . . denominations, we 3 would have $1, $2, $3, $5, $8, $13, . . . denominations. In what follows, we will show that the Fibonacci currency system is efficient in that very few bills are needed to make change for any value $d.

Consider the standard greedy algorithm for making change: To make change for $d, you would choose the largest denomination less than or equal to d, subtract that denomination value from d, and then repeat for the remainder. For example, to make change for $19 in the US currency system, we would choose a $10 bill, yielding a remainder of $9. We would then choose a $5 bill, yielding a remainder of $4. We would then choose a $1 bill, yielding a remainder of $3, and so on. Our change would then be

$10, $5, $1, $1, $1, $1.

Applying the same greedy strategy in the Fibonacci system, our change would be

$13, $5, $1.

i) In making change for $d using the greedy strategy, let Fn be the largest Fibonacci denomination value less than or equal to d. (1) Argue that Fn d < Fn+1. (2) Prove that after choosing an Fn bill, the remainder d Fn must satisfy d Fn < Fn1.

ii) Prove by induction that for any dollar value $d, you can make change for $d without using any denomination more than once and without the use of adjacent denominations. For example, while you could make change for $14 using two $5 bills, one $3 bill, and one $1 bill, you would be using a denomination twice (the $5 bill) and you would be using adjacent denominations (the $5 and $3 bills). One could instead use one $13 and one $1 bill, which are non-adjacent and without repetition. Hint: Make use of the results from part i.

iii) Prove that if change is being made with n denominations d1, d2, . . . , dn and adjacent denominations are not allowed, then at most n/2 unique denominations can be used. For simplicity, you may assume that n is even; the more general result for n odd or even is that at most dn/2eunique denominations can be used. Hint: Try a proof by contradiction, group the denominations in adjacent pairs, and employ the Pigeonhole Principle.

iv) Prove by induction that n 6, Fn 2 n/2 . Note that 2n/2 = ( 2)n 1.414n .

v) Given the results of the previous parts, prove (not necessarily by induction) that d 8 it is always possible to make change for $d in the Fibonacci currency system using at most log2 d bills.