Peteris Krumins comment on Using Fibonacci Numbers to Convert from Miles to Kilometers and Vice Versa

Privacy Controls Software from ParetoLogic

These machines have no common sense; they have not yet learned to 'think,' and they do exactly as they are told, no more and no less. This fact is the hardest concept to grasp when one first tries to use a computer.

Donald Knuth

I am doing a startup!

Cross-browser testing from your browser

I have written my third book!

Perl one-liners explained

You're viewing a comment by Peteris Krumins and its responses.

Peteris Krumins pkrumins Permalink

January 15, 2010, 07:52

Kou, all numbers can be represented as a sum of Fibonacci numbers.

Proof's really easy: it's true for n=1. Now suppose it's true for all n<=k. If n+1 is Fibonacci number, we are done. Otherwise, this number n+1 is bigger than some Fibonacci number Fi. Now let's look at the number n+1-Fi. As this number is smaller than n+1, then according to the inductive hypothesis it can be expressed as a sum of Fibonacci numbers. Therefore n+1 can be expressed as Fi + (n+1-Fi), where Fi is a Fibonacci number and (n+1-Fi) is a sum of Fibonacci numbers.

Reply to this comment