$2$ Calculate the Fibonacci numbers$(20$pts$)$

The Fibonacci numbers are the numbers in the following integer sequence.

$0,1,1,2,3,5,8,13,21,34,55,89,144,$dots

In mathematical terms, the sequence $Fn$ of Fibonacci numbers is defined by the recurrence relation:

$F_n=F_{n-1}+F_{n-2},$ where $F_0=0,F_1=1$

Discuss the correctness of the following algorithms that calculate Fibonacci numbers:

Algorithm $1$

fib $1(n)$

$\{$

integer array $f[n+1]$;

$f[0]=0$;

$f[1]=1$;

for $(i=2$ to $n)$

$f[i]=f[i-1]+f[i-2]$

return $f[n]$;

$\}$

Algorithm $2$

fib $2(n)$

$\{$

if $(n>1)$

return fib $2(n-1)+$ fib $2(n-2)$

else if $(n<mn\; id="EditorElement\_1021630">1</mn><mi\; id="EditorElement\_1021632">)</mi>$

return fib$2($n$)$

$\}$

Algorithm $3$

fib $3($n$)$

$\{$

$a=0$

$b=1$

if $(n=0)$

return a

for $($i $=2$ to $n)$

$\{$

$c=a+b$

$b=c$

$a=b$

$\}$

return b;

$\}$