27 ## MATHEMATICAL INDUCTIONThe principle of mathematical induction THE NATURAL NUMBERS are the counting
numbers: 1, 2, 3, 4, etc. Mathematical induction is a technique for proving a statement -- a theorem, or a formula -- that is asserted about By "every", or "all," natural numbers, we mean any one that we name. For example, 1 + 2 + 3 + . . . + This asserts that the sum of consecutive numbers from 1 to 1 + 2 + 3 = ½ -- which is true. It is also true for 1 + 2 + 3 + 4 = ½ But how are we to prove this rule for The method of proof is the following. We show that This is called the principle of mathematical induction.
To prove a statement by induction, we must prove parts 1) and 2) above. The hypothesis of Step 1) -- "
Example 1.
Prove that the sum of the first
This is the induction assumption. Assuming this, we must prove that the formula is true for its successor,
To do that, we will simply add the This is line (2), which is the first thing we wanted to show. Next, we must show that the formula is true for 1 = ½ -- which is true. We have now fulfilled both conditions of the principle of mathematical induction. The formula is therefore true for every natural number. (In the Appendix to Arithmetic, we establish that formula directly.)
Example 2. Prove that this rule of exponents is true for every natural number (
( With this assumption, we must show that the rule is true for its successor, ( (When using mathematical induction, the student should always write exactly what is to be shown.) Now, given the assumption, line (3), how can we produce line (4) from it ? Simply by multiplying both sides of line (3) by
This is line (4), which is what we wanted to show. So, we have shown that if the theorem is true for any specific natural number Next, we must show that the rule is true for ( But ( This rule is therefore true for every natural number Example 3. The sum of consecutive cubes. Prove this remarkable fact of arithmetic: 1 "The sum of In other words, according to Example 1:
This is line (2), which is what we wanted to show. Finally, we must show that the formula is true for
-- which is true. The formula therefore is true for every natural number. In the Appendix to Arithmetic, we show directly that that is true.
Problem 1. According to the principle of mathematical induction, to prove a statement that is asserted about every natural number a) What is the first? To see the answer, pass your mouse over the colored area.
b) What is the second?
The statement is true for c) Part a) contains the induction assumption. What is it?
The statement is true for
Problem 2. Let a) b)
Problem 3. 1 + 3 + 5 + 7 + . . . + (2 a) To prove that by mathematical induction, what will be the induction
The statement is true for
1 + 3 + 5 + 7 + . . . + (2 b) On the basis of this assumption, what must we show?
The statement is true for its successor,
1 + 3 + 5 + 7 + . . . + (2 k + 1)².c) Show that.
On adding 2
d) To complete the proof by mathematical induction, what must we show? The statement is true for e) Show that.
1 = 1 Problem 4. Prove by mathematical induction:
If we denote that sum by
Now show that the formula is true for
Begin:
Next,
The formula is true for
Therefore it is true for all natural numbers. Please make a donation to keep TheMathPage online. Copyright © 2021 Lawrence Spector Questions or comments? E-mail: [email protected] |