# Proof by induction inequality

• Oct 4th 2012, 05:06 PM
deezy
Proof by induction inequality
Prove $\displaystyle \sum_{i=1}^n \frac{1}{i^2} \le 2 - \frac{1}{n}$ for all $\displaystyle n \epsilon \mathbb{N}$

Proof: i) Show P(1) holds.

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

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

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

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

Then $\displaystyle \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 $\displaystyle 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.
• Oct 4th 2012, 05:19 PM
Prove It
Re: Proof by induction inequality
Quote:

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

Proof: i) Show P(1) holds.

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

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

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

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

Then $\displaystyle \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 $\displaystyle 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 \displaystyle \begin{align*} (k + 1)^2 > k + 1 \end{align*} for all \displaystyle \displaystyle \begin{align*} k > 1 \end{align*}. Then you can say \displaystyle \displaystyle \begin{align*} 2 - \frac{1}{k} + \frac{1}{k + 1} < 2 + \frac{1}{k + 1} \end{align*}.
• Oct 4th 2012, 05:33 PM
deezy
Re: Proof by induction inequality
But I'm not sure how I can use $\displaystyle 2 + \frac{1}{k + 1}$ since it isn't less than $\displaystyle 2 - \frac{1}{k + 1}$.
• Oct 5th 2012, 01:51 PM
MathoMan
Re: Proof by induction inequality
$\displaystyle 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 $\displaystyle \frac{n^2+n+1}{n(n+1)^2}$ is greater than or equal to $\displaystyle \frac{1}{n+1}$,
because that would give you the result $\displaystyle 2-\frac{n^2+n+1}{n(n+1)^2}\leq 2-\frac{1}{n+1}$.

But needed inequality holds since
$\displaystyle \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}$.