1

I'm working on proving the following statement using induction:

$$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$

Fair enough. I'll start with the basis step:

Basis Step: (n=1) $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ $$ \frac{1}{1^2} \le \frac{2}{1+1} $$ $$ 1 \le 1 \checkmark $$

Inductive Step: $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2(n+1)}{(n+1)+1} $$ $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2(n+1)}{n+2} $$

My goal is to prove $\forall_{n\ge1} s(n) \implies s(n+1) $ or that this inequality holds true for all $n\ge1$.

I'm not quite sure to go from here on the inductive step. I understand that I need to basically work some clever substitution and manipulation into the problem to end up with: $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2n}{n+1} $$

However, I'm not quite sure what needs to done to obtain this after attempting a few times.

Bob Shannon
  • 1,561

3 Answers3

2

For the inductive step: $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2n}{n+1} +\frac{1}{(n+1)^2}\le \frac{2n(n+1)+1}{(n+1)^2}=\frac{2n^2+2n+1}{n^2+2n+1}=\frac{2n+2+\frac{1}{n}}{n+2+\frac{1}{n}}\leq \frac{2(n+1)}{(n+1)+1}$$

meta_warrior
  • 3,288
  • 18
  • 34
  • The problem asks to prove that $ s(n+1) $ is $\le \frac{2n}{n+1}$, not $\le \frac{2(n+1)}{(n+1)+1}$? – Bob Shannon Nov 17 '13 at 04:24
  • 2
    The problem asks you to prove that $s(n)\le\frac{2n}{n+1}$. Notice that if we now replace $n$ with $n+1$ we get $s(n+1)\le\frac{2(n+1)}{(n+1)+1}$. – user71352 Nov 17 '13 at 04:34
1

I is true that $\displaystyle\sum_{r=1}^n \frac{1}{r^2} \leq \frac{2n}{n+1} $, so we need to prove that $\displaystyle \sum_{r=1}^{n+1} \frac{1}{r^2} \leq \frac{2(n+1)}{n+2}$. It is indeed true: $\displaystyle \sum_{r=1}^{n+1} \frac{1}{r^2} =\displaystyle\sum_{r=1}^n \frac{1}{r^2}+\frac{1}{(n+1)^2}\leq \frac{2n}{n+1}+\frac{1}{(n+1)^2}=\frac{2n(n+1)+1}{(n+1)^2}\leq \frac{2(n+1)}{n+2}$ since $2(n^3+3n^2)+5n+2=\bigg(2n(n+1)+1\bigg)(n+2)\leq 2(n+1)^3=2(n^3+3n^2)+6n+2$.

daulomb
  • 3,955
0

To prove the inductive step we assume it holds for $n=m$ and show for $n=m+1$. So

$\sum_{n=1}^{m+1}\frac{1}{r^{2}}=\sum_{n=1}^{m}\frac{1}{r^{2}}+\frac{1}{(m+1)^{2}}\le\frac{2m}{m+1}+\frac{1}{(m+1)^{2}}=\frac{1}{m+1}(2m+\frac{1}{m+1})=\frac{1}{m+1}\frac{2(m+1)m+1}{m+1}=\frac{m}{(m+1)^{2}}(2(m+1)+\frac{1}{m})=(\frac{m}{(m+1)^{2}}-\frac{1}{m+2})(2(m+1)+\frac{1}{m})+\frac{2(m+1)+\frac{1}{m}}{(m+2)}$

Notice that $\frac{m}{(m+1)^{2}}-\frac{1}{m+2}=\frac{m^{2}+2m-(m+1)^{2}}{(m+2)(m+1)^{2}}=\frac{-1}{(m+2)(m+1)^{2}}\le0$ so:

$\sum_{n=1}^{m+1}\frac{1}{r^{2}}\le\frac{2(m+1)+\frac{1}{m}}{m+2}\le\frac{2(m+1)}{(m+1)+1}$

user71352
  • 13,038