The Fibonacci Sequence is a recursively defined sequence determined by the function:
Fn = 0 if n = 0
Fn = 1 if n = 1
Fn-2 + Fn-1 if n ≥ 2
where n is a natural number.
The first few terms of the sequence are:
F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 =21 .....
Consider the formula ( Fn)^2 + ( Fn+1 )^2 = F2n+1.
a) Show that the formula is true for n = 0 and n = 1.
b) Prove the formula is true for all natural numbers n by induction.