2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ In $P(n)$, do you mean that the sum is $< n - 1/n$, rather than $<1/n$? Although as I look closer, it's probably $2 - 1/n$ on the right. $\endgroup$ – pjs36 Apr 4 '15 at 19:34
  • $\begingroup$ Yes it is. Sorry for the typo. Its 2 - 1/n $\endgroup$ – Donald Dang Apr 4 '15 at 19:37
  • $\begingroup$ The logic in the line "I assume $P(n)$ is true, so I need to prove $P(k)\Rightarrow P(k+1)$." is awkward. It should read: "I need to prove $P(k)\Rightarrow P(k+1)$, so I assume that $P(n)$ is true for $n=k$. $\endgroup$ – Michael Burr Apr 4 '15 at 19:57
  • $\begingroup$ The line "So $\frac{1}{(k+1)^2}<2-\frac{1}{k+1}$" doesn't seem to follow from the previous steps (even though it is true). Can you show how you conclude that? $\endgroup$ – Michael Burr Apr 4 '15 at 20:05
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ I will add that this idea is useful also for estimations for other sums. Some nice pictures related to the harmonic series $\sum_{k=1}^n \frac1k$ can be seen here. $\endgroup$ – Martin Sleziak Oct 25 '15 at 9:31
  • $\begingroup$ @MartinSleziak, thank you for the link. It serves as much better visual aid than my attempt with Alpha. $\endgroup$ – Ennar Oct 25 '15 at 9:36
0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your cancellation while telescoping isn't correct. The partial sum should be bounded by $2-\frac 1 n$. This is probably the reason why someone downvoted this answer. I will +1 after correction. $\endgroup$ – Ennar Oct 25 '15 at 9:09
  • $\begingroup$ @Ennar You are right. (Thanks for noticing it.) There were also some other typos (which I have edited before). I have no problem with the downvote, and I can think of plenty other reasons why the post might have been downvoted. $\endgroup$ – Martin Sleziak Oct 25 '15 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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