The Fibonacci sequence
Define the Fibonacci function with a double recursion step.
Recall that the Fibonacci sequence is the sequence un
u0 =u1 = 1
un+2 =un + un+1
Define another function for computing un with a linear
complexity (by computing simultaneously un and
Show that both functions always compute the same result.
Look at This file