Fibonacci$($n$)$

$//$ input: a positive integer number $n$

$//$ output: corresponding Fibonacci number

$2-$ Establish the recurrence relation describing the running time of the algorithm

$3-$ Prove by induction, that the running time of this algorithm $T(n)=(2^n).$

$($This running time can be inferred using a recurrence tree. But, this step is not required here$)$