# Mathematical Induction Inequality problem [closed]

I am trying to solve the following problem with mathematical induction: $$\forall n>1,\qquad \frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2}<\frac{n-1}{n}$$ but since I am new to the concept when it comes to inequalities I can't quite seem to work it out.

Help, anyone?

• Try to write down the base case, inductive hypothesis and from there, tell us where are you stuck at – Joshua Jul 23 '16 at 13:43
• I've gotten to the point where i need to prove that '(k-1)/k + 1/(k+1)^2 < k/(k+1)' but I can't seem to do it... – intersomnium Jul 23 '16 at 14:10
• @intersomnium use meta.math.stackexchange.com/questions/5020/… – A---B Jul 23 '16 at 14:37
• @ritwiksinha I will, thanks :) – intersomnium Jul 23 '16 at 14:39

Let $$f(n) = \frac{1}{2^2} + \cdots + \frac{1}{n^2}.$$ Now we want to show that $$f(n)<\frac{n-1}{n}\tag{1}$$ for all integers greater than $1$. A proof by induction consists of two equally important steps. In the base case we show that $(1)$ indeed holds for $n=2$. In the inductive step we assume that $(1)$ is true for some number $n$ and use that to show that it is also true for $n+1$.

Base case: We have $f(2)=\frac{1}{4} < \frac{1}{2}=\frac{2-1}{2}.$

Inductive step: Assume $(1)$ is true for some $n \geq 2$. We can calculate \begin{align*} f(n+1) &= \color{green}{f(n)} + \frac{1}{(n+1)^2} \\ & < \color{green}{\frac{n-1}{n}} + \frac{1}{(n+1)^2} \\ & < \frac{n-1}{n} + \frac{1}{n\cdot(n+1)} \\ &= \frac{(n+1)-1}{n+1}. \end{align*} The expressions in green indicate the essential part of the inductive step. This shows that $(1)$ is true for $n+1$. Together with the base case this proves $(1)$ for all $n\geq 2$.

• I understand everything all the way to the second half of the inductive step. How is (n−1)/n + 1/(n⋅(n+1)) equal to ((n+1)−1)/(n+1) ? Also, where did 1/(n*(n+1)) even come from? – intersomnium Jul 23 '16 at 14:24
• @intersomnium It came from the fact that $$\frac{1}{(n+1)^2}< \frac{1}{n(n+1)}$$ for $n \geq 2$. This bound is indeed the part that requires the most creative thinking in this proof. Showing that $$\frac{n-1}{n}+ \frac{1}{n(n+1)}=\frac{n}{n+1}$$ is an exercise in simplifying fractions. – Pjotr5 Jul 23 '16 at 14:27
• Awesome, I understand everything now. Thank you very much! :) – intersomnium Jul 23 '16 at 14:33
• You're welcome. :) – Pjotr5 Jul 23 '16 at 14:35
• @intersomnium You don't need to pull rabbits out of hats. It is very simple if you rewrite the inequality in standard form $\, x > 0,\,$ Then it reduces to a much simpler induction, that an increasing sequence which starts $> 0$ always remains $> 0$, which has an obvious inductive proof - see my answer. – Bill Dubuque Jul 23 '16 at 14:39

Hint $\$ To prove $\,f_n = {\rm rhs} - {\rm lhs} > 0\,$ for all $\,n\ge 2\,$ note $\,f_2 > 0\,$ (base)  and note

$$\ \color{#c00}{f_{n+1}-f_n} =\, \frac{1}{n(n+1)}-\frac{1}{(n+1)^2}\, =\, \frac{1}{n(n+1)^2} \color{#c00}{> 0}$$

thus $\, f_n > 0 \,\Rightarrow\, \color{#c00}{f_{n+1} > f_n} > 0\$ (induction step)

Remark $\$ The induction essentially shows that an increasing sequence stays $\ge$ its initial value, whose inductive proof is obvious, as above. Note how rearranging the inequality into standard form $\, x > 0\,$ allowed us to simplify the induction into a more intuitive and more general form. Many inductions can similarly be preprocessed to greatly simplify them. This is a special case of telescopic induction, about which you can find much discussion in prior posts on telescopy.

We want to prove: $$H_{n}^{(2)}\leq 2-\frac{1}{n}\tag{1}$$ by induction. $(1)$ holds for $n=1$, hence it is enough to prove that for every $n\geq 1$ $$H_{n+1}^{(2)}-H_{n}^{(2)}=\frac{1}{(n+1)^2}\leq \frac{1}{n}-\frac{1}{n+1} = \frac{1}{n(n+1)}\tag{2}$$ holds, but that is trivial. In a similar way we me prove the improved inequality: $$\boxed{\forall n\geq 1,\qquad H_{n}^{(2)}=\sum_{k=1}^{n}\frac{1}{k^2}\leq \zeta(2)-\frac{1}{\left(n+\frac{1}{2}\right)}+\frac{1}{12\left(n+\frac{1}{2}\right)^3}.} \tag{3}$$

It is interesting to point out that the last inequality can be used to prove Stirling's inequality.