1
$\begingroup$

Prove correctness of the following algorithm for computing the nth Fibonacci number.

algorithm fastfib (integer n) 
if n<0return0;
else if n = 0 return 0;
else if n = 1 return 1;
else a ← 1; b ← 0;
    for i from 2 to n do
       t ← a; a ← a + b; b ← t; 
return a;
end

Not 100% how to complete this with proof by induction. How I started: Base case: The proof is by induction on n. consider the cases n = 0 and n = 1. in these cases, the algorithm presented returns 0 and 1, which may as well be the 0th and 1st Fibonacci numbers.

Now we assume that the algorithm return the correct Fibonacci number for n ( the nth Fibonacci number) for all n<= k where k >= 1. I wasn't sure if I was on right track and where to move from here.

$\endgroup$
  • $\begingroup$ Assume that the k'th Fibonacci number is indeed the value of fastfib(k) for k=1, 2, ...k-1, k. Now run the algorithm for n = k+1 and look for cases where you find yourself computing fastfib(k) and fastfib(k-1) as you crank the handle on the algorithm. It should reduce to a step where you establish that fastfib(k+1) = fastfib(k) + fastfib(k-1), and then you are home free. $\endgroup$ – AlwaysLearning May 24 '17 at 0:47
2
$\begingroup$

You don't want to do induction on the fastfib routine as a whole, since it is not written as a recursive procedure (which is why it is fast, since the typical recursive routine is not)

Instead, you want to do induction on the $i$ of the for loop. In particular, show that after you have done the operations inside the for loop for some value of $i$, $a$ equals Fibonacci number $i$, and $b$ equals Fibonacci number $i-1$

So, as the base you can take $i=2$: given that $a$ is initially set to 1, and $b$ to 0, after the operations $t \leftarrow a$ (so $t$ is set to 1), $a \leftarrow a +b$ (so now $a$ is 1), and $b \leftarrow t$ (so now $b$ is 1), we have indeed that $a=1=F_2$, and $b=1=F_1$. Check!

As a step: assume that after you have done the operations inside the for loop for $i=k$, we have that $a=F_k$ and $b=F_{k-1}$. So now when $i$ becomes $k+1$ and we do one more pass through the operations, we get:

$t \leftarrow a$: so $t=F_k$

$a \leftarrow a +b$: so $a=F_k+F_{k-1}=F_{k+1}$

$b \leftarrow t$: so $b=F_k$

So, $a=F_{k+1}$ and $b=F_k$, as desired. Check!

$\endgroup$
  • $\begingroup$ So you wouldn't use n = 0 and 1 as the base case ? why would you use 2 ? $\endgroup$ – M.Jones May 24 '17 at 1:00
  • $\begingroup$ @M.Jones You could use that as a base case as well ... But I had my reasons for picking 2: I want to do induction over $i$, and the first value of $i$ is 2. Also, the routine returns $a$ after the loop is done, so to me the natural point at which I want to describe the values of he variables is after each time the operations inside the for loop have been done. $\endgroup$ – Bram28 May 24 '17 at 1:10
  • $\begingroup$ okay thanks ! would the inductive hypothesis be we must show that the algorithm returns the correct value for k + 1 . By the induction hypothesis k >= 1 $\endgroup$ – M.Jones May 24 '17 at 1:18
  • $\begingroup$ oh actually my part doesn't make sense ignore that $\endgroup$ – M.Jones May 24 '17 at 1:18
  • $\begingroup$ @M.Jones Again, don't do induction over the algorithm/routine as a whole, because fastfib(k+1) does not generate a call to fastfib(k) ... You need to focus on the for loop $\endgroup$ – Bram28 May 24 '17 at 1:21
0
$\begingroup$
algorithm fastfib (integer n) 
    if      n < 0 return 0;
    else if n = 0 return 0;
    else if n = 1 return 1;
    else {
        a ← 1;
        b ← 0;
        for i from 2 to n do {
           #assert a = F(i - 1)
           #assert b = F(i - 2)
           t ← a;
           a ← a + b;
           b ← t; 
           #assert a = F(i)
           #assert b = F(i - 1)
        }
        #assert i = n + 1
        #assert a = F(i - 1)
        return a;
   }
end

Now you can prove the assertions with induction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.