Fibonacci numbers on In Our Time

The most recent episode of BBC Radio 4’s In Our Time was about Fibonacci numbers. The host, Melvyn Bragg, usually doesn’t do well with the math and science shows, and this show was not a particularly good one, especially compared with last weeks wonderful show on Wordsworth. (There’s too much of a Two Cultures gap and Bragg tends to spend too much time talking about how hard the topic is—something he never does with any topic in the humanities. Still, I give him credit for including subjects he’s not comfortable with.) There were, however, a couple of things I learned.

First, I learned that Fibonacci numbers have cousins called the Lucas numbers, which have the same recurrence relation—each number in the sequence is the sum of the two previous numbers—but start with a different pair of seeds. As with the Fibonacci numbers, the ratio of successive Lucas numbers converges to the golden ratio.

Second, I learned that one of the simpler cool properties of Fibonacci numbers is that the square of a Fibonacci is always one less or one more that the product of the two Fibonaccis on either side of it. As you go through the sequence, the square alternates between being one less and one more than the product. I had to check this out, so I whipped up a quick Python program.

 1:  n = 25
 2:  f = [0, 1];
 3:  for i in range(2, n):
 4:    f.append(f[i-2] + f[i-1])
 5:  
 6:  for i in range(1, n-1):
 7:    sign = (-1)**(i+1);
 8:    symbol = '+' if sign>0 else '-'
 9:    print "%d*%d %s 1 == %d^2 :" % (f[i-1], f[i+1], symbol, f[i]),
10:    print (f[i-1]*f[i+1] + sign == f[i]**2)

Lines 1-4 create a list with the first 25 Fibonaccis: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, and 46368. Lines 6-10 test the square/product property and print out the results. Here’s the output:

0*1 + 1 == 1^2 : True
1*2 - 1 == 1^2 : True
1*3 + 1 == 2^2 : True
2*5 - 1 == 3^2 : True
3*8 + 1 == 5^2 : True
5*13 - 1 == 8^2 : True
8*21 + 1 == 13^2 : True
13*34 - 1 == 21^2 : True
21*55 + 1 == 34^2 : True
34*89 - 1 == 55^2 : True
55*144 + 1 == 89^2 : True
89*233 - 1 == 144^2 : True
144*377 + 1 == 233^2 : True
233*610 - 1 == 377^2 : True
377*987 + 1 == 610^2 : True
610*1597 - 1 == 987^2 : True
987*2584 + 1 == 1597^2 : True
1597*4181 - 1 == 2584^2 : True
2584*6765 + 1 == 4181^2 : True
4181*10946 - 1 == 6765^2 : True
6765*17711 + 1 == 10946^2 : True
10946*28657 - 1 == 17711^2 : True
17711*46368 + 1 == 28657^2 : True

Line 7 alternates the addition and subtraction of one. Line 8 uses Python’s new conditional expression to set the plus or minus symbols in the printed equations. That line won’t work in Pythons before version 2.5; you’ll have to use a traditional if/else block.

Python can deal with very large integers—integers beyond 32 bits—with no fuss. Changing Line 1 to n = 100, for example, yields a list of tests where the last few are

31940434634990099905*83621143489848422977 - 1 == 51680708854858323072^2 : True
51680708854858323072*135301852344706746049 + 1 == 83621143489848422977^2 : True
83621143489848422977*218922995834555169026 - 1 == 135301852344706746049^2 : True

These 20-21 digit numbers are well beyond the limits of what will fit in 32 bits.

I think my older boy has done some simple things with Fibonacci numbers. Tonight I’ll see if he knows about this square/product thing.

Tags: