Tell me more ×
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.
up vote 4 down vote favorite

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.

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

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
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
2  
@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
show 10 more comments
up vote 2 down vote

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

share|improve this answer
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

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.