PRINT LINKED RELATED

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: $7.50 You Save: $11.45 (60%) New (32) Used (23) from $7.50The 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)

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... List Price: $16.00 Buy New: $8.75 You Save: $7.25 (45%) New (38) Used (19) 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)

Bayesian Computation with R (Use R) List Price: $49.95 Buy New: $37.86 You Save: $12.09 (24%) New (36) Used (13) from $35.00There 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)

Euler's Gem: The Polyhedron Formula and the Birth of Topology List Price: $27.95 Buy New: $16.98 You Save: $10.97 (39%) New (31) Used (4) from $16.98Leonhard 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)

e: The Story of a Number List Price: $19.95 Buy Used: $2.94 You Save: $17.01 (85%) New (11) Used (37) Collectible (1) from $2.94The 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)

Not Even Wrong: The Failure of String Theory and the Search for Unity in Phys... List Price: $16.95 Buy New: $7.61 You Save: $9.34 (55%) New (33) Used (11) from $7.27When does physics depart the realm of testable hypothesis and come to resemble theology? Peter Woit argues that string theory isn't just going in the wrong direction, it's not even science. Not Even Wrong (more)

Killer Poker By the Numbers: Mathematical Edge for Winning Play List Price: $14.95 Buy New: $6.99 You Save: $7.96 (53%) New (34) Used (13) from $6.99Killer Poker By the Numbers: Mathematical Edge for Winning Play (more)

Elementary Number Theory (5th Edition) List Price: $124.00 Buy New: $99.20 You Save: $24.80 (20%) New (10) Used (18) from $28.00Elementary Number Theory and Its Applications is noted for its outstanding exercise sets, including basic exercises, exercises designed to help students explore key concepts, and challenging exercises. (more)

Complex Analysis for Mathematics and Engineering List Price: $124.95 Buy New: $44.94 You Save: $80.01 (64%) New (14) Used (14) from $44.94Revised and updated, the new Fifth Edition of Complex Analysis for Mathematics and Engineering presents a comprehensive, student-friendly introduction to Complex Analysis. It's clear, concise writing (more)

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills List Price: $29.95 Buy New: $14.75 You Save: $15.20 (51%) New (41) Used (16) from $14.49I 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)