Proof by induction inequality

Printable View

October 4th 2012, 05:06 PM
deezy

Proof by induction inequality

Prove $\sum_{i=1}^n \frac{1}{i^2} \le 2 - \frac{1}{n}$ for all $n \epsilon \mathbb{N}$

Proof: i) Show P(1) holds.

LHS = $\sum_{i=1}^1 \frac{1}{i^2} = \frac{1}{1} = 1$
RHS = $2 - \frac{1}{1} = 2 - 1 = 1$

LHS $\le$ RHS, thus, P(1) holds.

ii) Assume P(k) holds for some $k \epsilon \mathbb{N}$
That is, assume $\sum_{i = 1}^k \frac{1}{i^2} \le 2 - \frac{1}{k}$ .

To show: P(k + 1): $\sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k+1}$

Then $\sum_{i=1}^{k+1} \frac{1}{i^2} = \left( \sum_{i=1}^{k} \frac{1}{i^2} \right) + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{(k+1)^2}$

Not sure what to do next. In my next step, I said $2 - \frac{1}{k} + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{k+1}$ . But I'm not sure if this is the right path to take.
October 4th 2012, 05:19 PM
Prove It

Re: Proof by induction inequality

Quote:

Originally Posted by deezy

Prove $\sum_{i=1}^n \frac{1}{i^2} \le 2 - \frac{1}{n}$ for all $n \epsilon \mathbb{N}$

Proof: i) Show P(1) holds.

LHS = $\sum_{i=1}^1 \frac{1}{i^2} = \frac{1}{1} = 1$
RHS = $2 - \frac{1}{1} = 2 - 1 = 1$

LHS $\le$ RHS, thus, P(1) holds.

ii) Assume P(k) holds for some $k \epsilon \mathbb{N}$
That is, assume $\sum_{i = 1}^k \frac{1}{i^2} \le 2 - \frac{1}{k}$ .

To show: P(k + 1): $\sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k+1}$

Then $\sum_{i=1}^{k+1} \frac{1}{i^2} = \left( \sum_{i=1}^{k} \frac{1}{i^2} \right) + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{(k+1)^2}$

Not sure what to do next. In my next step, I said $2 - \frac{1}{k} + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{k+1}$ . But I'm not sure if this is the right path to take.

What you have done is fine, but you need to state why that inequality is true, the reason being that $\displaystyle \begin{align*} (k + 1)^2 > k + 1 \end{align*}$ for all $\displaystyle \begin{align*} k > 1 \end{align*}$ . Then you can say $\displaystyle \begin{align*} 2 - \frac{1}{k} + \frac{1}{k + 1} < 2 + \frac{1}{k + 1} \end{align*}$ .
October 4th 2012, 05:33 PM
deezy

Re: Proof by induction inequality

But I'm not sure how I can use $2 + \frac{1}{k + 1}$ since it isn't less than $2 - \frac{1}{k + 1}$ .
October 5th 2012, 01:51 PM
MathoMan

Re: Proof by induction inequality

$2-\frac{1}{n}+\frac{1}{(n+1)^2}=2-\left(\frac{1}{n}-\frac{1}{(n+1)^2} \right)=2-\frac{n^2+n+1}{n(n+1)^2}$

Now you just have to prove that $\frac{n^2+n+1}{n(n+1)^2}$ is greater than or equal to $\frac{1}{n+1}$ ,
because that would give you the result $2-\frac{n^2+n+1}{n(n+1)^2}\leq 2-\frac{1}{n+1}$ .

But needed inequality holds since
$\frac{n^2+n+1}{n(n+1)^2}& =\frac{n(n+1)+1}{n(n+1)^2}=\frac{n(n+1)}{n(n+1)^2} +\frac{1}{n(n+1)^2}= \\ &=\frac{1}{n+1}+\frac{1}{n(n+1)^2}\geq \frac{1}{n+1}$ .