CISC 260 Lecture 18: Lecture 5.1
6 Feb 2017
School
Department
Course
Professor
Document Summary
If n e n, n + 1 e n. If x :: a and xs :: [a], the (x:xa) :: [a] S inductively defined can use induction to prove properties over s. Proofs: quasi-mathematical proof that a program or function works correctly. Goal: logical proof that the statement is true. Goal: prove property p(n) is trye for all n >=0. Induction proof rule: simple induction over natural numbers if it can be shown that: base: p holds for some n=0 (eg. p(0)) Inductive step: for all n >= 0, the assumption that p holds for n implies that p also holds for n+1 (p(n) implies p(n+1)) Then, p holds for all n, ie p(n) for all n >= 0. Square n = square (n-1) + 2*n -1. Prove that squaare n = n*n for all n>= 0. P(n): square n = n*n - for all n>=0. Inductive step: p(n-1) - p(n) for all n>0.
