2.15. (Fibonacci computational system) Prove that each positive integer admits a unique representation in the form $a_1f_1 + a_2f_2 + \cdots$, where $f_n$ are the Fibonacci numbers, each of the numbers $a_i$ is either $0$ or $1$, the number of ones in the representation is finite, and no two subsequent elements of the sequence $a_i$ are equal to $1$ simultaneously. For example, the first few representations are $1 = f_1$, $2 = f_2$, $3 = f_3$, $4 = f_3 + f_1$, $5 = f_4$, $6 = f_4 + f_1$, $7 = f_4 + f_2$. (Pay attention to the fact that the number $f_0 = 1$ is not used in this computational system, so that the Fibonacci sequence starts with $1,2,3,5,8,\cdots$). Invent algorithms for converting numbers from the Fibonacci system to the decimal positional number system and back, and algorithms for adding and multiplying numbers written in the Fibonacci sequence.
( "Lectures on Generating Functions by S.K. Lando, AMS 2003" )
I like problems like this. Haven't solved it yet, I am working on it.
Off and on I study the book "A course in enumeration - GTM238, by M. Aigner. Springer 2007", a book for graduate students so I need a lot of extra reading to understand the book. A good companion for Chapter 1 is the well known Concrete Mathematics by Ron Graham, Don Knuth and Patashnik. For chapters 2 and 3, mostly about generating functions, I use the book as mentioned above by Lando. - Generating functions are among the mathematical objects I love most. The power of GFs are only limited by our own imagination.
No comments:
Post a Comment