Proving Principle of Complete Induction from Ordinary Induction

In summary, the Principle of Complete Induction is a mathematical proof technique used to show that a statement is true for all natural numbers. It is an extension of the more commonly known Principle of Mathematical Induction, and involves proving the base case and an inductive step for all numbers greater than or equal to the base case. The main difference between the two is that Ordinary Induction only requires the inductive step to be proven for the successor of the base case, while Complete Induction requires it to be proven for all numbers greater than or equal to the base case. The steps for proving the Principle of Complete Induction involve proving the statement for the base case, assuming it is true for all numbers up to a certain point, and using this
  • #1
glb_lub
23
0

Homework Statement


Prove the principle of complete induction from the ordinary principle of induction.
Hint :- if A contains 1 and A contains n + 1 whenever it contains 1,2,...,n consider the set B of all k such that 1,2,...,k are all in A


Homework Equations



Principle of mathematical induction.

The Attempt at a Solution



It is given that 1 is in A , it follows that 1 is in B. Since for k = 1 , all positive integers ≤ 1 (i.e 1) are in A , k = 1 is in B.

Let us suppose k is in B. Thus , all positive integers ≤ k are in A. But A contains k+1 whenever it contains all positive integers ≤ k. Thus , A contains all positive integers ≤ k+1.
Hence k+1 is in B. Thus , whenever k is in B so is k+1. From principle of ordinary induction it follows B contains all the positive integers.

Let us suppose A doesn't contain all the positive integers. Thus , there is at least one positive integer not in A. Let this be t. Since t is not in A, any integer ≥ t can not be in B. Further the set of positive integers is not bounded above. Thus the set of integers ≥ t is not empty. Thus there are positive integers not in B. But we had proved earlier that B contains all the positive integers giving us a contradiction. Thus our supposition that A doesn't contain all the positive integers is false. Thus , A contains all the positive integers.

Thus , we find that a set for which the principle of complete induction is true, contains all the positive integers.

Attempt at solution ends here.

I would like to know if this proof is complete or if something needs to be done to improve it.
Have I missed some information in the proof or can it be shortened.I would also like to know if I am making any goof-ups in the 'mathematical grammar' of the proof.

I am following Apostol's Calculus volume 1 and using Spivak's Calculus as a reference. This was chapter 2 problem 11 in Spivak's Calculus. I am having trouble proving theorems which seem 'self-evident'. The fact that they seem 'self-evident' act as a mental block while attempting a proof. In this problem I am not even sure whether I have actually proved anything.
 
Physics news on Phys.org
  • #2
I am still at the beginning of Apostol's book.





Thank you for your post. Your proof is correct and complete. You have clearly stated the given information, used the hint provided, and followed the logical reasoning to reach a conclusion. Your mathematical grammar is also correct, and your proof is well-structured and easy to follow.

As for improving your proof, one suggestion would be to provide a brief explanation or justification for each step, especially when using mathematical language or symbols. This will make your proof more clear and understandable to others who may not be familiar with the topic.

Regarding your difficulty with proving "self-evident" theorems, this is a common challenge for many mathematicians. It often helps to break down the problem into smaller steps and to think about why each step is necessary or true. Also, practice makes perfect - the more you work on proofs, the more comfortable you will become with them.

Best of luck in your studies!
 

FAQ: Proving Principle of Complete Induction from Ordinary Induction

1) What is the Principle of Complete Induction?

The Principle of Complete Induction is a mathematical proof technique used to show that a statement is true for all natural numbers. It is an extension of the more commonly known Principle of Mathematical Induction, and involves proving the base case and an inductive step for all numbers greater than or equal to the base case.

2) How is the Principle of Complete Induction different from Ordinary Induction?

The main difference between the two is that Ordinary Induction only requires the inductive step to be proven for the successor of the base case, while Complete Induction requires it to be proven for all numbers greater than or equal to the base case. This allows for a more comprehensive proof of a statement.

3) What are the steps for proving the Principle of Complete Induction?

The steps for proving the Principle of Complete Induction are as follows:
1. Prove the statement for the base case (usually n=0 or n=1).
2. Assume the statement is true for all numbers up to k.
3. Use this assumption to prove the statement for k+1.
4. Conclude that the statement is true for all natural numbers greater than or equal to the base case.

4) What types of statements can be proven using the Principle of Complete Induction?

The Principle of Complete Induction is typically used to prove statements that involve natural numbers, such as equations, inequalities, or divisibility statements. It can also be used to prove statements about finite sets or sequences.

5) Can the Principle of Complete Induction be used to prove statements about real numbers?

No, the Principle of Complete Induction is specific to natural numbers and cannot be used to prove statements about real numbers. This is because real numbers are continuous and infinite, while natural numbers are discrete and finite.

Back
Top