Principle of Mathematical Induction

    This topic states the well-ordering principle, the principle of mathematical induction,  and the fact that they are equivalent mathematical statements. We give several examples of how to use the technique of mathematical induction; as well as, the strong form of mathematical induction.  

(1) (Well-Ordering Principle) The well-ordering principle is the following statement: every nonempty set of positive integers contains a least element.

(2) (Principle of Mathematical Induction) Let be a set of positive integers with the following properties: (i) The integer 1 belongs to and (ii) If is in then is in Then is the set of positive integers.

     The induction principle as just stated is cast as a rule for theorem-proving. Let be a proposition involving an integer variable and suppose we wish to prove the theorem "for every integer ", where is a specific integer. This can be accomplish by proving the following two statements instead: " " and "for every integer implies ". That this rule follows from (and in fact, is equivalent to) the principle of induction is seen simply by taking to be the set of integers for which The rule itself is frequently called the induction principle and was first used by B. Pascal. It must be empathized that the three statements in quotation marks are different  form one another.  The last of them is usually proved by assuming that is an integer for which and deducing but this is quite different from assuming that for all which is the theorem. The assumption " " is an integer for which " is called the induction hypothesis.

     The well-ordering principle and the principle of mathematical induction are equivalent statements. That is to say, if one of the statements is assumed to be true, then the other statement can be proven true.

(3) Proposition (Mathematical Induction - Well Ordering Equivalence) If a set of positive integers has the two properties (i) the integer 1 belongs to and (ii) whenever the integer is in the next integer must also be in   then is the set of positive integers; then every set of positive integers must a have a least element.

(4) Example (Principle of Mathematical Induction) Use mathematical induction to prove that



for all positive integers

    Solution. For so the base case holds. Assume that the result is true for some positive integer we need to show that  



holds. We have,



(using the induction hypothesis)





Therefore, by mathematical induction, the statement is true for all positive integers

(5) Example (Principle of Mathematical Induction) Use mathematical induction to prove that for all positive integers

    Solution.  For so the base case holds.  Assume that the result is true for a positive integer we need to show that  



holds. We have,



(using the induction hypothesis)


    
Therefore, by mathematical induction, the statement is true for all positive integers

(6) Example (Principle of Mathematical Induction) Use mathematical induction to prove that



for all positive integers

    Solution. For so the base case holds. Assume that the result is true for a positive integer we need to show that   holds. We have,



(using the induction hypothesis)


    
Therefore, by mathematical induction, the statement is true for all positive integers

(7) Example (Principle of Mathematical Induction) Use mathematical induction to prove that for all positive integers

    Solution. Since the statement is true for Assume that the result is true for a positive integer greater than 3,  we need to show that   holds. Starting from we multiply by 2 to obtain But since Therefore, as desired. Therefore, by mathematical induction, the statement is true for all positive integers

(8) Example (Principle of Mathematical Induction) Let be any real number greater than . Use mathematical induction to prove that for all positive integers

    Solution. Since the statement is true for Assume that the result is true for a positive integer we need to show that   holds. Since we can multiply by to obtain


    
Since we see that



as desired. Therefore, by mathematical induction, for all positive integers

(9) Example (Principle of Mathematical Induction) Use mathematical induction to establish that for all

    Solution. For is obvious so the statement is true for   Suppose that the equation is true for namely,
    


Then for we have,







Now using the induction hypothesis,





and so



Therefore, by mathematical induction, for all

(10) Proposition (Strong Form of Mathematical Induction) A set of positive integers that contains the integer 1, and that has the property: for every positive integer if the set contains then it also contains the integer must be the set of all positive integers.

(11) Example (Principle of Mathematical Induction) Define a function recursively for all positive integers by and for Show that for all positive integers using the strong form of mathematical induction.

    Solution. The basis step consists of verifying the formula for and For we have and for we have Now assume that for all positive integers with where BY the induction hypothesis it follows that
















    


Therefore, by the second principle of mathematical induction (strong form),   for all positive integers as desired.

Number Theory Books

A Beginner's Guide to Constructing the Universe: Mathematical Archetypes of N... List Price: $18.95 Buy New: $10.45 You Save: $8.50 (45%) New (37) Used (28) from $8.49The Universe May Be a Mystery,But It's No SecretMichael Schneider leads us on a spectacular, lavishly illustrated journey along the numbers one through ten to explore the mathematical principles made visible (more)

Bayesian Computation with R (Use R) List Price: $49.95 Buy New: $33.51 You Save: $16.44 (33%) New (32) Used (8) from $33.51There has been a dramatic growth in the development and application of Bayesian inferential methods. Some of this growth is due to the availability of powerful simulation-based algorithms to summarize (more)

e: The Story of a Number List Price: $19.95 Buy New: $8.23 You Save: $11.72 (59%) New (42) Used (32) Collectible (1) from $3.25The interest earned on a bank account, the arrangement of seeds in a sunflower, and the shape of the Gateway Arch in St. Louis are all intimately connected with the mysterious number e. In this informal (more)

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... List Price: $16.00 Buy New: $8.91 You Save: $7.09 (44%) New (35) Used (15) from $7.49In 1859, Bernhard Riemann, a little-known thirty-two year old mathematician, made a hypothesis while presenting a paper to the Berlin Academy titled ?On the Number of Prime Numbers Less Than a Given Quantity.? (more)

Euler's Gem: The Polyhedron Formula and the Birth of Topology List Price: $27.95 Buy New: $17.00 You Save: $10.95 (39%) New (27) Used (3) from $14.99Leonhard Euler's polyhedron formula describes the structure of many objects--from soccer balls and gemstones to Buckminster Fuller's buildings and giant all-carbon molecules. Yet Euler's formula is so (more)

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills List Price: $29.95 Buy New: $17.98 You Save: $11.97 (40%) New (36) Used (10) from $17.98I used to think math was no fun'Cause I couldn't see how it was doneNow Euler's my heroFor I now see why zeroEquals e[pi] i+1--Paul Nahin, electrical engineer In the mid-eighteenth century, Swiss-born (more)

The Fabulous Fibonacci Numbers List Price: $28.98 Buy New: $15.00 You Save: $13.98 (48%) New (35) Used (11) Collectible (1) from $14.50The most ubiquitous, and perhaps the most intriguing, number pattern in mathematics is the Fibonacci sequence. In this simple pattern beginning with two ones, each succeeding number is the sum of the two (more)

Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) List Price: $14.95 Buy New: $7.69 You Save: $7.26 (49%) New (35) Used (13) from $7.69Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) (more)

Sacred Number: The Secret Quality of Quantities (Wooden Books) List Price: $12.00 Buy New: $5.59 You Save: $6.41 (53%) New (30) Used (13) from $5.59Numbers permeate every aspect of our lives; very little happens without a basic ability to manipulate the simple whole numbers we all take for granted. Beautifully illustrated with old engravings as well (more)

The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics List Price: $13.95 Buy Used: $0.98 You Save: $12.97 (93%) New (28) Used (29) from $0.98In 1859, German mathematician Bernhard Riemann presented a paper to the Berlin Academy that would forever change the history of mathematics. The subject was the mystery of prime numbers. At the heart of (more)

• print this page
• pages linking here
• related pages