As of May 4 2007 the scripts will autodetect your timezone settings. Nothing here has to be changed, but there are a few things

Please follow this blog

Search this blog

Thursday, July 8, 2010

Fibonacci computational system

Exercise.

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

Popular Posts

Welcome to The Bridge

Mathematics: is it the fabric of MEST?
This is my voyage
My continuous mission
To uncover hidden structures
To create new theorems and proofs
To boldly go where no man has gone before




(Raumpatrouille – Die phantastischen Abenteuer des Raumschiffes Orion, colloquially aka Raumpatrouille Orion was the first German science fiction television series. Its seven episodes were broadcast by ARD beginning September 17, 1966. The series has since acquired cult status in Germany. Broadcast six years before Star Trek first aired in West Germany (in 1972), it became a huge success.)