Proof By Mathematical Induction

[erok81]

Homework Statement

Use mathematical induction to prove the following statement.

$$n \geq 2,~ \sum_{k=1}^{n} \frac{1}{k^2}~<~1-\frac{1}{n}$$

Homework Equations

The Attempt at a Solution

This is the third problem I've done of this type, so I am by no means an expert. So this attempt may be completely wrong.

Basis step:
Prove that P(2) is true. The examples in the text start with proving 1 first. Since this is for all n greater or equal to 2, I figured I would start at the lowest possible n. Except the sum starts at 1 - so I was a little unsure here.

$$\frac{1}{2^2}~<~1-\frac{1}{2}~\Rightarrow~ \frac{1}{4}<\frac{1}{2}$$

This is true and therefore P(2) is true.

Induction step:
Assume that P(k) is true.
This is just a matter of replacing the n's and k's with k.

This yields:
$$\frac{1}{k^2}~<~1-\frac{1}{k}$$

Next, prove that P(k+1) is true. Here obviously the k's are replaced by (k+1)'s.

$$\frac{1}{(k+1)^2}~<~1-\frac{1}{(k+1)}$$

Since k comes before k+1 in the sum I tried this on the LHS...

$$\frac{1}{k^2}+\frac{1}{(k+1)^2}~<~1-\frac{1}{(k+1)}$$

This didn't work. I tried combining the LHS into one fraction. Same on the RHS. But could see definite proof that the RHS was greater than the LHS.

What step am I missing? Is there a better way to prove this?

 

[SammyS]

Your induction step is wrong.

It should be:

Assume that $$\sum_{k=1}^{m} \frac{1}{k^2}~<~1-\frac{1}{m}$$ is true for m ≥ 2.


Show that $$\sum_{k=1}^{m+1} \frac{1}{k^2}~<~1-\frac{1}{m+1}$$ is true.

 

[erok81]

Huh. I'll give that a try.

In my text for similar examples they do the induction like I have.

The book's only summation example goes like this.

$$\sum_{j=0}^{n}ar^{j}~=~ \frac{ar^{n+1}-a}{r-1}$$

They then show the k step as...

$$ar^{k}~=~ \frac{ar^{k+1}-a}{r-1}$$

And the (k+1) step just replacing the k's with (k+1)

Although...if I proceed in your manner, I have no idea what to do next. I could write out a few steps on the summation. But then I would be back to what I have

$$\frac{1}{k^2}+\frac{1}{(k+1)^2}~<~1-\frac{1}{(k+1)}$$

Except with m's instead of k's.

 

[SammyS]

I suspect your textbook does something different than what you are interpreting it as doing. (Perhaps I'll come back to this in a subsequent post.)

Notice that  $$\sum_{k=1}^{m+1} \frac{1}{k^2}=\frac{1}{(m+1)^2}+\sum_{k=1}^{m} \frac{1}{k^2}\ .$$

So,  $$\sum_{k=1}^{m+1} \frac{1}{k^2}<\frac{1}{(m+1)^2}+1-\frac{1}{m}\ .$$

You'll need to show that   $$\frac{1}{(m+1)^2}+1-\frac{1}{m}\leq1-\frac{1}{m+1}\ ,$$ for m ≥ 2.

.

 

[erok81]

Ok...I think I see what you are saying now. for the next 15 hours I have work and school. I'll come back to this as soon as I get off of work and try it again.

Thanks for the help so far!

 

[erok81]

Ok I finally got it.

Thanks again for the help. That made sense.

Now I just need to practice that induction step on more sums. I can do them on non-sums no problem. I think with what you've posted I should be able to get it.

 

[snits]

Isn't the problem as stated false? $\sum_{k=1}^n \frac{1}{k^2}$ will always be greater than 1 and $1 - \frac{1}{n}$ will be less than 1. I think what is meant is $\sum_{k=2}^n \frac{1}{k^2}$ instead. How does the condition $n \ge 2$ effect the start condition of $k=1$?

 

[SammyS]

Isn't the problem as stated false? $\sum_{k=1}^n \frac{1}{k^2}$ will always be greater than 1 and $1 - \frac{1}{n}$ will be less than 1. I think what is meant is $\sum_{k=2}^n \frac{1}{k^2}$ instead. How does the condition $n \ge 2$ effect the start condition of $k=1$?

Actually, $$\sum_{k=1}^n \frac{1}{k^2}=\frac{\pi^2}{6}\approx 1.64493\dots$$

 

[snits]

Actually, $$\sum_{k=1}^n \frac{1}{k^2}=\frac{\pi^2}{6}\approx 1.64493\dots$$

And that agrees with what I said. If the task is to prove $\sum_{k=1}^n \frac{1}{k^2} < 1 - \frac{1}{n}$ where $n \ge 2$, then we have a counterexample with the case of $n=2$.

$$\begin{align*}\sum_{k=1}^2 \frac{1}{k^2} &< 1 - \frac{1}{2} \\ \frac{1}{1^2} + \frac{1}{2^2} &< \frac{1}{2} \\ 1 + \frac{1}{4} &< \frac{1}{2} \\ \frac{5}{4} &< \frac{1}{2} \end{align*}$$

is obviously false.

If on the other hand the task is to prove $\sum_{k=2}^n \frac{1}{k^2} < 1-\frac{1}{n}$ where $n \ge 2$, then the proof by induction will work.

Or what am I missing here? It has been a long time (~15 years) since I have studied any of this, but I am pretty sure the condition $n \ge 2$ only effects the upper limit of the index.

 

[SammyS]

And that agrees with what I said. If the task is to prove $\sum_{k=1}^n \frac{1}{k^2} < 1 - \frac{1}{n}$ where $n \ge 2$, then we have a counterexample with the case of $n=2$.

...

You are absolutely correct.

I suppose there was a typo in the original post & the sum should have had n start at 2, not 1.