# A (probably trivial) induction problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting to solve. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling with some algebraic gymnastics for a while now, but I can't seem to get the proof right. Proving it using calculus isn't a problem, but I'm struggling hither.

-
Why do you think that this problem can be solved using induction? –  joriki Jul 24 '12 at 22:08
@joriki the person who gave it to me said it could? So, ethos I guess... –  Paquito Jul 24 '12 at 22:10
what about comparing it with $ln2$ –  Theorem Jul 24 '12 at 22:17

As often happens with induction proofs, the easiest approach to proving this statement (which doesn't seem inducable at all - after all, how does knowing the sum for $n$ is less than $1$ tell you anything about the sum for $n+1$?) via induction is to transform it into a stronger one: $$\mathrm{For\ all\ } n\geq2, \frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2} \lt 1-\frac{1}{n}.$$

Now, the answer becomes a matter of simple algebra:

$$\sum_{i=2}^{n+1} \frac{1}{i^2} = \sum_{i=2}^{n} \frac{1}{i^2} +\frac{1}{(n+1)^2}\lt 1-\frac{1}{n}+\frac{1}{(n+1)^2}\lt 1-\frac{1}{n}+\frac{1}{n(n+1)} = 1-\frac{1}{n+1}.$$

-
Awesome! Many thanks...Might I ask what motivated the choice of subtracting 1/n? –  Paquito Jul 24 '12 at 22:21
@Paquito To a certain extent, intuition - since the difference between consecutive terms of the form $1/n$ is on the order of $1/n^2$, I could see that adding a quadratic term to a $1/n$-sized 'gap' between the sum and 1 would give a $1/n+1$-sized gap; from there it was just a quick dig to see whether $1-1/n$ itself would work or whether I would need to do something like $1-1/(n+1)$. –  Steven Stadnicki Jul 24 '12 at 22:26
That's beautiful, Steven! –  Bruno Joyal Jul 24 '12 at 22:40
Of course, this is also the "integral test" estimate. –  Robert Israel Jul 24 '12 at 23:53
@Paquito What Steven did is a classical example of inventor's paradox. Similarly proving $\frac{(2n-1)!!}{(2n)!!} < \frac{1}{\sqrt{n}}$ does not give in to the method of induction, while a stronger inequality $\frac{(2n-1)!!}{(2n)!!} < \frac{1}{\sqrt{n+1}}$ readily does. The explanation for why this works, is that the assumptions of the induction step are stronger in the latter case, allowing to draw stronger conclusion. –  Sasha Jul 25 '12 at 1:22

Another proof is by comparison: note that

$${1 \over k^2} < {1 \over (k-1)k}$$

for all integers $k \ge 2$. Therefore

$${1 \over 2^2} + {1 \over 3^2} + \cdots + {1 \over n^2} < {1 \over 1 \times 2} + {1 \over 2 \times 3} + \cdots + {1 \over (n-1) \times n}$$

and now you need to find the sum on the right-hand side. But you can actually write

$${1 \over (k-1)k} = {1 \over k-1} - {1 \over k}$$

(this is just the usual partial fraction decomposition) and therefore

$${1 \over 1 \times 2} + {1 \over 2 \times 3} + \cdots + {1 \over (n-1) \times n} = \left( {1 \over 1} - {1 \over 2} \right) + \left( {1 \over 2} - {1 \over 3} \right) + \cdots + \left( {1 \over n-1} - {1 \over n} \right)$$

and the right-hand side what's called a telescoping sum'' -- that is, the pairs of terms $-1/2$ and $+1/2$, $-1/3$ and $+1/3$, and so on cancel. So the right-hand side is $1 - 1/n$, which is less than 1.

This came to mind pretty much immediately for me, because I happened to know that $\sum_{k \ge 2}^\infty 1/(k(k-1)) = 1$, but if you didn't know that ahead of time it would be a bit tricky to discover.

-

Yet another approach :

Let us first analyze the sum till infinity. Let $$S= \frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}+ \cdots \infty$$ $$\Rightarrow S=(\frac{1}{2^2}+\frac{1}{4^2}+ \cdots\infty) +(\frac{1}{3^2}+\frac{1}{5^2}+ \cdots\infty )$$$$\Rightarrow S= \frac{1}{4}(1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots\infty)+ S'$$ Where $$S'=\frac{1}{3^2}+\frac{1}{5^2}+ \cdots\infty$$ $$\Rightarrow S=\frac{1}{4}(1+S)+S'$$ $$\Rightarrow 3S=4S'+1........ Eqn(1)$$ Now examine the following inequality $$(\frac{1}{2^2}-\frac{1}{3^2})+(\frac{1}{4^2}-\frac{1}{5^2})+ \cdots \infty > 0$$ $$\Rightarrow \frac{1}{2^2}+\frac{1}{4^2}+\cdots > \frac{1}{3^2}+\frac{1}{5^2}+ \cdots$$ $$\Rightarrow \frac{1}{4}(1+\frac{1}{2^2}+\cdots) >\frac{1}{3^2}+\frac{1}{5^2}+ \cdots$$ $$\Rightarrow \frac{1}{4}(1+S)> S'$$ $$\Rightarrow (1+S)> 4S'......Eqn(2)$$ From Equation 1 and 2 we get $$1+S> 3S-1$$ $$\Rightarrow 1> S$$ Which shows $$1> \frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}+ \cdots \infty$$

-