# Generating induction proofs from graphs/integrals

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

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

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.

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

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