# WTF is Fibonnacci

Sean Ross sross at connectmail.carleton.ca
Thu Jun 19 21:21:22 CEST 2003

```"Mike" <ss3canon at earthlink.net> wrote in message
> I'm readin through the Non-Programers Tutorial for Python and I'm on the
> examples of section Count to 10. And I can't figure out how the example
got
> the output, can anyone help break it down for me?
>
>

# From Non-Programmers Tutorial for Python
# http://honors.montana.edu/~jjc/easytut/easytut/node6.html
# Fibonnacci.py
#This program calulates the fibonnacci sequence
a = 0
b = 1
count = 0
max_count = 20
while count < max_count:
count = count + 1
#we need to keep track of a since we change it
old_a = a
old_b = b
a = old_b
b = old_a + old_b
#Notice that the , at the end of a print statement keeps it
# from switching to a new line
print old_a,
print

Output:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

You can find a *very* detailed discussion of what the fibonacci numbers are
here:
http://mathworld.wolfram.com/FibonacciNumber.html

But, here's a quick version:

A fibonacci number f_n is a number whose value is defined by the recursive
relation f_n = f_n-2 + f_n-1, for n= 3, 4, ...
where f_0 = 0, f_1 = 1, and f_2 = 1.

What does that mean? Let's state it as a function:

Let f_n be represented by f(n). Then f(n) = f(n-2) + f(n-1), by the relation
expressed above when n >= 3.
And we say that

f(0) = 0,
f(1) = f(2) = 1

Here's a concrete example:

f(3) = f(3-2) + f(3-1) = f(1) + f(2) = f(1) + [f(2-2) + f(2-1)]
= 1+[f(0) + f(1)] =  1 + [0 + 1] = 1 + 1 = 2

so f(3) = 2
or the 3rd fibonacci number (f_3) is 2.

Here's the first 99 fibonacci numbers represented as f(n), 0 <= n <= 99
http://math.holycross.edu/~davids/fibonacci/fib0-99.html

Hope this helps,
Sean

```