Problem 8

The Fibonacci sequence of numbers is well-known: \(F_1=1,F_2=1,F_3=2,F_4=3,F_5=5,F_6=8,F_7=13,….\)

The nth term, \(F_n\), in this sequence is given by the recurrence relation \(F_n=F_{n-1}+F_{n-2}\) with initial terms \(F_1=1,F_2=1\). However, there is nothing special about starting with 1 and 1; you could start with any two numbers for F_1,F_2, although this will, of course, give you a different sequence.

Suppose you pick two positive integers p,q and define the sequence \(F_1=p,F_2=q,F_n=F_{n-1}+F_{n-2}.\)

Suppose this sequence has the property that \(F_m=1000000\) for some value of m. What are the values of p,q that make m as large as possible?

You should enter your answer in the form p,q (two integers separated by a comma, with no spaces). For example, if you think the answer is \(p=12, q=34\) then you should enter 12,34.