Proving Properties of Programs

COMP109 Lectures 2020-10-29

Using induction to show that a program is correct.

Example on a Recursive Function that Generates Factorials

Proof

By mathematical induction on $n$.

Base Case $n=1$

\(g(1)=1=1!\)

Inductive Step

Suppose that for some $n=m, g(n)=n!$

Consider $n=m+1$

$g(m+1)$ the code returns $g(m)\times(m+1)$

By induction hypothesis, $g(m)=m!$

So: \(g(m)\times(m+1)=m!\times(m+1)=(m+1)!\)