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)"?
 A: 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.
A: 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. 
