# Statements true for all integers but not provable by induction

Is there any examples of statements P(n) such that "for all $n>1$, P(n)" is provable, but P(n)=>P(n+1) is not provable? (without using some mild deformation of "for all $n>1$, P(n)"=>"P(n)=>P(n+1)"?

-
Well, if $P(n+1)$ is true, then $P(n) \Rightarrow P(n+1)$ is true regardless of whether $P(n)$ is. – dtldarek Jun 7 '12 at 12:32
There are results such as Goodstein's Theorem and a certain strengthening the finite Ramsey Theorem which are not provable in Peano Arithmetic. – arjafi Jun 7 '12 at 12:49
@GJB: It would help, I think, if you asked what you are actually looking for, rather than trying to pose a problem along with an ad-hoc dismissal of the obvious answer to the problem. – Hurkyl Jun 7 '12 at 13:22
+1 Hurkyl. Speficifically, if you want to exclude proofs that are "mild deformations of" the obvious one, you owe us a definite and operational definition of which proofs you accept and which ones you don't. – Henning Makholm Jun 7 '12 at 15:25
Sometimes you need $\forall k\leq n. P(k)$ as induction hypothesis. – Raphael Jun 7 '12 at 23:13

How about, "for all $n$, the $n$th digit in the decimal expansion of $1/3$ is 3"?

EDIT: OK, no one likes this example, I'll try another one: for all $n$, the Riemann zeta function has more than $n$ zeros in the critical strip.

-
1/3 is rational, so it has periodic decimals. I guess we could use this fact and a period as a base case. – user1708 Jun 7 '12 at 12:38
Not sure I see this. If you know that it's periodic and the repeating part is a 3 then I'm not sure there's anything to prove. – Gerry Myerson Jun 7 '12 at 12:53

Provable in what? Note that provability is always w.r.t. to some formal system/theory, otherwise it is meaningless. Often it is omitted because it is clear from context what formal system we are using but in your question it is not clear.

To answer the question in the title, assume that $T$ is a rich-enough (e.g. contains Robinson's $Q$) effective (i.e. recursive system of axioms) first-order theory about natural number. Then by Godel's theorem there is a sentence of the form $\forall x \varphi(x)$ which is true but unprovable. Moreover for every natural number $n$ $T$ proves $\varphi(n)$. Theory $T$ can contain induction.

To answer the question in the post, if $\forall x \varphi(x)$ is provable in some theory $T$ then it follows by logic that for all terms $t$, $T$ proves $\varphi(t)$. Let $t=x+1$, then $T$ prove $\varphi(x+1)$ and again by logic it follows that $T$ proves $\varphi(x) \rightarrow\varphi(x+1)$. In other words, if $\forall x \varphi(x)$ is provable then $\forall x [\varphi(x) \rightarrow \varphi(x+1)]$ is also provable.

-

This paper has one such example and this paper has general method for obtaining statements that are not provable in PA.

-