Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have a statement $P$ and I wanna prove that $P$ is true for all $n \in \Bbb N$, do I have to use induction or can I just take an arbitrary $k \in \Bbb N $ and prove that $P$ is true for $k$? (obviously I wouldn't use any induction hypothesis). Would that be enough to prove that $P$ holds for all $n \in \Bbb N$?

share|improve this question
1  
Either way works. –  user61527 Feb 13 at 4:30
1  
I think it depends on what you're actually trying to prove. I guess technically both methods will work, but some proofs might be much harder if you choose to not use induction. –  Petaro Feb 13 at 4:32
1  
Almost always, you will need to use induction or use results that were proved earlier by induction. –  André Nicolas Feb 13 at 4:38

3 Answers 3

up vote 4 down vote accepted

Both are valid and present equivalent techniques in terms of the achieved result, but the mechanics of the proof is different.

In an inductive construction, if you can prove the recurrence $p_k \Rightarrow p_{k+1}$ (which is easier sometimes than to prove $p_k$ outright), you just need to verify one initial condition (typically not hard to do) and you are done.

But some things can be done with both methods.

share|improve this answer

An interesting exercise can be, referring to S.C.Kleene, Introduction to Metamathematics (1952), page 183-on, trying to prove all the theorems of formal arithmetics (first-order logic with Peano's axioms) numberd from #100 :

$\vdash a = a$

to #160 :

$\vdash a|b \equiv \exists c(c \le b \land ac=b)$.

Some of them requires induction, others no.

share|improve this answer

For example, "For all $n\in\mathbb{N}$, there exists an $m\in\mathbb{N}$ with $m>n$" does not require induction to prove. You can just construct $m$ to be $n+1$.

There are some propositions though that I would find difficult to prove without it. You raise an interesting question regarding whether such propositions are impossible to prove without induction. But that question is kind of the opposite question of what you have asked here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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