## Problem of the Week 1037## Fibonacci Is a PalindromeThe 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 © Copyright 2005 Stan Wagon. Reproduced with permission. |

20 September 2005