07 Inverse thinking

Sometimes there can be useful challenges involved by thinking in the inverse direction (the method below can also be described as "working backwards"). Here is a problem from the Mathematics Challenge for Young Australians.

Example 7.1

A Fibonacci sequence is one in which each term is the sum of the two preceding terms. The first two terms can be any positive integers. An example of a Fibonacci sequence is 15, 11, 26, 37, 63, 100, 163, ...

1. Find a Fibonacci sequence which has 2000 as its fifth term.
2. Find a Fibonacci sequence which has 2000 as its eighth term.
3. Find the greatest value of n such that 2000 is the nth term of a Fibonacci sequence.

Discussion

Generally one thinks of a Fibonacci sequence in the forward direction. Here, as is common in an inverse thinking scenario, instead of being given the data and then finding the results, we are given the results and are asked to find the data. It is a challenge for students to think this way.

The student can do this by searching through various second-last terms and working back. In doing so, depending on which term they choose, they can work back uniquely but some choices will not go back far. If the second last term is less than 1000, the third last term is greater than 1000 and that is as far as we can go, as the next term would be negative. We do not do much better if the second last term is too high.

The student can eventually focus in on a small range of values for which the sequence can be traced back a few terms, and then finally the one which goes back optimally.

Solution 7.1

1. Note that the fifth term in the standard Fibonacci series is 5, a factor of 2000. So multiplying the first five terms by 400 yields 400, 400, 800, 1200, 2000. Many other sequences are possible and can easily be found by trial and error.
   1. Alternative Method: Systematic trialling of possible numbers for the fourth term eventually shows that if the fourth term is 1333, the previous three terms are 667, 666 and 1, giving 1, 666, 667, 1333, 2000. Note that if the fourth term is 1334 or more, the third term is 666 or less, the second term is 668 or more, and the first term must be negative, giving an invalid sequence.
   2. Similarly, if the fourth term is 1001, the previous terms are 999, 2 and 997. Note that if the fourth term is 1000 or less, then the third term is 1000 or more, the second term is 0 or negative, giving an invalid sequence.
   3. It follows that the selection for the fourth term of any integer between 1001 and 1333 inclusive will lead to a valid sequence with 2000 as the fifth term.
   4. Selection for the fourth term of any integer outside this range will lead to an invalid sequence. There are 333 valid sequences.
2. Systematic trialing of possible numbers for the seventh term shows that the selection of any integer between 1231 and 1249 inclusive will lead to a valid sequence with 2000 as the eighth term.
   1. Note that if the seventh term is 1230 or less, then the sixth term is 770 or more, the fifth term is 460 or less, the fourth term is 310 or more, the third term is 150 or less, the second term is 160 or more and the first term is negative, giving an invalid sequence.
   2. Similarly, if the seventh term is 1250 or more, the sixth term is 750 or less, the fifth term is 500 or more, the fourth term is 250 or less, the third term is 250 or more and the second term is 0 or negative, giving an invalid sequence.
   3. Selection for the seventh term of any integer outside the range 1231 and 1249 inclusive will, as shown, not lead to a valid sequence.
   4. There are 19 valid sequences. For example, a seventh term of 1231 yields 3, 152, 155, 307, 462, 769, 1231, 2000.
3. With similar reasoning to that in 2., systematic trialing of possible numbers for the term preceding 2000 shows that the selection of any integer between 1236 and 1238 inclusive will lead to a valid sequence with 2000 as the tenth term.
   1. Writing each of these sequences in reverse for ten terms yields:
   2. 2000, 1236, 764, 472, 292, 180, 112, 68, 44, 24.
   3. 2000, 1237, 763, 474, 289, 185, 104, 81, 23, 58.
   4. 2000, 1238, 762, 476, 286, 190, 96, 94, 2, 92.
   5. Note that the latter two sequences cannot be extended further, since an extra term will be negative. However the first sequence can be extended to three more terms: 20, 4, 16. It follows that there is exactly one sequence of 13 terms:
   6. 2000, 1236, 764, 472, 292, 180, 112, 68, 44, 24, 20, 4, 16.
   7. This 13-term sequence is the one of maximum length.

Further Discussion

The Golden Ratio can be discovered in extended thinking of this problem, which makes a nice surprise.

Fibonacci sequences are generated via what are known as recurrence relations of the form x_n+2=x_n+1+x_n. It can be shown that the ratio x_n+1/x_n of successive terms gets closer and closer to what is known as the Golden Ratio, whose value is (1+√5)/2, which equals 1.61803398875... (Try checking this by calculating the ratio of some successive ratios for higher n.)

So if we are looking for a lengthy sequence ending in 2000 we might expect the second last term to be approximately 2000/1.61803398875..., which is 1236.0679775379..., closest to 1236, which was the actual second-last term in the longest sequence, as we discovered.