Induction proof concerning a finite sum inequality

Printable View

June 10th 2011, 07:23 PM
Ontolog

Induction proof concerning a finite sum inequality

Here is the link:

https://docs.google.com/viewer?a=v&p...thkey=CO2G4q4F

Could someone help me with the style? Specifically, I don't like (4) and I wish there was a way to express (1) through a series of transformation on (3). Keeping the number of steps about the same or less of course.
June 10th 2011, 08:04 PM
BAdhi

here was the same post below. Sorry for the inconvenience
June 10th 2011, 08:05 PM
BAdhi

this is how I got it,

assume (1) is true up to n=p

then,
$\sum_{i=0}^{p} \frac{1}{i^2} \leq 2-\frac{1}{p}$

adjust and subtract both sides by $\frac{1}{(p+1)}$
$\sum_{i=0}^{p} \frac{1}{i^2}+\frac{1}{p}-\frac{1}{(p+1)}\leq 2-\frac{1}{(p+1)}$

since (8)
$\sum_{i=0}^{p} \frac{1}{i^2}+\frac{1}{p}-\frac{1}{(p+1)}\geq \frac{1}{(p+1)^2}+\sum_{i=0}^{p} \frac{1}{i^2}$
$\sum_{i=0}^{p} \frac{1}{i^2}+\frac{1}{p}-\frac{1}{(p+1)}\geq \sum_{i=0}^{p+1} \frac{1}{i^2}$
$\sum_{i=0}^{p+1} \frac{1}{i^2} \leq \sum_{i=0}^{p} \frac{1}{i^2}+\frac{1}{p}-\frac{1}{(p+1)} \leq 2-\frac{1}{(p+1)}$

$\sum_{i=0}^{p+1} \frac{1}{i^2} \leq 2-\frac{1}{(p+1)}$ which prove correct for n=p+1
June 10th 2011, 08:30 PM
TheCoffeeMachine

Try to mimick the style of typical proofs by induction:

http://oi53.tinypic.com/25qvdcn.jpg

And in general, by mimicking the style of others one can eventually develop one's own style, or so I believe. (Itwasntme)
June 10th 2011, 08:55 PM
Also sprach Zarathustra

A better bound:

$\sum_{i=0}^{p}\frac{1}{i^2}=1+\frac{1}{2^2}+\frac{ 1}{3^2}+\frac{1}{4^2}+...+\frac{1}{p^2}<1+\frac{1} {2}+\frac{1}{2^2}+\frac{1}{2^3}+...+\frac{1}{2^p}= 2-(\frac{1}{2})^p$
June 11th 2011, 01:22 AM
Archie Meade

Quote:

Originally Posted by Ontolog

Here is the link:

https://docs.google.com/viewer?a=v&p...thkey=CO2G4q4F

Could someone help me with the style? Specifically, I don't like (4) and I wish there was a way to express (1) through a series of transformation on (3). Keeping the number of steps about the same or less of course.

Alternatively,

P(k)

$\sum_{i=1}^{k}\frac{1}{i^2}\le\ 2-\frac{1}{k}$

P(k+1)

$\sum_{i=1}^{k+1}\frac{1}{i^2}\le\ 2-\frac{1}{k+1}$

Try to show that IF P(k) is true, THEN P(k+1) will also be true.

If P(k) is true, then P(k+1) is

$x+\frac{1}{(k+1)^2}\le\ 2-\frac{1}{k+1}\;\;?$

where $x\le\ 2-\frac{1}{k}$

$x\le\ 2-\frac{1}{k+1}-\frac{1}{(k+1)^2}\;\;?\;\;\Rightarrow\ x\le\ 2-\left[\frac{k+1+1}{(k+1)^2}\right]\;\;?$

$x\le\ 2-\left[\frac{1}{\left(\frac{[k+1]^2}{k+2}\right)}\right]\;\;?\;\;\Rightarrow\ x\le\ 2-\frac{1}{\left(\frac{k^2+2k+1}{k+2}\right)}\;\;?$

$\Rightarrow\ x\le\ 2-\frac{1}{\left(\frac{k[k+2]+1}{k+2}\right)}\;\;?$

True, since

$\frac{k(k+2)+1}{k+2}>\frac{k(k+2)}{k+2}$

so the above line is subtracting a smaller value from 2 than 1/k
June 11th 2011, 08:44 AM
melese

The inequality $\sum_{i=1}^{n}\frac{1}{i^2}<2-\frac{1}{n}$ can be established without using induction.

From $i^2>(i-1)i$ , it follows $\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{n^2}<1 +\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{ 1}{(n-1)\cdot n}$ , which is a telescoping sum.(a)
Therefore, $\sum_{i=1}^{n}\frac{1}{i^2}<1+1-\frac{1}{n}=2-\frac{1}{n}$ . (To Also sprach Zarathustra, $2-\frac{1}{n}<2-\frac{1}{2^n}$ for $n\geq1$ )

(a) $\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1 }{(n-1)\cdot n}=(\frac{1}{1}-\frac{1}{2})+(\frac{1}{2}-\frac{1}{3})+\cdots+(\frac{1}{n-1}-\frac{1}{n})$ ; the terms, except the first and last, cancel.