Proving $ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ for all $n\geq 2$ by induction

Question

Question:

Let $P(n)$ be the statement that $1+\dfrac{1}{4}+\dfrac{1}{9}+\cdots +\dfrac{1}{n^2} <2- \dfrac{1}{n}$. Prove by mathematical induction. Use $P(2)$ for base case.

Attempt at solution:

So I plugged in $P(2)$ for the base case, providing me with $\dfrac{1}{4} < \dfrac{3}{2}$ , which is true.

I assume $P(n)$ is true, so I need to prove $P(k) \implies P(k+1)$.

So $\dfrac{1}{(k+1)^2} < 2 - \dfrac{1}{k+1}$.

I don't know where to go from here, do I assume that by the Inductive hypothesis that it's true?

Answer 1

For $n\geq 2$, let $S(n)$ denote the statement $$ S(n) : 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}. $$

Base step ($n=2$): $S(2)$ says that $1+\frac{1}{4}=\frac{5}{4}\leq\frac{3}{2}= 2-\frac{1}{2}$, and this is true.

Inductive step: Fix some $k\geq 2$ and suppose that $S(k)$ is true. It remains to show that $$ S(k+1) : 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{k^2}+\frac{1}{(k+1)^2}\leq 2-\frac{1}{k+1} $$ holds. Starting with the left-hand side of $S(k+1)$, \begin{align} 1+\frac{1}{4}+\cdots+\frac{1}{k^2}+\frac{1}{(k+1)^2} &\leq 2-\frac{1}{k}+\frac{1}{(k+1)^2}\quad\text{(by $S(k)$)}\\[1em] &= 2-\frac{1}{k+1}\left(\frac{k+1}{k}-\frac{1}{k+1}\right)\\[1em] &= 2-\frac{1}{k+1}\left(\frac{k^2+k+1}{k(k+1)}\right)\tag{simplify}\\[1em] &< 2-\frac{1}{k+1}.\tag{$\dagger$} \end{align} we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k+1)$ is true, thereby completing the inductive step.

By mathematical induction, for any $n\geq 2$, the statement $S(n)$ is true.

---

Addendum: How did I get from the "simplify" step to the $(\dagger)$ step? Well, the numerator is $k^2+k+1$ and the denominator is $k^2+k$. We note that, $k^2+k+1>k^2+k$ (this boils down to accepting that $1>0$). Since $\frac{1}{k+1}$ is being multiplied by something greater than $1$, this means that what is being subtracted from $2$ in the "simplify" step is larger than what is being subtracting from $2$ in the $(\dagger)$ step.

---

Note: It really was unnecessary to start your base case at $n=2$. Starting at $n=1$ would have been perfectly fine. Also, note that this exercise shows that the sum of the reciprocals of the squares converges to something at most $2$; in fact, the series converges to $\frac{\pi^2}{6}$.

Answer 2

Hint: You assume that the statement is true for $n=k$. In other words, $$ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{k^2}<2-\frac{1}{k}. $$ Now, add $\frac{1}{(k+1)^2}$ to both sides to get $$ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{k^2}+\frac{1}{(k+1)^2}<2-\frac{1}{k}+\frac{1}{(k+1)^2}. $$ What you would really like is that $$ 2-\frac{1}{k}+\frac{1}{(k+1)^2}<2-\frac{1}{k+1} $$ because then, by transitivity, your result would hold. So, can you prove that?

Answer 3

Your base case is wrong. You should realize it's true since $\frac{5}{4}<\frac{3}{2}$ obtained from $$1+\frac{1}{2^2} = \frac{5}{4} < \frac{3}{2} = 2-\frac{1}{2}$$ For the induction step, suppose $P(n)$ is true for all $n \in \{1,2,\ldots,k\}$. Then $$\begin{align}1+\frac{1}{2^2}+\ldots+\frac{1}{k^2}+\frac{1}{(k+1)^2} = \left(1+\frac{1}{2^2}+\ldots+\frac{1}{k^2}\right)+\frac{1}{(k+1)^2} \\ < \left(2-\frac{1}{k} \right)+\frac{1}{(k+1)^2}\end{align}$$ Now if you can show that $$\left(2-\frac{1}{k} \right)+\frac{1}{(k+1)^2}<2-\frac{1}{k+1}$$ you are done. It is possible to get to that inequality simply starting with the fact that $\frac{1}{k+1}<\frac{1}{k}$

Answer 4

Notice that for $k\ge2$ you have $$\frac1{k^2} \le \frac1{k(k-1)} = \frac1{k-1} - \frac{1}{k}.$$ Using this we can get $$\sum_{k=1}^{n} \frac1{k^2} = 1+\frac1{2^2}+\frac1{3^2}+\dots+\frac1{n^2} \le 1+\frac1{2\cdot 1}+\frac1{3\cdot 2}+\dots+\frac1{n(n-1)} \le\\\le 1+\left(1-\frac12\right)+\left(\frac12-\frac13\right)+\dots+\left(\frac1{n-1}-\frac1n\right).$$ Notice that many terms cancel out and in the end we get $$\sum_{k=1}^n \frac1{k^2} \le 2-\frac1n.$$

This is called telescoping series. (In fact, it is probably the best known telescoping series - it is also mentioned in the Wikipedia article I linked to.)

It is not difficult to rewrite this to induction proof. Induction step would be $$\sum_{k=1}^n \frac1{k^2}+\frac1{(n+1)^2} \le \left(2-\frac1n\right) + \frac1{(n+1)^2} \le \left(2-\frac1n\right) + \left(\frac1n -\frac1{n+1}\right) =\\= 2-\frac1{n+1}.$$ (The first inequality is from the induction hypothesis. The second one is from the equality given at the beginning of this post.)

As an exercise you might try to prove that $\sum\limits_{k=2}^n \dfrac1{k(k-1)} =1-\dfrac1n$ in a similar way. See also this post and some other posts about the same sum.

Answer 5

Although OP asks for proof by induction, other answers cover it, so I will add solution through integral estimation. What we will use is integral test for convergence of series, more precisely, the last line in the proof section of Wiki.

We have estimate $$\sum_{k=1}^n\frac 1{k^2} \leq 1 + \int_1^n \frac{dx}{x^2} = 1 + \left(-\left.\frac 1x\ \right|_1^n \right) = 2 - \frac 1 n$$ (see this for visualization)