Induction Proof

{ Precondition: n ³ 1 } FACTORIAL(n)     if n = 1 then return 1     else return FACTORIAL(n-1) * n { Postcondition: FACTORIAL(n) == n! }

Definition: 1! = 1

                n! = (n-1)! * n

Prove by induction that: FACTORIAL(n) = n!

Induction Hypothesis:

P(k): FACTORIAL(k) = k!

Base Step:

P(1): If n=1 then return FACTORIAL(1) = 1!

Inductive Step: P(k) ® P(k+1)

Show P(k+1): FACTORIAL(k+1) = (k+1)!

For FACTORIAL(k+1), k+1 > 1 so the algorithm else is executed.

 

Proof of else return FACTORIAL(n-1) * n:

FACTORIAL(k)	= FACTORIAL(k+1-1)
FACTORIAL(k+1-1) * (k+1)	= FACTORIAL(k) * (k+1)	Multiply both sides by (k+1)
	= k! * (k+1)	IH: FACTORIAL(k) = k!
	= (k + 1)!	Definition of n!