Problem of the Week 1037

Fibonacci Is a Palindrome

The Fibonacci recurrence (F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2) ) can be run backward as well as forward. That leads to the sequence {..., 13 ,-8 ,5, -3, 2, -1 ,1 , 0, 1, 1, 2, 3, 5, 8, 13,...}. Ignoring signs, the backward sequence is the same as the forward.

If we allow the initial values to vary from (0, 1) to other pairs of integers (a, b) -- but use the same basic recurrence -- how many choices lead to sequences that are palindromic in absolute value?

Note that we consider two sequences the same if they are, well, the same. For example, the pair (-8, 5) works, but the sequence it generates is identical to the Fibonacci sequence, so this doesn't count as a new sequence.

Source: The new British magazine Infinity, April 2005, p. 27. More info at www.tarquinbooks.com.

© Copyright 2005 Stan Wagon. Reproduced with permission.