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$

closed as off-topic by Carl Mummert, Math1000, Najib Idrissi, Watson, user91500 Jul 24 '16 at 9:18

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, Math1000, Najib Idrissi, Watson, user91500
If this question can be reworded to fit the rules in the help center, please edit the question.

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