Is there any formal problem that cannot be proven using mathematical induction? 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?
 A: 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. 
A: 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.
A: 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}$.

A: 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:


*

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

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