Question

function fib(n)

if n=0 then return(1)

if n=1 then return(1)

last=1

current=1

for i=2 to n do

temp=last+current

last=current

current=temp

return(current)

Fibonacci numbers are defined as F₀=1, F₁=1, F_i=F_i-1+F_i-2 for i>

The algorithm of above can also be proven correct using the Loop Invariant method. The proof will first show that it will correctly compute F₀ & F₁ by virtue of lines 1 and 2, and then show that it will correctly compute F_n, n>1, using the LI technique on the for loop. For this latter part of the correctness proof, complete the Loop Invariant below by filing in the blanks. Then complete the three parts of the rest of the proof.

Loop Invariant:

Before any execution of the for loop of line 5 in which the loop variable i=k, 2≤k≤n, the variable last will contain _______ and the variable current will contain _________.

Initialization:

Maintenance:

Termination:

Answer 1

Before the execution of the for loop, the variable last contains the (k-2)th Fibonacci number F(k-2) and the variable current contains (k-1)th Fibonacci number F(k-1).

Initialization: Before the first iteration, with i=2, we have current containing F(1)=1 and last containing F(0)=1. Hence, the loop invariant is true.

Maintenance: Let before the iteration of the for loop with i=k, the variable current contains F(k-1) and last contains F(k-2). Then, after the iteration (before the iteration with i=k+1), temp=last+current sets temp to be F(k-1)+F(k-2)=F(k), last=current sets last as F(k-1) and current=temp sets current as F(k). So, the loop invariant remains true.

Termination: The for loop runs till i=n, so the final value of current when i=n is F(n). Since this value is returned, the function successfully computes the nth Fibonacci number.