Mathematical Induction I & II
Question 1
1) What do you show in the basis step and what do you show in the inductive step when you use (ordinary) mathematical induction to prove that a property involving an integer n is true for all integers greater than or equal to some initial integer? - You may use example of problems to explain this answer.
Answer
Let P(n) be a property that is defined for integers n, and let a be a fixed integer. Suppose the following two statements are true:
1. P(a) is true. 2. For all integers k ≥a, ifP(k) is true then P(k +1) is true. Then the statement for all integers n ≥a, P(n)is true.
1. P(a) is true. 2. For all integers k ≥a, ifP(k) is true then P(k +1) is true. Then the statement for all integers n ≥a, P(n)is true.
Consider a statement of the form, “For all integers n ≥a, a property P(n) is true.” To prove such a statement, perform the following two steps: Step 1 (basis step): Show that P(a) is true. Step 2 (inductive step): Show that for all integers k ≥a, ifP(k) is true then P(k +1) is true. To perform this step, suppose that P(k) is true, where k is any particular but arbitrarily chosen integer with k ≥a. [This supposition is called the inductive hypothesis.] Then show that P(k +1) is true.
Example
For all integers n ≥ 8, nc / can be obtained using 3c / and 5c / coins.
Proof (by mathematical induction):
Let the property P(n) be the sentence
Let the property P(n) be the sentence
nc / can be obtained using 3c / and 5c / coins. ← P(n)
Show that P(8) is true:
P(8) is true because 8c / can be obtained using one 3c / coin and one 5c / coin.
Show that for all integers k≥8, if P(k) is true then P(k+1) is also true:
[Suppose that P(k) is true for a particular but arbitrarily chosen integer k ≥ 8. That is:]
Suppose that k is any integer with k ≥ 8 such that
kc / can be obtained using 3c / and 5c / coins. ←P(k)inductive hypothesis
[We must show that P(k +1) is true. That is:] We must show that
(k +1)c / can be obtained using 3c / and 5c / coins. ← P(k +1)
Case 1
(There is a 5 c / coin among those used to make up the kc /.):
In this case replace the 5c / coin by two 3c / coins; the result will be (k +1)c /.
Case 2
(There is not a 5 c / coin among those used to make up the kc /.):
In this case, because k ≥ 8, at least three 3c / coins must have been used.
So remove three 3c / coins and replace them by two 5c / coins; the result will be (k +1)c /. Thus in either case (k +1)c / can be obtained using 3c / and 5c / coins [as was to be shown].
[Since we have proved the basis step and the inductive step, we conclude that the propo- sition is true.]
[Since we have proved the basis step and the inductive step, we conclude that the propo- sition is true.]
Question 2
2) What is the inductive hypothesis in a proof by (ordinary) mathematical induction?
Answer
Inductive
hypothesis is the supposition in inductive step for P(n).
Way to state inductive hypothesis :
If P(k) is a true, then P(k + 1) is true.
:: We need to assumes
the inductive hypothesis for P(k) is
true before we can proof that P(x-1) is true.
Question 3
3) Are you able to use (ordinary) mathematical induction to construct proofs involving various kinds of statements such as formulas, divisibility properties and inequalities? - You may use example of problems to explain this answer. Give examples of question for each type of problems (formulas, divisibility properties and inequalities)
Answer
By Formula
Show that if n is a positive integer, then
1 + 2+· · ·+n =
Solution :
Let P(n) = 1 + 2+· · ·
n = n(n+1)/2 is
.
Prove that P(n) is true for n = 1, 2, 3, . . . .
BASIS STEP:
P(1) is true, because
1 = 1(1 + 1).
~ The left-hand side of this equation is 1 because 1 is the sum of the first
positive integer. The right-hand side is found by substituting 1 for n in
.
INDUCTIVE STEP:
For the inductive hypothesis we assume that
P(k) holds for an arbitrary positive
integer k. That is, we assume
that 1 + 2+· · ·+k =
Under this assumption, it must be shown
that P(k + 1) is true, namely, that
1 + 2+· · ·+k + (k + 1) =
=
is also true. When we add k + 1 to both
sides of the equation in P(k),
we obtain
1 + 2+· · ·+k + (k + 1) =
+ (k + 1) =
=
=
This last equation shows that P(k + 1) is true under the
assumption that P(k) is true.
This completes the inductive step.
Therefore,
P(n) is true for all positive integers n. That is, we have proven that 1 +
2+· · ·+n =
for
all positive integers n.
Divisibility Properties
Use mathematical induction to prove that n³− n is divisible by 3 whenever n is a positive integer.
Solution:
To construct the proof, let P(n) denote the proposition: “n³
− n is divisible by
3.”
BASIS STEP:
The statement P(1) is true
because 1³ − 1 = 0 is divisible by 3. This completes the basis step.
INDUCTIVE STEP:
Assume that P(k) is
true; that is, we assume that k³ − k
is divisible by 3 for an arbitrary positive integer k.
Then, P(k + 1) = (k +
1)³ − (k + 1) is divisible by 3, is also true.
That is, we must show that
(k + 1) ³ − (k
+ 1) is divisible by 3.
Expand : (k + 1) ³ − (k + 1) = (k³ + 3k² + 3k + 1) − (k + 1)
= (k³ − k)
+ 3(k² + k).
Therefore,
n³ − n is divisible by 3
whenever n is a positive
integer.
Inequalities
Use mathematical induction to prove the
inequality n < 2ⁿ for
all positive integers n.
Solution:
Let P(n)
be the proposition that n < 2ⁿ.
BASIS STEP:
P(1) = 1 <
= 2, true.
INDUCTIVE STEP:
Assume the inductive hypothesis that P(k)
is true for an arbitrary positive integer k.
P(k + 1) = k + 1 <
, is true.
To show that this conditional statement is
true for the positive integer k, we first add 1 to both sides of
k <
,
and then note that 1 ≤
.
This tells us that
k + 1 <
≤ 2k + 2k = 2 · 2k = 2k+1.
This shows that P(k + 1) is
true, namely, that k + 1 <
, based on the assumption that P(k)
is true. The induction step is complete.