5
$\begingroup$

So I'm suppose to prove that $\sum 1/n^2 \le 2$. Should I use induction?

$\endgroup$

marked as duplicate by Ayman Hourieh, njguliyev, Dan Rust, Sasha, Johannes Kloos Sep 5 '13 at 13:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I've removed the discrete-mathematics tag (nothing discrete in sight here) and replaced summation by sequences-and-series. $\endgroup$ – Marc van Leeuwen Sep 5 '13 at 8:48
13
$\begingroup$

In potato's answer,it may seem that the stronger induction hypothesis came out of the blue. Here is another approach:

Hint: For all $n\in\mathbb{Z}^+$, we have: $\frac{1}{n^2}\leq\frac{1}{n^2-0.5^2}=\frac{1}{(n-0.5)(n+0.5)}$ Thus: $$\sum_{n=1}^\infty \frac{1}{n^2}\leq \sum_{n=1}^\infty \frac{1}{(n-0.5)(n+0.5)}$$ The sum in the right hand side of the inequality telescopes and can be shown to be equal to $2$.

$\endgroup$
  • 2
    $\begingroup$ Your starting index on the last summation is wrong. $\endgroup$ – oldrinb Sep 4 '13 at 22:38
  • $\begingroup$ @oldrinb I don't see that. Could you elaborate more ? $\endgroup$ – Amr Sep 4 '13 at 22:40
  • 1
    $\begingroup$ @Amr You're dividing by $0$ when $n = 1$ in the last summation. $\endgroup$ – 6005 Sep 4 '13 at 22:41
  • $\begingroup$ @oldring OK I see. $\endgroup$ – Amr Sep 4 '13 at 22:41
  • 1
    $\begingroup$ This answer is the most elementary and easy imo...and short and nice.+1 $\endgroup$ – DonAntonio Sep 4 '13 at 22:47
7
$\begingroup$

Hint: Prove the the following holds for all $n$ by induction.

$$\sum_1^n \frac{1}{k^2} \le 2 - \frac{1}{n}.$$

Is it not uncommon that when proving some inequality by induction, you will first need to strengthen the hypothesis to get the induction to work.

You can use the same technique to bound other values of the zeta function. For example, try showing $\zeta(3)$ is bounded above by $\frac{3}{2}$.

$\endgroup$
  • $\begingroup$ how did you get 2 - 1/n? $\endgroup$ – whatdidthefoxsay Sep 5 '13 at 0:12
  • $\begingroup$ @EricJan I looked first at $2-f(n)$ and tried to find the function of $n$ that would work. The function $1/n$ is a pretty natural guess. Many others work. The point is that you are strengthening the hypothesis just a little to get the induction off the ground. $\endgroup$ – Potato Sep 5 '13 at 0:37
  • $\begingroup$ As a clue to finding $f(n)$, note that $1/(n+1)^2$ is too weak (you just get the regular induction again), so you need to try something stronger. Then $1/n$ is really an obvious guess. $\endgroup$ – Potato Sep 5 '13 at 0:39
  • $\begingroup$ why do we need to find 2 - f(n)? what are we trying to do here is what I'm confused about. Strong induction contains too much magic for me to fully understand what's going on :( $\endgroup$ – whatdidthefoxsay Sep 5 '13 at 0:52
  • $\begingroup$ @EricJan Strong induction is something different. As I mentioned in my answer, there is a general principle that when proving inequalities by induction, one should try to use a stronger hypothesis to make the induction go more smoothly. So instead of using $2$, I tried to find out what stronger hypothesis to use. I guessed it would have the form $2-f(n)$. I then tried to find $f(n)$. Guessing worked here because there are many ways to strengthen the hypothesis that will work, so it wasn't hard to find one. All roads lead to Rome. $\endgroup$ – Potato Sep 5 '13 at 1:02
5
$\begingroup$

If you don't want to use induction, you can use the integral test for convergence which says that for a non-negative, strictly decreasing function $f$, we have $$\int_N^{\infty}f(x)dx \leq \sum_{n=N}^{\infty}f(n) \leq f(N) + \int_N^{\infty}f(x)dx.$$ In this case $f(x) = \dfrac{1}{x^2}$ and $N = 1$.

$\endgroup$
3
$\begingroup$

Should I use induction?

Not necessarily. Note that $\dfrac1{n^2}\lt\dfrac1{n(n-1)}=\dfrac1{n-1}-\dfrac1n$ for each $n\geqslant2$ hence, telescoping the terms of the series for $n\geqslant2$ shows that $$ \sum_{n=2}^{\infty}\frac1{n^2}\lt\sum_{n=\color{red}{\mathbf2}}^{\infty}\left(\dfrac1{n-1}-\dfrac1n\right)=\dfrac1{\color{red}{\mathbf2}-1}=1. $$ To conclude, add the $n=1$ term $\dfrac1{1^2}=1$.

$\endgroup$
0
$\begingroup$

There's a geometric proof that the sum of $1/n$ is less than 2.

One divides a square into rows of height 1/2, 1/4, 1/8, 1/16 &c.

Onto the top shelf of height 1/2, go 1/2, 1/3.

Onto the second shelf (1/4), go 1/4, 1/5, 1/6, 1/7, all equal to or less or equal to 1/4, so they will all fit.

And so on with 1/8, 1/16, &c.

Since all the squares $1/2^2$ to $1/\infty^2$ fit into the second square, then the sum of these numbers must be less than $2$.

$\endgroup$

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