0

Prove correctness of the following algorithm for computing the $n$th Fibonacci number.

algorithm fastfib (integer $n$)
if $n \lt 0$ return $0$;
else if $n = 0$ return $0$;
else if $n = 1$ return $1$;
else $a \leftarrow 1; b \leftarrow 0$;
$\qquad$for $i$ from $2$ to $n$ do
$\qquad$$\qquad$ $t \leftarrow a; a \leftarrow a + b; b \leftarrow t$;
return $a$;
end

Can anyone show me how to prove the correctness of this algorithm? It seems like a code

jhg
  • 77
  • 2
    It seems like a code. Well, it is a code ! – Evargalo May 24 '17 at 09:33
  • Well, if you insist that Fibonacci numbers with negative index are $0$ (generally, that's not done, it's extended in such a way that the recurrence is still valid for negative indices), it seems to be correct. I'd call it slowfib, though. ;-) –  May 24 '17 at 09:36

2 Answers2

1

Yes the code is correct.

You can proceed by induction, say the code worked for all natural numbers $1,2,3\dots ,n$.

Then when you input $n+1$ then the for loop, runs from $2$ to $n+1$, we know that when inside the for loop we reach $i=n-1$, we have $a=F_{n-1}$, the $(n-1)$th fibonacci number, as the code worked fine when your input was $n-1$.

So after that when we have $i=n$, then we have $b=F_{n-1}$(from the above argument) and $a=F_{n}$ as the code worked fine when your input was $n$, so when $i=n+1$, $a=F_{n}+F_{n-1}$, so you are given the right output, hence your code is perfectly ok!

Arpan1729
  • 3,414
0

Case $n>1$: Can you prove by recurrence that for each i from 2 to n,

$t_i=F_{i-1}, a_i=F_i, b_i=F_{i-1}$ ?

Evargalo
  • 2,593