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