Take the 2-minute tour ×
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.

I just came across a question on an old take-home exam,

Prove, using induction, that $\sum_{k = 1}^{n} \frac{1}{k^2} > \frac{3}{2} - \frac{1}{n} + \frac{1}{2n^2} $

Then I remembered something that the professor said about his method of coming up with these problems by looking at graphs and integrals (and possibly partitions/lower sums ??).

How can we generate similar proofs by induction (where, say, the denominators have degree at most $= 3$)?
Can you demonstrate such a method with an example(s)?
I think we're looking for inequalities here...

*Note: I don't need help proving this inequality. *

share|improve this question
1  
Your disclaimer makes me smile: "Note: I don't need help proving this inequality." :) –  Bill Cook Oct 14 '11 at 0:16

2 Answers 2

up vote 1 down vote accepted

This is just an elaboration on Bill's answer.

Let $f(x)$ be a continuous, positive decreasing function, and let $F$ be an antiderivative of $F$.

Then $f(1)+f(2)+...+f(n) \geq F(n+1)-F(1)$.


A much more interesting application is the following, the idea is exactly the same:

Let $f(x)$ be a continuous, positive decreasing function, and let $F$ be an antiderivative of $f$.

Let

$$S_n:= f(1)+f(2)+...+f(n)- F(n) \,.$$ $$T_n:= f(1)+f(2)+...+f(n)- F(n+1) \,.$$

Then

$$S_1 \geq S_2 \geq S_3 \geq ... \geq S_n ..\geq T_n \geq ...\geq T_1 \,.$$

This is basically Cauchy's Integral Test.

You can get nice induction inequalities simply by taking $$S_1 \geq S_n \geq T_n \geq T_1 \,.$$

But you can also use this to prove that the sequences are convergent.

Each of the case $f(x)=\frac{1}{x} \,;\, f(x)=\frac{1}{2\sqrt{x}} \,;\, f(x)=\frac{1}{x^2}$ lead to a famous convergent sequence, the first one is my favourite application... Also the case $f(x)=\frac{1}{x^p}$ tells you something about the $p$-series.

share|improve this answer
    
This is exactly what I was looking for! Thanks for the theory lesson and the examples. –  The Chaz 2.0 Oct 13 '11 at 22:32
    
Well there is also a hidden "assignment" in it, you can try to prove that $S_n \leq S_{n-1}$ and $T_n \geq T_{n-1}$. The inequality $S_n \geq T_n$ is easier ;) –  N. S. Oct 13 '11 at 22:37
    
I have a hard enough time doing non-hidden assignments! –  The Chaz 2.0 Oct 13 '11 at 22:42

$\int_1^n 1/x^2\,dx = 1 - 1/n$

The sum $\sum_{k=1}^{n-1} 1/k^2$ is a left hand rule approximation of the above integral (using $\Delta x=1$). Since this function is decreasing the left hand rule gives an overestimate. Therefore, $\sum_{k=1}^{n-1} 1/k^2 > 1-1/n$. Adding $1/n^2$ to both sides gives $\sum_{k=1}^n 1/k^2 > 1-1/n+1/n^2$.

I'm not entirely sure how to arrive at your particular problem, but I imagine a slightly different estimate will do the trick.

Also, if we used a right hand rule, we could rig up an inequality with the summation on the smaller side (since right hand rule gives an underestimate for decreasing functions).

Edit: Sorry I didn't actually answer your question!

Use $\int_1^n 1/x^3\,dx=1-2/n^2$ and so $\sum_{k=1}^{n-1} 1/k^3 > 1-2/n^2$ and thus $\sum_{k=1}^n 1/k^3 > 1-2/n^2+1/n^3$

share|improve this answer
    
Since the difference between your answer and the problem above is $\frac{1}{2}+\frac{1}{2n^2}=\frac{1}{2}[f(1)+f(n)]$, it is clear that the trapezoid rule was used ;) –  N. S. Oct 13 '11 at 22:11
    
So would a method be to find an interval where a rational function is decreasing (increasing) and use a left (right) approximation? –  The Chaz 2.0 Oct 13 '11 at 22:29
1  
Well it is easiest to start with a function which is increasing or decreasing. If you start with a random rational function, it has only finitely many CP, so you know that is monotonic for all $x \geq a$. Then do exactly the same as above but starting at $a$ instead of $1$. –  N. S. Oct 13 '11 at 22:33

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.