Is there any proposition $\mathcal{P}(n)$ such that $\mathcal{P}(n)$ is true $\forall n \in \mathbb{N}$ but cannot be deduced using induction (regardless of its being true? i.e. $\mathcal{P}(k)$ being true does not necessarily implies that $\mathcal{P}(k+1)$ is also true.

Are there formal problems that cannot be proven using mathematical induction but require the use of direct proof?

  • 1
    $\begingroup$ As the answer from Yves Daoust points out, this question is meaningless: if $P(n)$ is true for all $n \in \Bbb{N}$, then $P(0)$ and $P(k) \implies P(k+1)$ must hold. $\endgroup$
    – Rob Arthan
    Feb 1 '18 at 1:24
  • $\begingroup$ Where is his answer? $\endgroup$
    – Narasimham
    Feb 8 '18 at 22:32

Goodstein's theorem is a well-known and "purely number-theoretic" theorem about natural numbers that can be expressed by means of a first order statement in the language of arithmetic but cannot be proved in first-order Peano Arithmetic, in particular cannot be proved by induction on $\mathbb{N}$. This thorem states that every Goodstein sequence eventually terminates at 0. The definition of Goodstein sequence is quite technical, see the Wikipedia page.

  • $\begingroup$ I think the OP is asking for a problem that is provable in usual arithmetic, but, particularly, not with induction. $\endgroup$ Jan 30 '18 at 15:39
  • $\begingroup$ @ΒασίληςΜάρκος - I don't think Fermat's Last Theorem (cited in orlp's answer) can be proved in usual arithmetic, even if it is a statement about natural numbers. $\endgroup$ Jan 30 '18 at 16:06
  • $\begingroup$ Yeap, I also have the same feeling, but I did not want to double post under two different answers. Actually, my objection is about provability in general. I feel, that, until a further clarification, @Yves Daoust's answer is the most accurate. $\endgroup$ Jan 30 '18 at 16:08
  • $\begingroup$ @ΒασίληςΜάρκος - I agree that the OP question is ambiguous and gives rise to very different answers. $\endgroup$ Jan 30 '18 at 16:11

Formally speaking, if $\mathcal{P}(k)$ and $\mathcal{P}(k+1)$ are both true, then

$$\mathcal{P}(k)\implies\mathcal{P}(k+1)$$ holds.

This makes your question a little pointless.

  • $\begingroup$ Hm... I get your point. My question was indeed ambiguous. But $P(k) \implies P(k+1)$ BECAUSE P(k) and P(k+1) were true then you have assumed the truth value of P(k+1) for granted. What I meant about P(n) is that you cannot deduce P(k+1) from P(k) even though $P(k) \implies P(k+1)$. I will revise my question. $\endgroup$
    – Minh Khôi
    Jan 30 '18 at 16:32

I think any sufficiently complicated statement dependent on $n$ will do. E.g.:

$a^{n+2} + b^{n+2} = c^{n+2}$ has no integer solutions for any $n \in \mathbb{N}$.

  • $\begingroup$ Yes, that would make sense. But what if there can be an induction proof for the proposition above, it's just that it is so complicated that no one could ever derive at? How can we make sure such complicated proposition like Fermat Last Theorem would have no possible induction proof? $\endgroup$
    – Minh Khôi
    Jan 30 '18 at 15:27
  • $\begingroup$ @MichaelDNguyen At this point you need to be more specific what you mean with 'induction proof', because it's not clear where you draw the line. $\endgroup$
    – orlp
    Jan 30 '18 at 15:30
  • $\begingroup$ Hm, can you explain that? Was my question being ambiguous? Can you suggest me a way to edit my question? $\endgroup$
    – Minh Khôi
    Jan 30 '18 at 15:31
  • $\begingroup$ You’re missing “nontrivial”. $\endgroup$
    – k.stm
    Jan 30 '18 at 15:37
  • $\begingroup$ Then there would be problems that can be solve using trivial induction proof and not nontrivial induction proof is not it? $\endgroup$
    – Minh Khôi
    Jan 30 '18 at 16:22

I could think of the following:

Let $x_1,x_2,\dots,x_n\in H$, where $H$ is equipped with a dot product $\langle\cdot,\cdot\rangle$. Also consider the matrix: $$A=\left(\begin{array}{cccc} \langle x_1,x_1\rangle & \langle x_1,x_2\rangle & \dots & \langle x_1,x_n\rangle \\ \langle x_2,x_1\rangle & \langle x_2,x_2\rangle & \dots & \langle x_2,x_n\rangle \\ \vdots & \vdots & \ddots & \vdots\\ \langle x_n,x_1\rangle & \langle x_n,x_2\rangle & \dots & \langle x_n,x_n\rangle \\ \end{array}\right)$$ Prove that: $$\det A\geq0$$ and that: $$\det A=0\Leftrightarrow x_1,x_2,\dots,x_n\text{ are linearly dependent}$$

Now, I have a (long) proof that does not use induction and, I think that this cannot be proved with induction, since:

  1. The case $n=1$ is trivial $\langle x_1,x_1\rangle=\lVert x_1\rVert^2\geq0$ and $\lVert x_1\rVert=0\Leftrightarrow x_1=0$.
  2. The case $n=2$ is as follows: $$\det A=\langle x_1,x_1\rangle\langle x_2,x_2\rangle-\langle x_1,x_2\rangle\langle x_2,x_1\rangle=\lVert x_1\rVert^2\lVert x_2\rVert^2-|\langle x_1,x_2\rangle|^2$$ So, proving the requested is equivalent to proving Cauchy-Schwarz inequality: $$|\langle x_1,x_2\rangle|\leq\lVert x_1\rVert\lVert x_2\rVert\tag{$\dagger$}$$

But, since $(\dagger)$ can be proved independently of the case $n=1$, there is not a non-trivial proof using induction starting from $n=1$.

But this is just a very specific thought, though...

  • $\begingroup$ In my opinion, every proof $\pi$ of an arithmetic theorem that uses only arithmetic concepts can be reformulated in a proof by induction on $\mathbb{N}$ in a trivial way: the base case is a special case of $\pi$ and the inductive step for $n+1$ is proved by $\pi$, without using the inductive hypothesis for $n$. $\endgroup$ Jan 30 '18 at 16:15
  • $\begingroup$ That's why I mention, non -trivial proof. Intuitively meaning that $p(\kappa)$ is essentially used to prove $p(\kappa+1)$. $\endgroup$ Jan 30 '18 at 16:17
  • $\begingroup$ Good point! But I have another objection (I'm sorry, I'm not polemic at all, I want just to understand your viewpoint): Is your statement an arithmetic statement? Can you define all the concept you use in your statement inside first-order Peano arithmetic? Even if it is so, do you really need Cauchy-Schwarz inequality to prove the statement? $\endgroup$ Jan 30 '18 at 16:32
  • $\begingroup$ It is not an arithmetic statement, at all, it is just a proposition in the requested form $P(n)$ that is true for every $n$ - even if the proof I have in mind has a lot of lines. I need Cauchy-Schwarz for the case $n=2$, for sure. For larger matices, it is sufficient to show that $A$ is positively defined - for any, arbitrary $n$. $\endgroup$ Jan 30 '18 at 16:39

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.