Q3. Define the Fibonacci sequence by fi=1, f2 = 1, fn=fn-1+ fn-2 for n 3. Prove by induction that ged(fn fn+1)=1 for n > 1.