# The Fibonacci sequence

Define the Fibonacci function with a double recursion step.
Recall that the Fibonacci sequence is the sequence *u*_{n}
defined by

*u*_{0} =u_{1} = 1

*u*_{n+2} =u_{n} + u_{n+1}

Define another function for computing *u*_{n} with a linear
complexity (by computing simultaneously *u*_{n} and
*u*_{n+1}).

Show that both functions always compute the same result.
## Solution

Look at This file

Going home

Pierre Castéran