25 February 2012

Fibonacci: The Math of Agile

Agile planning poker1 uses the Fibonacci sequence or in some cases a bastardized version of it.  I do not know the exact reason that the series was chosen, I do know the intent is that there is a standard set of numbers and using these deters the player from the temptation of using false precision, like a value of 10.5 for example.  Also it captures growth so each next number is a "unit" of growth larger than the last.  I suspect that the sequence of powers of two (1,2,4,8,16,32,64...) would also work, and might be more apropos to the computer industry, but these two sequences are similar in that they both increase by a constant factor, each subsequent power of two is two times larger and in the Fibonacci sequence each term is roughly 1.618... larger than the previous term, also each has a closed form exponential formula for each term 2n or for Fibonacci sequence it's Binet’s Formula, see below.   I don’t know if the Fibonacci sequence is the right way to go, but it seems to work and it is fairly prevalent in nature and art so it’s probably not a bad choice.  I confess that while this in one of my math of programming series, I am using it primarily as an excuse to write a post about some interesting results relating to the Fibonacci sequence and the Golden Mean, so if you are only interested in Agile you may want to treat this as a short post and stop here, but I encourage you to read on, the math is mostly high school level and it really is interesting.

The Fibonacci sequence is generally attributed to a man, Leonardo Pisano Bigollo who went by Fibonacci and did not actually discover the sequence, it was known about five hundred years earlier in the tenth century by Pingala and it was probably known much earlier.  Ironically Fibonacci’s greatest mathematical contribution was the introduction of Hindu-Arabic Numeral System to Europe, just imagine trying to do multiplication and fractions with Roman numerals.

The Fibonacci sequence is what is known as a recurrence relation or recursive sequence each term is defined as the sum of the two previous terms where the first two terms, which are the generator or seed values F0 = 0 and F1 = 1, the formula is:

It can alternatively be written as:

This form will be more useful to us in a moment.

The sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,...

The Fibonacci sequence has a very interesting relation with a very interesting number known as the Golden Mean which is sometimes referred to as phi and has the following value:

An irrational number that is approximately: 1.6180339887498948482045868343656...

The ratio of a Fibonacci number divided by the previous number in the sequence eventually converges to phi, the first few ratios are:

3/2 = 1.5
5/3 = 1.666666...
8/5 = 1.6
13/8 = 1.625
21/13 = 1.615384...
34/21 = 1.619047...
55/34 = 1.617647...
89/55 = 1.6181818...

As you can see it is already heading there.  It is interesting that a ratio which is in the set of rational numbers converges to an algebraic irrational number. The following equation describes this relationship, the Limit of consecutive quotients:

Additionally the following is true:

If we take the following formula:

And divide it by Fn we get:

We then take the limit as n goes to infinity, replacing the terms using the two limit equations from above:

And if we multiply by phi:

Solving for zero gives us:

Using the quadratic equation we get the following two roots (conjugates):

This is phi and its conjugate, which we will call tau:

Now that we have defined phi and tau we can describe Binet’s formula, mentioned above, which is an exponential form closed formula:

Binet’s formula is an easy way to compute Fibonacci Sequence values without having to calculate all of the values prior to the value you wish to calculate. 

Additionally there is an interesting matrix based calculation:

The above matrix raised to the nth power gives the above matrix of Fibonacci numbers, the first few are:

The determinant of this matrix is (-1)n which is described by Cassini’s Identity:

The Fibonacci sequence and the Golden mean have many interesting identities and relationships with other mathematical disciplines and natural phenomena, for example there is the famous relation rabbit breeding, it relates to bee ancestry, the packing of seeds in flowers, and other plant growth proportions. The Fibonacci sequence occurs in the shallow diagonals of Pascal’s Triangle, it relates to Pythagorean Triples. It relates to the similar Lucas Sequence , the Fibonacci Spiral form above which is a Logarithmic Spiral and the list goes on, a lot of this can be found on the previously linked Wikipedia Page and this BBC radio program.

1 http://renaissancesoftware.net/papers/14-papers/44-planing-poker.html

1 comment: