One way to prove a statement is to check the validity of every single possible case. We can show a proposition that has many cases to be true by exhausting each possible case. For example:
Proposition : has no rational roots.
Proof: we can prove that there are no rational roots by using the rational root theorem. According to the theorem the polynomial will have four possible rational roots -1, 1, -3, 3 and we proceed to check all of them.
Which means that has no rational roots.
Now the problem with this are statements such as is impossible to do with exhaustion. Although there is direct way of proving this, the fastest way is by induction.
Proof by induction works as follows. We start with statement where is the statement and is the index used. What we do is we prove that is true for the smallest possible value what isn’t too obvious. Once that is done we assume that we assume that is true for . is an arbitrary value. We now must show that is true for .
- What is a proof?
- Direct Proof Part I
- Direct Proof Part II
- Proof by Contradiction
- Proof by Induction
- Proof by Induction example
- Proof by Contrapositive
- Proof of Existence
- Proof of Uniqueness
Filed under : Mathematics