Tuesday, January 1, 2019

discrete mathematics - Proving $ 1+frac{1}{4}+frac{1}{9}+cdots+frac{1}{n^2}leq 2-frac{1}{n}$ for all $ngeq 2$ by induction



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



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...