1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Try to write down the base case, inductive hypothesis and from there, tell us where are you stuck at $\endgroup$ – Joshua Jul 23 '16 at 13:43
  • $\begingroup$ 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... $\endgroup$ – intersomnium Jul 23 '16 at 14:10
  • $\begingroup$ @intersomnium use meta.math.stackexchange.com/questions/5020/… $\endgroup$ – A---B Jul 23 '16 at 14:37
  • $\begingroup$ @ritwiksinha I will, thanks :) $\endgroup$ – intersomnium Jul 23 '16 at 14:39
3
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – intersomnium Jul 23 '16 at 14:24
  • $\begingroup$ @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. $\endgroup$ – Pjotr5 Jul 23 '16 at 14:27
  • $\begingroup$ Awesome, I understand everything now. Thank you very much! :) $\endgroup$ – intersomnium Jul 23 '16 at 14:33
  • $\begingroup$ You're welcome. :) $\endgroup$ – Pjotr5 Jul 23 '16 at 14:35
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jul 23 '16 at 14:39
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.