4
$\begingroup$

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

  • 1
    Your disclaimer makes me smile: "Note: I don't need help proving this inequality." :)2011-10-14

2 Answers 2

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.

  • 0
    I have a hard enough time doing non-hidden assignments!2011-10-13
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$

  • 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$.2011-10-13