Proof by Induction

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 : f(x) = x^2+3 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.

f(-1)= -1^2+3 = 4 \neq 0

f(1)=1^2+3=4 \neq 0

f(-3) = (-3)^2 + 3 = 12 \neq 0

f(3) = 3^2 + 3 = 12 \neq 0

Which means that f(x) = x^2 + 3 has no rational roots.

Now the problem with this are statements such as 1+2+3+...+x = \frac{x(x+1)}{2} 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 P(x) where P is the statement and x is the index used. What we do is we prove that P(x) is true for the smallest possible x value what isn’t too obvious. Once that is done we assume that we assume that P(x) is true for x = n. n is an arbitrary value. We now must show that P(x) is true for x = n+1.

Previous | Next

  1.  What is a proof?
  2. Direct Proof Part I
  3. Direct Proof Part II
  4. Proof by  Contradiction
  5. Proof by Induction
  6. Proof by Induction example
  7. Proof by Contrapositive
  8. Proof of Existence
  9. Proof of Uniqueness
  10. Disproof
  11. Conclusion

Filed under : Mathematics

Sharing the Wonder