- #1
IntroAnalysis
- 64
- 0
1. Prove the following modified version of the second principle of mathematical induction:
Let P(n) be a statement for each n Є Z (set of all integers). If
a) P(nσ), (Pnσ + 1), ...,P(m) is true, and
b) for k ≥ m, if P(i) is true for nσ ≤ i ≤ k, then P(k + 1) is true,
then P(n) is true for all n ≥ nσ, n Є Z.
Can someone tell me if below is correct? and/or a simpler proof?
Proof:
Assume that P(n) is a statement about the variable n such that
i. P(nσ) Λ (Pnσ + 1) Λ ...Λ P(m) is true, and
ii. for k ≥ m, if P(i) is true for nσ ≤ i ≤ k, then P(k + 1) is true,
In addition, assume that P(n) is not true for some n Є Z. Since
P(n) is false for some n Є Z, the set
S = {n:P(n) is false} is a nonvoid subset of Z. As such, by the well-ordering principle,
S has a smallest member ; call it nσ. Since nσ is the smallest member of S, P(nσ) is false
and P(Nσ -1) is true. But, if P(k) is true, then P(K+ 1) is true. So, if we let k = nσ - 1,
then P(k) is true, but k + 1 = nσ and P(k + 1) is false . This is a contradiction. Hence, by method of proof contradiction, the theorem is true.
Or can I just go from P(nσ) is false is a contradiction of i. P(nσ) is true. Hence,
by method of proof contradiction, the theorem is true.
Let P(n) be a statement for each n Є Z (set of all integers). If
a) P(nσ), (Pnσ + 1), ...,P(m) is true, and
b) for k ≥ m, if P(i) is true for nσ ≤ i ≤ k, then P(k + 1) is true,
then P(n) is true for all n ≥ nσ, n Є Z.
Homework Equations
The Attempt at a Solution
Can someone tell me if below is correct? and/or a simpler proof?
Proof:
Assume that P(n) is a statement about the variable n such that
i. P(nσ) Λ (Pnσ + 1) Λ ...Λ P(m) is true, and
ii. for k ≥ m, if P(i) is true for nσ ≤ i ≤ k, then P(k + 1) is true,
In addition, assume that P(n) is not true for some n Є Z. Since
P(n) is false for some n Є Z, the set
S = {n:P(n) is false} is a nonvoid subset of Z. As such, by the well-ordering principle,
S has a smallest member ; call it nσ. Since nσ is the smallest member of S, P(nσ) is false
and P(Nσ -1) is true. But, if P(k) is true, then P(K+ 1) is true. So, if we let k = nσ - 1,
then P(k) is true, but k + 1 = nσ and P(k + 1) is false . This is a contradiction. Hence, by method of proof contradiction, the theorem is true.
Or can I just go from P(nσ) is false is a contradiction of i. P(nσ) is true. Hence,
by method of proof contradiction, the theorem is true.
Homework Equations
The Attempt at a Solution
Last edited: