4

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

The Chaz 2.0
  • 10,464

2 Answers2

2

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

Bill Cook
  • 29,244
  • 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
1

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.

N. S.
  • 132,525