Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I'm a bit stuck on the following problem I'm attempting. 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.

share|improve this question
    
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
add comment

3 Answers

up vote 42 down vote accepted

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}.$$

share|improve this answer
1  
Awesome! Many thanks...Might I ask what motivated the choice of subtracting 1/n? –  Paquito Jul 24 '12 at 22:21
4  
@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
3  
Of course, this is also the "integral test" estimate. –  Robert Israel Jul 24 '12 at 23:53
2  
@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
show 1 more comment

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.

share|improve this answer
add comment

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$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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