The Fizbin numbers are defined by the recurrence relation:

$F_{0}2,F_{1}2,F_{2}2,F_n{F}_{n-1}-2F_{n-2}+F_{n-3},$ for $n3.$

We are to prove, using the Principle of Strong Mathematical Induction, that the following

algorithm for computing the $n-$th Fizbin number is correct.

FrzBIN$(n)$

Precondition: ninZ with $n0$

Postcondition: returns $F_n($the $n-$th Fizbin number

if $n2$ then

return $2$

else

$\{$:$[xlarrFizBin(n-1)],[YlarrFizbin(n-2)],[xlarrx-2Y],[YlarrFizbin(n-3)],[xlarrx+Y],[$ return $x]\}$

$($a$)$ What is the predicate $P(n)$ to be proven $($for all integers $n0)?$

Answer:

$F_n=F_{n-1}-2F_{n-2}+F_{n-3}$

$($b$)$ In the basis step, what should be shown? Do not give the proofs.

Answer:

$F(0)=2$

$($c$)$ In the inductive step, we are to show that for a given integer $k0,$ the statement

$P(k)$ is true. As result of the basis step, what other assumption can be made about

the value of $k?$

Answer:

$F(k)=F_{k-1}-2F_{k-2}+F_{k-3}$

$F(k+1)=F_k-2F_{k-1}+F_{k-2}$

$($d$)$ In the inductive step, what is the inductive hypothesis? Be as explicit as possible.