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.


No comments:

Post a Comment