# 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? Jul 24, 2012 at 22:08
• @joriki the person who gave it to me said it could? So, ethos I guess... Jul 24, 2012 at 22:10
• what about comparing it with $ln2$ Jul 24, 2012 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? Jul 24, 2012 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)$. Jul 24, 2012 at 22:26
• That's beautiful, Steven! Jul 24, 2012 at 22:40
• Of course, this is also the "integral test" estimate. Jul 24, 2012 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. Jul 25, 2012 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$$