Define the sequence of positive integers fn by f0 = 1, f1 = 1, fn+2 = fn+1 + fn. Show that fn = (an+1 - bn+1)/√5, where a, b are real numbers such that a + b = 1, ab = -1 and a > b.
Solution
Put a = (1+√5)/2, b = (1-√5)/2. Then a, b are the roots of x2 - x - 1 = 0 and satisfy a + b = 1, ab = -1. We show by induction that fn = (an+1 - bn+1)/√5. We have f0 = (a-b)/√5 = 1, f1 = (a2-b2)/√5 = (a+1 - b-1)/√5 = 1, so the result is true for n = 0, 1. Finally, suppose fn = (an+1 - bn+1)/√5 and fn+1 = (an+2 - bn+2)/√5. Then fn+2 = fn+1 + fn = (1/√5)(an+1(a+1) - bn+1(b+1) ) = (an+1a2 - bn+1b2)/√5, so the result is true for n+1.
Thanks to Suat Namli
© John Scholes
jscholes@kalva.demon.co.uk
7 March 2004
Last corrected/updated 7 Mar 04