Proof by Induction

go back

”For all” statements

• Sometimes in proofs, we get “for all statements”
• An example would be, “for all integers n, n to the power of 3, take n, is divisible by 3”
• This would be written as: $n^3-n=3k,k\in {\mathbb{Z}}^{+},\forall n\in {\mathbb{Z}}^{+}$
• So…how do we solve this?
• There are infinite numbers, thus we can’t prove that all of them are subjective to this proof by trial and error
• Instead, we must use proof by induction

How to do a proof by induction

1. Prove that the statement is true for n=1
2. Assume the statement is true, for some integer k
3. Prove that the statement is true for k+1
4. Say, “By the principle of mathematical induction, it can thus be concluded that [proof] is true”