Induction Principle Proof

Fundamental Proof Techniques

  1. Induction Principle
  2. Diagonalization Principle
  3. Pigeonhole Principle

Induction Principle
The principle of mathematical induction states that any set of natural numbers containing zero, and with the property that it  contains n + 1 whenever it contains all the numbers up to and including n, must in fact be the set of all natural numbers. Let we want to show that property P holds for all natural numbers. To prove this property, P using mathematical induction following are the steps:

  • Basic Step: Firstly, show that property P is true for 0 or 1 i.e. the statement holds for the first natural number n where n = 0 or n = 1.
  • Induction Hypothesis: Assume that property P holds for n
  • Induction Step: Using induction hypothesis, show that P is true for n+1. Then by the principle of mathematical induction, P is true for all natural numbers

 

We're always listening.
Have something to say about this article? Find us on Facebook, Twitter or our LinkedIn.
Raju Dawadi
Raju Dawadi
Raju is currently actively involved in DevOps world and is focused on Container based architecture & CI/CD automation along with Linux administration. Want to discuss with him on any cool topics? Feel free to connect on twitter, linkedIn, facebook.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.