1

I'm working on proving the following statement using induction:

$$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$

Fair enough. I'll start with the basis step:

Basis Step: (n=1) $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ $$ \frac{1}{1^2} \le \frac{2}{1+1} $$ $$ 1 \le 1 \checkmark $$

Inductive Step: $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2(n+1)}{(n+1)+1} $$ $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2(n+1)}{(n+1)+1} $$ $$ \sum_{r=1}^n \frac{1}{r^2} + \frac{1}{(n+1)^2} \le \frac{2n}{n+1} + \frac{1}{(n+1)^2} $$ $$ \sum_{r=1}^{k+1} \le \frac{2n}{n+1} + \frac{1}{(n+1)^2} $$

My goal is to prove $\forall_{n\ge1} s(n) \implies s(n+1) $ or that this inequality holds true for all $n\ge1$.

I'm not quite sure to go from here on the inductive step. I understand that I need to basically work some clever substitution and manipulation into the problem to end up with: $$ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2(n+1)}{(n+1)+1} $$

However, I'm not quite sure what needs to done to obtain this after attempting a few times.

Bob Shannon
  • 1,561
  • 2
    The habit of working backwards from what is desired to a known fact has to be dropped. If every step can be reversed (and that is shown), it is a correct way of doing things. However, in many proofs steps are not necessarily reversible. The argument must be written up in the forward direction, from the known to the unknown. It is OK if in preliminary fooling around, you do things in the wrong direction. But the writeup needs to be in the right direction: one does not prove that $A\implies B$ by showing that $B\implies A$. – André Nicolas Nov 19 '13 at 07:17

1 Answers1

1

For the inductive step you have to show that $ \sum_{r=1}^{n} \frac{1}{r^2} \le \frac{2n}{n+1} $ implies $ \sum_{r=1}^{n+1} \frac{1}{r^2} \le \frac{2n+2}{n+2} $.

Start with $ \sum_{r=1}^{n+1} \frac{1}{r^2}$ and show that is less or equal than $\frac{2n}{n+1}+\frac{1}{(n+1)^2}$ (use the inductive hypothesis). Then, show that the last quantity is less or equal than $\frac{2n+2}{n+2}$.

P..
  • 14,929