Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
The Fibonacci numbers are (here we list each value once, starting at ). A theorem says: every whole number is a sum of distinct Fibonacci numbers, no two of them next to each other in the list. For example .
State the base case and say where the hypothesis about smaller numbers is used.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Base case. is itself a Fibonacci number.
Step 2. Hypothesis. Assume every number from to has such a representation.
Step 3. The largest piece. If is a Fibonacci number, we are done. If not, let be the largest Fibonacci number below , and the one before it. The next one after is , and it is bigger than . So .
Step 4. Use the hypothesis. is between and , so it has a representation. Every term of it is at most , so it uses neither nor . Adding gives distinct terms, none next to each other. By strong induction, every has a representation.
Step 5. Part (b). . That is terms.
Step 6. Part (c). The largest Fibonacci number up to is . Then , , . So , with terms.
Answer: needs terms; has largest term and terms.
Log in to join the discussion.
Loading…
Strong induction: assume and prove . A step that goes back places needs base cases. Well-ordering: every non-empty set of positive integers has a least element.