Friday, January 16, 2009

Ch1, Ex3

Proof By Induction:
We see {Pascal 1} = [1] is correct and so is {Pascal 2} = [1 1].
Assume {Pascal N-1} is correct. Then
{Pascal N} = {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
is nth row of pascal's triangle. Hence {Pascal N} is correct.

Note: Actually we should also prove that all three auxiliary functions are
also correct, which will be similar arguments.

No comments:

Post a Comment