Prove modified Second Principle of Math Induction

In summary, the Second Principle of Mathematical Induction is a proof technique used to prove statements involving natural numbers. It is based on the idea that if a statement is true for a base case and can be shown to be true for n+1 whenever it is true for n, then it is true for all natural numbers. The Modified Second Principle of Mathematical Induction expands on this by allowing for different base cases and is important because it allows for more versatile use in proofs. An example of using the Modified Second Principle is to prove the sum of the first n odd natural numbers is equal to n^2.
  • #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.

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:
Physics news on Phys.org
  • #2
Yes, your second proof is correct. You can also prove it using contrapositive. Assume that P(n) is false for some n ≥ nσ. Then, by the well-ordering principle, there is a smallest element in the set S = {n : P(n) is false} which we call nσ. This implies that P(nσ) is false and, thus, contradicts i).
 

1. What is the Second Principle of Mathematical Induction?

The Second Principle of Mathematical Induction is a proof technique used in mathematics to prove statements that involve natural numbers. It states that if a statement is true for a base case (usually n=1) and if it can be shown that the statement is also true for n+1 whenever it is true for n, then the statement is true for all natural numbers n.

2. How is the Second Principle of Mathematical Induction used?

The Second Principle of Mathematical Induction is used to prove statements involving natural numbers, such as number patterns or divisibility rules. It is a powerful tool in mathematics and is commonly used in fields such as number theory, algebra, and combinatorics.

3. What is the Modified Second Principle of Mathematical Induction?

The Modified Second Principle of Mathematical Induction is a variation of the Second Principle that allows for a different base case, such as n=0 or n=2. It is used when the statement being proved is not true for n=1, but is still true for all other natural numbers. It can also be used when the statement involves negative integers.

4. Why is the Modified Second Principle of Mathematical Induction important?

The Modified Second Principle of Mathematical Induction expands the scope of the Second Principle and allows for more versatile use in mathematical proofs. It also allows for the proof of statements that may not be true for the traditional base case of n=1.

5. Can you provide an example of using the Modified Second Principle of Mathematical Induction?

Yes, an example of using the Modified Second Principle of Mathematical Induction would be to prove that the sum of the first n odd natural numbers is equal to n^2. The base case could be n=0, and then using the modified induction step of n+2, the statement can be shown to be true for all other positive integers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
24
Views
672
  • Calculus and Beyond Homework Help
Replies
7
Views
338
  • Calculus and Beyond Homework Help
Replies
8
Views
927
  • Calculus and Beyond Homework Help
Replies
5
Views
849
  • Calculus and Beyond Homework Help
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
870
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
151
  • Calculus and Beyond Homework Help
Replies
6
Views
983
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top