Problem:
Define a sequence of integers as follows: , , and for , . How many different ways are there to write as a sum of distinct elements of this sequence?
Problem:
Define a sequence of integers as follows: , , and for , . How many different ways are there to write as a sum of distinct elements of this sequence?
Solution:
Note that these 's are in fact the Fibonacci numbers. Denote by the number of distinct ways to express a number as a sum of . Note that .
We prove the following lemma:
This follows simply from induction. It is true for ; adding to both sides and using the fact that gives the result.
Now, denote by the number of ways to express as a sum of distinct 's; we are looking for . Now, note that any such sum must contain either or . If the sum does not contain , it must certainly contain ; otherwise, from the lemma, the sum would be at most . Moreover, if the sum contains (but not ), it must also contain ; otherwise, it will be at most .
Hence, .
By a similar argument, any sum of must contain either or . However, this time, it is perfectly possible for this sum to contain but not , since . We thus have two cases to deal with.
Case 1: If the sum contains , then we have to compute . Now, note that as in the argument from earlier, any sum adding up to contains either or . Hence . Repeating this argument, we get . This gives us .
Case 2: The sum does not contain . In this case, the sum must contain . We then have to compute . Any sum adding up to must contain either or ; moreover, if it contains , it must contain as well. Hence, by our previous computation.
Thus, , and .