4
$\begingroup$

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 it's getting me nowhere or I am doing something wrong. I am no expert so a clear explanation would be appreciated. Thanks.

$\endgroup$
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 1337holiday Apr 19 '11 at 1:42
  • $\begingroup$ 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. $\endgroup$ – Bill Karr Apr 19 '11 at 1:48
  • $\begingroup$ 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$. $\endgroup$ – Bill Karr Apr 19 '11 at 1:49
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 19 '11 at 1:52
  • 2
    $\begingroup$ @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) $\endgroup$ – Arturo Magidin Apr 19 '11 at 2:18
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The only thing that i am seeing is that the denominator is always significantly larger on the LHS and therefore it converges to 0? $\endgroup$ – 1337holiday Apr 19 '11 at 1:40
  • $\begingroup$ Use the induction hypothesis! $\endgroup$ – JavaMan Apr 19 '11 at 1:45

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