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

<br /> \frac{1}{k^2}+\frac{1}{(k+1)^2}~&lt;~1-\frac{1}{(k+1)}<br />

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}&lt;\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} &lt; 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} &amp;&lt; 1 - \frac{1}{2} \\ \frac{1}{1^2} + \frac{1}{2^2} &amp;&lt; \frac{1}{2} \\ 1 + \frac{1}{4} &amp;&lt; \frac{1}{2} \\ \frac{5}{4} &amp;&lt; \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} &lt; 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} &lt; 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.