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.

  • $\begingroup$ Why do you think that this problem can be solved using induction? $\endgroup$ – joriki Jul 24 '12 at 22:08
  • $\begingroup$ @joriki the person who gave it to me said it could? So, ethos I guess... $\endgroup$ – Paquito Jul 24 '12 at 22:10
  • $\begingroup$ what about comparing it with $ln2$ $\endgroup$ – 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}.$$

  • 1
    $\begingroup$ Awesome! Many thanks...Might I ask what motivated the choice of subtracting 1/n? $\endgroup$ – Paquito Jul 24 '12 at 22:21
  • 5
    $\begingroup$ @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)$. $\endgroup$ – Steven Stadnicki Jul 24 '12 at 22:26
  • $\begingroup$ That's beautiful, Steven! $\endgroup$ – Bruno Joyal Jul 24 '12 at 22:40
  • 4
    $\begingroup$ Of course, this is also the "integral test" estimate. $\endgroup$ – Robert Israel Jul 24 '12 at 23:53
  • 3
    $\begingroup$ @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. $\endgroup$ – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.