Is there any formal problem that cannot be proven using mathematical induction?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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