1

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$?

Twnk
  • 2,436
  • 1
    Either way works. –  Feb 13 '14 at 04: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. – EpicMochi Feb 13 '14 at 04:32
  • 1
    Almost always, you will need to use induction or use results that were proved earlier by induction. – André Nicolas Feb 13 '14 at 04:38

3 Answers3

4

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.

gt6989b
  • 54,422
1

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.

Mauro ALLEGRANZA
  • 94,169
1

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.

2'5 9'2
  • 54,717