<s>[INST] Proving an inequality by induction, how to figure out intermediate inductive steps? 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.
 [/INST] 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}$
</s>