Proof By Mathematical Induction

  • #1
erok81
464
0

Homework Statement



Use mathematical induction to prove the following statement.

[tex]n \geq 2,~ \sum_{k=1}^{n} \frac{1}{k^2}~<~1-\frac{1}{n}[/tex]

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. :redface:

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.

[tex]\frac{1}{2^2}~<~1-\frac{1}{2}~\Rightarrow~ \frac{1}{4}<\frac{1}{2}[/tex]

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:
[tex]\frac{1}{k^2}~<~1-\frac{1}{k}[/tex]

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

[tex]\frac{1}{(k+1)^2}~<~1-\frac{1}{(k+1)}[/tex]

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

[tex]\frac{1}{k^2}+\frac{1}{(k+1)^2}~<~1-\frac{1}{(k+1)}[/tex]

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?
 
Physics news on Phys.org
  • #2
Your induction step is wrong.

It should be:

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


Show that [tex]\sum_{k=1}^{m+1} \frac{1}{k^2}~<~1-\frac{1}{m+1}[/tex] is true.
 
  • #3
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.

[tex] \sum_{j=0}^{n}ar^{j}~=~ \frac{ar^{n+1}-a}{r-1}[/tex]

They then show the k step as...

[tex] ar^{k}~=~ \frac{ar^{k+1}-a}{r-1}[/tex]

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

[tex]
\frac{1}{k^2}+\frac{1}{(k+1)^2}~<~1-\frac{1}{(k+1)}
[/tex]

Except with m's instead of k's.
 
  • #4
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  [tex]\sum_{k=1}^{m+1} \frac{1}{k^2}=\frac{1}{(m+1)^2}+\sum_{k=1}^{m} \frac{1}{k^2}\ .[/tex]

So,  [tex]\sum_{k=1}^{m+1} \frac{1}{k^2}<\frac{1}{(m+1)^2}+1-\frac{1}{m}\ .[/tex]

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

.
 
  • #5
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!
 
  • #6
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.
 
  • #7
Isn't the problem as stated false? [itex]\sum_{k=1}^n \frac{1}{k^2}[/itex] will always be greater than 1 and [itex]1 - \frac{1}{n}[/itex] will be less than 1. I think what is meant is [itex]\sum_{k=2}^n \frac{1}{k^2}[/itex] instead. How does the condition [itex]n \ge 2[/itex] effect the start condition of [itex]k=1[/itex]?
 
  • #8
snits said:
Isn't the problem as stated false? [itex]\sum_{k=1}^n \frac{1}{k^2}[/itex] will always be greater than 1 and [itex]1 - \frac{1}{n}[/itex] will be less than 1. I think what is meant is [itex]\sum_{k=2}^n \frac{1}{k^2}[/itex] instead. How does the condition [itex]n \ge 2[/itex] effect the start condition of [itex]k=1[/itex]?

Actually, [tex]\sum_{k=1}^n \frac{1}{k^2}=\frac{\pi^2}{6}\approx 1.64493\dots[/tex]
 
  • #9
SammyS said:
Actually, [tex]\sum_{k=1}^n \frac{1}{k^2}=\frac{\pi^2}{6}\approx 1.64493\dots[/tex]


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

[tex]\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*}[/tex]

is obviously false.

If on the other hand the task is to prove [itex]\sum_{k=2}^n \frac{1}{k^2} < 1-\frac{1}{n}[/itex] where [itex]n \ge 2[/itex], 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 [itex]n \ge 2[/itex] only effects the upper limit of the index.
 
  • #10
snits said:
And that agrees with what I said. If the task is to prove [itex]\sum_{k=1}^n \frac{1}{k^2} < 1 - \frac{1}{n}[/itex] where [itex]n \ge 2[/itex], then we have a counterexample with the case of [itex]n=2[/itex].

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

Similar threads

Replies
15
Views
2K
Replies
6
Views
2K
Replies
5
Views
1K
Replies
4
Views
1K
Replies
3
Views
990
Replies
6
Views
1K
Replies
1
Views
1K
Back
Top