Is it possible to prove by induction that $1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{n^2}<2\space\space \forall n\geqslant 1?$

Question

Let's denote the inequality in question by $A(n)$. I am looking for the way to prove this inequality using "direct induction" (see my question 1 below). By usual induction I mean $A(1)\&\left(\forall k\geqslant 2\space \left(A(k-1)\implies A(k)\right)\right)\implies\left(\forall n\geqslant1\space A(n)\right)$.

My questions are:

1) Is is possible to prove the statement $\forall n\geqslant 1\space A(n)$ by proving $A(n-1)\implies A(n)$ without using facts that imply $A(n)$? That is, by applying induction directly (it is allowed to use statements $C(n)$ that do not imply $A(n)$ and it is allowed to use induction hypothesis $A(n-1)$).
For instance using statement $\forall n\geqslant 1\sum\limits_{k=1}^n\frac{1}{k^2}\leqslant2-\frac{1}{n}$ is prohibited, because it implies that $A(n)$ is true and hence $A(n-1)\implies A(n)$ is true as well.
$ $

2) If it is not possible to prove $\forall n\geqslant 1 \space A(n)$ by direct induction, how one can rigorously prove this fact (the fact that it is impossible)? $ $

3) If it is possible to prove by direct induction $\forall n\geqslant 1 \space A(n)$ (can you show it?), are there examples of statements for which the proof by induction is impossible? Can you give an example? $ $
$ $

4) Is there some characterization of the set of statements $B(n)$ that possess the same or similar properties (something like "proving $B(n-1)\implies B(n)$ is not possible although $B(n)$ is true" or "proving $B(n-1)\implies B(n)$ is not easier than proving $B(n)$"). All statements of the "Inventor's paradox" type will fit, but probably there are some other examples.

Please note that I am not a specialist in mathematical logic, so the problem setup may lack rigor. But hopefully the idea is clear. If it is not, I am looking forward to suggestions on how to set the problem up in a meaningful way.

Answer 1

Here is an answer to the parts of your question:

1. It is not possible to prove your statement by direct induction. I take this to mean the proof is only allowed use the induction hypothesis. Otherwise the question becomes incredibly vague.
2. The reason why is given in the comments. An inductive hypothesis of $\sum\limits_{k=1}^n\frac{1}{k^2}<2$ is too weak to imply $\sum\limits_{k=1}^{n+1}\frac{1}{k^2}<2$. The reason, as given in the comments, is that $\sum\limits_{k=1}^{n+1}\frac{1}{k^2}<2$ could give you any number less than $2$, including all numbers $x$ with $2 - \frac{1}{(n+1)^2} < x < 2$. All such $x$ will violate the condition for $n+1$.
3. Not applicable.
4. This is a very broad question and it is quite ambiguous. It depends on what you mean by "easier". It also depends on what you mean by "proof".

Overall, I will just comment that the question you ask is very meta-mathematical. Such questions need to be very rigorously formulated or they don't really have any meaning. We can only talk about things like proofs if we start reasoning about them in a formal manner, and then we get into formal proof systems and all sorts of impossibility results like incompleteness theorems and undecidability.

Answer 2

HINT: prove that $\frac{1}{k^2}\le \frac{1}{k(k-1)}$ for $k>1$