# Thread: Proof by induction inequality

1. ## 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.

2. ## Re: Proof by induction inequality

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*}.

3. ## 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}$.

4. ## 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}$.