The Fibonacci numbers are defined by the recursion fn$+1=$ fn $+$ fn$1,$ and the initial

conditions that f$0=$ f$1=1.$ The first few Fibonacci numbers are: $1,1,2,3,5,8,13,21,34,...$

They are named after Fibonacci $(1180-1228),$ aka Leonardo of Pisa.

Prove that $($fn$,$ fn$+1)=1.$ Your proof, naturally, will make use of the definition of the

Fibonacci numbers. And, while it may not be absolutely necessary, your proof will probably

be better if you use induction.