## Thursday, March 31, 2011

### A Proof by Induction

This is mostly a test to see how well the latex script stuff from watchmath.com works in blogger. This came up on the Physics Forums and the problem was stated as:

Prove for $$n \ge 2$$ that $$\sum_{k=1}^n \frac{1}{k^2} < 1 - \frac{1}{n}$$

The above is false because $$\sum_{k=1}^n \frac{1}{k^2}$$ will always be greater than 1. What I believe was meant was:

Prove for $$n \ge 2$$ that $$\sum_{k=2}^n \frac{1}{k^2} < 1 - \frac{1}{n}$$

First, we prove it for the most simple case, $$n=2$$.

\begin{aligned}\sum_{k=2}^2 \frac{1}{k^2} &< 1 - \frac{1}{2}\\ \frac{1}{2^2} &< \frac{1}{2}\\ \frac{1}{4} &< \frac{1}{2}\end{aligned}

Now let's assume that $$\sum_{k=2}^m \frac{1}{k^2}$$ is true. Then $$\sum_{k=2}^m \frac{1}{k^2} < 1 - \frac{1}{m}$$ .

Now prove that $$\sum_{k=2}^{m+1} \frac{1}{k^2} < 1 - \frac{1}{m+1}$$ is true.

First we know that $$\sum_{k=2}^{m+1} = \frac{1}{{(m+1)}^2} + \sum_{k=2}^m$$, so prove that $$\frac{1}{{(m+1)}^2} + 1 - \frac{1}{m} \le 1 - \frac{1}{(m+1)}$$.

\begin{aligned}\frac{1}{{(m+1)}^2} + 1 - \frac{1}{m} &\le 1 - \frac{1}{(m+1)}\\ \frac{m}{m(m+1)^2} + \frac{m(m+1)^2}{m(m+1)^2} - \frac{(m+1)^2}{m(m+1)^2} &\le \frac{m}{(m+1)}\\ \frac{m+m(m+1)^2-(m+1)^2}{m(m+1)^2} &\le \frac{m}{m+1}\\ \frac{m+(m-1)(m+1)^2}{m(m+1)} &\le m\\ m+(m-1)(m+1)^2 &\le m^2(m+1)\\ m+(m-1)(m^2+2m+1) &\le m^3+m^2\\ m+m^3+2m^2+m-m^2-2m-1 &\le m^3+m^2\\ m^3+m^2-1 &\le m^3+m^2 \end{aligned}

$$\therefore\sum_{k=2}^n \frac{1}{k^2} < 1 - \frac{1}{n}$$ is true.

Note: This could quite possibly be wrong since it has been about 14 years since I have done any of this stuff.

Edit: Here is a picture illustrating this, using Maxima and Gnuplot.