5.1 Mathematical Induction Flashcards
How is Mathematical Induction going to help? discovering new formulas?
mathematical induction can be used
only to prove results obtained in some other way. It is not a tool for discovering formulae or
theorems.
Used to assert that P(n) is true for all positive integers n, where P(n) is a propositional function.
Vocab Warning | Use of words:
Mathematical proofs, including arguments that
use mathematical induction, are deductive, not inductive.
In logic, deductive reasoning uses rules of inference to draw conclusions from premises, whereas inductive reasoning makes conclusions only supported, but not ensured, by evidence.
PRINCIPLE OF MATHEMATICAL INDUCTION
express as rule of Inference:
To prove that P(n) is true for all positive
integers n, where P(n) is a propositional function, we complete two steps:
BASIS STEP: We verify that P(1) is true.
INDUCTIVE STEP: We show that the conditional statement P(k) → P(k + 1) is true for all
positive integers k.
(P(1) ∧ ∀ k(P(k) → P(k + 1))) → ∀ nP(n)
Domain : Set of positive Integers.
Inductive Hypothesis:
To complete the inductive step of a proof using the principle of mathematical induction, we
assume that P(k) is true for an arbitrary positive integer k and show that under this assumption,
P(k + 1) must also be true. The assumption that P(k) is true is called the inductive hypothesis.
Doubt that Mathematical Induction is some fallacy:
In a proof by mathematical induction it is not assumed that P(k) is true for all positive
integers! It is only shown that if it is assumed that P(k) is true, then P(k + 1) is also true. Thus,
a proof by mathematical induction is not a case of begging the question, or circular reasoning.
Well Ordering Property:
An axiom for the set of positive integers, which states
that every nonempty subset of the set of positive integers has a least element.
Why mathematical Induction is valid?
It comes from Well ordering property.
Now, Suppose we know P(1) is true and that
P(k) -> P(k+1) is true for all positive integers k.
To show that P(n) must be true for all positive integers n, assume that there is at least one positive integer n for which P(n) is false.
Then the set S of positive integers n for which P(n) is false is nonempty.
And by well ordering S has least element, let that be m.
Now, m != 1.
also, P(m-1) not in S.
and by P(m-1) -> P(m) we get a contradiction.
Henc P(n) must be true for every positive integer.
Well ordering and Principle of Mathematical Induction:
They are equivalent. Ws showed one way, we could show other way to: take this principle as axiom and prove that positive integers are well ordered.
Choosing the Correct Basis Step:
Often, we will need to show that P(n) is true for n =
b, b + 1, b + 2, … , where b is an integer other than 1.
We can use mathematical induction
to accomplish this, as long as we change the basis step by replacing P(1) with P(b).
In the inductive step,
we show that the conditional statement P(k) → P(k + 1) is true for k = b, b + 1, b + 2, …. Note
that b can be negative, zero, or positive.
Template for proofs by mathematical Induction:
page 335:
1. Express the statement that is to be proved in the form “for all n ≥ b, P(n)” for a fixed
integer b. For statements of the form “P(n) for all positive integers n,” let b = 1, and for
statements of the form “P(n) for all nonnegative integers n,” let b = 0. For some statements
of the form P(n), such as inequalities, you may need to determine the appropriate value
of b by checking the truth values of P(n) for small values of n, as is done in Example 6.
The Good and the Bad of Mathematical Induction:
You can prove a theorem by mathematical induction even if you do not have the slightest idea why it is true!
As we noted, mathematical induction is not a tool for finding theorems about all positive
integers. Rather, it is a proof method for proving such results once they are conjectured.
Sum of first n odd positive integers:
1 + 3 + 5 + ⋯ + (2n − 1) = n^2
PROVING INEQUALITIES
Mathematical induction can be used to prove a variety of inequalities that hold for all positive integers greater than a particular positive integer
An Inequality for Harmonic Numbers The harmonic numbers Hj,
j = 1, 2, 3, … , are
defined by
Hj = 1 +1/2 +1/3 + ⋯ +1/j.
Prove it.
Hv(2^n) ≥ 1 +n/2
Remark: The inequality established here shows that the harmonic series
1 + 1/2 + 1/3 + ⋯ + 1/n + ⋯
is a divergent infinite series. This is an important example in the study of infinite series.
Go through examples.
DA : Example 9, Example 12. example 13.
