# Proof by Induction for inequality, $\sum_1^nk^{-2}\lt2-(1/n)$

Let n be a positive natural number , $n\ge 2$, then. $\displaystyle\sum_{k=1}^n \frac{1}{k^2} \lt 2 - \frac{1}{n}$

The basis step was easy but could someone give me a hint in the right direction as to how to do the induction step?

I tried this:

$\displaystyle\sum_{k=1}^k \frac{1}{k^2} + \frac{1}{(k + 1)^2} \lt 2 - \frac{1}{k + 1}$

But its getting me nowhere or i am doing something wrong. I am no expert so a clear explanation would be appreciated. Thanks.

-
Perhaps this might also help in a general sort of way: math.stackexchange.com/questions/19485/… –  Arturo Magidin Apr 19 '11 at 1:59

Here is how the induction step should look:

$$\text{Assume } \sum_{k = 1}^{n} \frac{1}{k^2} < 2 - \frac{1}{n}.$$

Then,

$$\sum_{k = 1}^{n+1} \frac{1}{k^2} = \sum_{k = 1}^{n} \frac{1}{k^2} + \frac{1}{(n+1)^2} < 2 - \frac{1}{n} + \frac{1}{(n+1)^2}$$

Now the problem is reduced to showing that

$$- \frac{1}{n} + \frac{1}{(n+1)^2} \leq - \frac{1}{n+1}$$

which is easy to show with some algebra. The point is that you have to use the assumption that it works for $n$. Also, when you use $k$ as an index over which you are summing, you should not use $k$ anywhere else like you did above.

Hope this helps.

-
I noticed you added the 1/(n + 1)^2 to both sides, can you explain why this was done? I think thats what i was missing. –  1337holiday Apr 19 '11 at 1:42
I pulled the $n+1$ term off of the sum. We assumed that what was left was less than $2 - \frac{1}{n}$. The $n+1$ term still remains. –  Bill Karr Apr 19 '11 at 1:48
That is how induction works... you assume the formula or statement is true for some $n$, and then you try to show the statement is true for $n+1$. –  Bill Karr Apr 19 '11 at 1:49
The heart of induction is that first you prove a base case (here n=2), then you prove that if it is true for n then it is true for n+1. So he is proving it true for n+1, given that it is true for n. Look at the upper limit of the sums-that is where the $\frac{1}{(n+1)^2} comes from. – Ross Millikan Apr 19 '11 at 1:52 @1337holiday: Say your wallet has 10 bills in it, and you want to show that you have less than 100 dollars in it; if you know that the last bill is either a 20 or less; and you know that the first 9 bills add up to at most 60 dollars, you don't need to count all the bills: you can just say: "the first 9 are at most 60, and the last bill is at most 20, so the ten bills together add up to at most 80 dollars, less than 100." Here you have a sum of$n+1$things. And you know (thanks to the induction hypothesis) that the first$n$add up to at most$2 - \frac{1}{n}$; (cont) – Arturo Magidin Apr 19 '11 at 2:18 What you write is actually what you are trying to show. However, you are almost there. For the induction step, you get to assume that $$\sum_{k=1}^n \frac{1}{k^2} < 2 - \frac{1}{n}.$$ Then, you need to show the statement holds for$k = n+1\$:

$$\sum_{k=1}^{n+1} \frac{1}{k^2} = \sum_{k=1}^n \frac{1}{k^2} + \frac{1}{(n+1)^2} < \dots$$

-
The only thing that i am seeing is that the denominator is always significantly larger on the LHS and therefore it converges to 0? –  1337holiday Apr 19 '11 at 1:40
Use the induction hypothesis! –  JavaMan Apr 19 '11 at 1:45