2
$\begingroup$

Hello mathematics community,

Today I was studying mathematical induction which is an axiom.

I was wondering

  1. Can "ANY" identity or inequality involving integers which is already proven can also be proved by mathematical induction?

  2. Are there any theorems which can only be proved using mathematical induction?

3.As far as I know we have first principle of mathematical induction, second principle of mathematical induction

Do we have nth principle of mathematical induction also, if yes can I know problems involving it.(n value being larger upto 10 or even more).

I dont know what tags are to be kept for this question....

Thankyou for your valuable time.

EDIT

I have found the answer for the third question and the example of such a problem is to prove the that the number of triangles in a triangulation of polygon of n sides is n-2. Here is the link https://www.youtube.com/watch?v=Z9sYIWHIvNc

$\endgroup$
  • $\begingroup$ What do you mean by $n$-th principle of mathematical induction? $\endgroup$ – user 170039 Oct 19 '14 at 6:24
  • $\begingroup$ If you found an example for part of your question, you should either edit it into the question, or submit it as an answer. These discussions are not only for the question submitter. $\endgroup$ – Slade Oct 19 '14 at 7:44
  • $\begingroup$ I meant the extended principle of mathematical induction @user170039 $\endgroup$ – Jasser Oct 19 '14 at 9:17
  • $\begingroup$ edited the question @Slade $\endgroup$ – Jasser Oct 19 '14 at 9:18
  • 3
    $\begingroup$ The answer to your question (2) is very nearly "yes", because the natural numbers (= the set of non-negative integers) are defined by the Peano axioms [see Wikipedia]. These say, in essence, (i) that $0$ is a number, (ii) if $n$ is a number then $n+1$ is a number, and (iii) that induction works. And any proof about natural numbers has to be derived from these axioms. So apart from a few statements like "$\forall n (n + 1 \neq 0)$" derived from the non-inductive axioms [1-8 on the Wikipedia page], every theorem uses induction everywhere. Even the proof that $\forall x\forall y (x+y = y+x)$. $\endgroup$ – HTFB Oct 19 '14 at 15:50
2
+25
$\begingroup$

As a logical matter, the answer to 1. is yes, since any proof could be inserted into an inductive proof. As a practical matter, the answer is no, since some proofs about integers are best proven using fields in which integers are embedded (real or complex numbers, for example).

The answer to 2. is yes, if you mean "require the assumptions that induction uses". In particular, when using mathematical induction on integers we assume the set of natural numbers is well ordered (every nonempty subset has a least element). This assumption is equivalent to the Axiom of Choice.

$\endgroup$
1
$\begingroup$

Here is an integer identity which can easily be proved, but not by induction:

$$p\in\mathbb{P}\implies[p=2]\vee[p=3]\vee[p\equiv\pm1\pmod6]$$

However, I have no idea how to prove that it cannot be proved by induction.

$\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.