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)
