13th Swedish 1973 Problem 2 The Fibonacci sequence f 1 , f 2 , f 3 , ... is defined by f 1 = f 2 = 1, f n+2 = f n+1 + f n . Find all n such that f n = n 2 .
12 Solution The first few values are f 1 = 1, f 2 = 1, f 3 = 2, f 4 = 3, f 5 = 5, f 6 = 8, f 7 = 13, f 8 = 21, f 9 = 34, f 10 = 55, f 11 = 89, f 12 = 144, f 13 = 233, f 14 = 377. Note that the only solution to f n = n 2 for n ≤ 12 is n = 12. We claim that f n > n 2 for n ≥ 13. It is true for n = 13, 14. Suppose it is true for n, n+1, then f n+2 > (n+1) 2 + n 2 = 2n 2 + 2n + 1. But n 2 -2n-3 = (n-3)(n+1) > 0, so 2n 2 +2n+1 > n 2 +4n+4 = (n+2) 2 , so the result is true for n+2 and hence for all n ≥ 13. Thanks to Suat Namli 13th Swedish 1973 © John Scholes jscholes@kalva.demon.co.uk 12 February 2004 Last corrected/updated 12 Feb 04