Computer Science 260

Assignment 6

1. Use mathematical induction to prove that Pn

i=0 i2

i = (n − 1)2n+1 + 2. (4 marks)

2. Let fk be the kth fibonacci number. Use strong mathematical induction to prove

that for n ≥ 3 fn ≥ (

3

2

)

n−2

. (4 marks)

3. Given the loop

while i 6= n

p := 3 × f

f := p + f + 1

i := i + 1

end while

with the precondition {n integer, n ≥ 0, j = 0, f = 1}

and the postcondition {f =

4

n+1−1

3

}

Prove the correctness of this loop with respect to its pre- and post-conditions using the

loop invariant {I(k) : i = k and f =

4

k+1−1

3

} (6 marks)