Okay to illustrate this problem, I'm going to need to give an example, and go through the steps of Mathematical Induction to show where my question is aimed at.
Example : Prove that $$ n^2 \geq 2n + 3,for, n\geq 3$$
Setting up in symbolic form we get :
$$D = \{ x |x \in \mathbb{Z}, x \geq 3 \}$$ $$P(n) = n^2 \geq 2n + 3$$
Required to Prove: $$ \forall n \in D, P(n)$$
Proof:
Base Case : Show that P(3) holds $$3^2 \geq 9$$ $$2(3)+3 = 9$$ $$ \therefore LHS = RHS$$ Therefore the base case holds.
Inductive Hypothesis: $$Assume: P(k) = k^2 \geq 2k +3$$
Inductive Step : Show P(k+1) holds
Now this is where my question comes in.
What I'm supposed to arrive at is the inequality below $$(k+1)^2 \geq 2(k+1) + 3$$ What I will arrive at however is something other than this, and I want to know if what I've arrived at is Mathematically correct, and whether it has proven what we've set out to prove by Mathematical Induction. This is it below.
$$(k+1)^2 = (k^2) + 2k + 1$$ $$(k+1)^2 \geq (2k+3) + 2k + 1 : by, I.H.$$ $$(k+1)^2 \geq 4k + 4$$ $$(k+1)^2 \geq 4(k+1)$$ $$(k+1) \geq 4$$ $$ \therefore k \geq 3$$
$$QED?$$
My Conclusion : Obviously, any k greater than or equal to 3 makes the last inequality $$k \geq 3$$ I reason that the inductive step, together with the fact that P(3) is true, results in the conclusion that $$\forall n \in D, P(n)$$.
The reason why I would think that this is a valid proof, and proves what I set out to prove using Mathematical Induction, has to do with the binary nature of Predicates.
Remember a predicate can be true or false, but not both. In the Induction Step, where we have to show that P(k+1) is true, we don't need to get it into the form (or maybe we do need it in this form I stand to be corrected, if I'm wrong please correct me here) : $$(k+1)^2 \geq 2(k+1) + 3$$
Instead of getting it into that form, since we are only trying to prove that the predicate P(k+1) is true, if there is no contradiction in the last step, i.e. as long as we reach something that is obviously true, then the predicate must be true. Only if we reach a contradiction then it must be false. Since there is no contradiction that I've reached in this proof, and $$k \geq 3, \forall k \in D$$ this must have indirectly proven the predicate P(k+1) to be true (again I stand to be corrected here)
And since we have used/incorporated the Inductive Hypothesis (our assumption) to show that no contradiction occurs when we have k+1, we have essentially shown P(k+1) to be true, even though we did not get P(k+1) into the form $$(k+1)^2 \geq 2(k+1) + 3 $$.
Question in a nutshell:
Essentially what I'm asking here in a nutshell is if it's fine to indirectly prove the Predicate in the inductive step (by showing that there is no contradiction when we incorporate the IH) rather than directly proving it be getting it into the form we a are looking for.
If any answers need the use of higher/more advanced Mathematics, please don't be afraid to post it, I'm always eager to learn new Math.
Answer
As @Ethan Bolker mentioned in the comment to my post above :
"Reaching something that is obviously true" is not a proof!
Which is exactly what I did here. For anyone who would like to read further how I realized this, the comments of this question : Is this direct proof of an inequality wrong? help to clarify why this is the case.
No comments:
Post a Comment