<s>[INST] Proving using Mathematical Induction from my discrete math class This is a practice exercise from our class about proving inequalities using mathematical induction. I've been stuck on the last step for quite a while now.
This is the Question. "Prove that $\sum_{k=1}^n\frac{1}{k^2}=\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{n^2}\le 2-\frac{1}{n}$ whenever $n$ is a positive integer."
This is my attempt to prove it.
Step 1: Base case $(n=1)$
$\sum_{k=1}^1\frac{1}{(1)^2}\le2-\frac{1}{1}$
$1\le1$
Step 2: Induction hypothesis
Assume that $\sum_{k=1}^n\frac{1}{k^2}\le 2-\frac{1}{n}$ is true for $n=c$
Then, $\sum_{k=1}^c\frac{1}{k^2}\le 2-\frac{1}{c}$
Step 3: prove that it is true for $n=c+1$
$\sum_{k=1}^{c+1}\frac{1}{k^2}$ $\le$ $2-\frac{1}{c}+\frac{1}{(c+1)^2}$
$\le 2+\frac{-(c+1)^2+c}{c(c+1)^2}$
$\le 2+\frac{-(c^2+2c+1)+c}{c(c+1)^2}$
$\le 2+\frac{-c^2-2c-1+c}{c(c+1)^2}$
$\le 2-\frac{c^2+c+1}{c(c+1)^2}$
$\le 2-\frac{c^2+c}{c(c+1)^2}-\frac{1}{c(c+1)^2}$
$\le 2-\frac{c(c+1)}{c(c+1)^2}-\frac{1}{c(c+1)^2}$
$\le 2-\frac{1}{c+1}-\frac{1}{c(c+1)^2}$
I'm Stuck on this step.
 [/INST] It is very straightforward induction. You just add
$\dfrac{1}{(n+1)^{2}}$ to both sides of $P(n)$ and you get
$2-\dfrac{1}{n}+\dfrac{1}{(n+1)^{2}}$ must be less than $2-\dfrac{1}{n+1}$ .
Making all the simplifications we get
$\dfrac{n+2}{(n+1)^{2}}<\dfrac{1}{n}$ which is obviously true. So we get
$P(n+1)$ and we are done!
</s>