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