1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @Ethan Bolker. Ah okay, I see my error now, reduction to a truth as is the case with what I did above, proves nothing. $\endgroup$ – Perturbative Apr 2 '16 at 23:25
  • 1
    $\begingroup$ Your argument is backwards. "Reaching something that is obviously true" is not a proof!.Your question is essentially a duplicate of this one: math.stackexchange.com/questions/1723937/… . Although the algebra in there is not the same as the algebra here, the logical fallacy is just the same. Absorb the answers there and you should be able to answer your own question. $\endgroup$ – Ethan Bolker Apr 2 '16 at 23:27
0
$\begingroup$

Esentially what you have proved is nothing else than:

Assume : $ k^2 \geq 2k + 3 $ then $ k \geq 3 $

This can be easily derived: $$ k^2 - 2k - 3 = (k-3)(k+1) \geq 0 \rightarrow k \geq 3 $$

So your proof is correct (is just a rearrange of the above steps)

but it is not using the inductive principle, since you are not proving that $P(k+1)$ is true.

What you have done is find the set that belongs to an assumption.

$$IH(k) \rightarrow k \in A$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.