A (probably trivial) induction problem: $\sum_2^nk^{-2}\lt1$
So I'm a bit stuck on the following problem I'm attempting to solve. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling with some algebraic gymnastics for a while now, but I can't seem to get the proof right. Proving it using calculus isn't a problem, but I'm struggling hither.
discrete-mathematics inequality summation induction
VividD
PaquitoPaquito
$\begingroup$ Why do you think that this problem can be solved using induction? $\endgroup$ – joriki Jul 24 '12 at 22:08
$\begingroup$ @joriki the person who gave it to me said it could? So, ethos I guess... $\endgroup$ – Paquito Jul 24 '12 at 22:10
$\begingroup$ what about comparing it with $ln2$ $\endgroup$ – Theorem Jul 24 '12 at 22:17
As often happens with induction proofs, the easiest approach to proving this statement (which doesn't seem inducable at all - after all, how does knowing the sum for $n$ is less than $1$ tell you anything about the sum for $n+1$?) via induction is to transform it into a stronger one: $$\mathrm{For\ all\ } n\geq2, \frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2} \lt 1-\frac{1}{n}.$$
Now, the answer becomes a matter of simple algebra:
$$\sum_{i=2}^{n+1} \frac{1}{i^2} = \sum_{i=2}^{n} \frac{1}{i^2} +\frac{1}{(n+1)^2}\lt 1-\frac{1}{n}+\frac{1}{(n+1)^2}\lt 1-\frac{1}{n}+\frac{1}{n(n+1)} = 1-\frac{1}{n+1}.$$
Steven StadnickiSteven Stadnicki
$\begingroup$ Awesome! Many thanks...Might I ask what motivated the choice of subtracting 1/n? $\endgroup$ – Paquito Jul 24 '12 at 22:21
$\begingroup$ @Paquito To a certain extent, intuition - since the difference between consecutive terms of the form $1/n$ is on the order of $1/n^2$, I could see that adding a quadratic term to a $1/n$-sized 'gap' between the sum and 1 would give a $1/n+1$-sized gap; from there it was just a quick dig to see whether $1-1/n$ itself would work or whether I would need to do something like $1-1/(n+1)$. $\endgroup$ – Steven Stadnicki Jul 24 '12 at 22:26
$\begingroup$ That's beautiful, Steven! $\endgroup$ – Bruno Joyal Jul 24 '12 at 22:40
$\begingroup$ Of course, this is also the "integral test" estimate. $\endgroup$ – Robert Israel Jul 24 '12 at 23:53
$\begingroup$ @Paquito What Steven did is a classical example of inventor's paradox. Similarly proving $\frac{(2n-1)!!}{(2n)!!} < \frac{1}{\sqrt{n}}$ does not give in to the method of induction, while a stronger inequality $\frac{(2n-1)!!}{(2n)!!} < \frac{1}{\sqrt{n+1}}$ readily does. The explanation for why this works, is that the assumptions of the induction step are stronger in the latter case, allowing to draw stronger conclusion. $\endgroup$ – Sasha Jul 25 '12 at 1:22
Another proof is by comparison: note that
$$ {1 \over k^2} < {1 \over (k-1)k} $$
for all integers $k \ge 2$. Therefore
$$ {1 \over 2^2} + {1 \over 3^2} + \cdots + {1 \over n^2} < {1 \over 1 \times 2} + {1 \over 2 \times 3} + \cdots + {1 \over (n-1) \times n} $$
and now you need to find the sum on the right-hand side. But you can actually write
$$ {1 \over (k-1)k} = {1 \over k-1} - {1 \over k} $$
(this is just the usual partial fraction decomposition) and therefore
$$ {1 \over 1 \times 2} + {1 \over 2 \times 3} + \cdots + {1 \over (n-1) \times n} = \left( {1 \over 1} - {1 \over 2} \right) + \left( {1 \over 2} - {1 \over 3} \right) + \cdots + \left( {1 \over n-1} - {1 \over n} \right) $$
and the right-hand side what's called a ``telescoping sum'' -- that is, the pairs of terms $-1/2$ and $+1/2$, $-1/3$ and $+1/3$, and so on cancel. So the right-hand side is $1 - 1/n$, which is less than 1.
This came to mind pretty much immediately for me, because I happened to know that $\sum_{k \ge 2}^\infty 1/(k(k-1)) = 1$, but if you didn't know that ahead of time it would be a bit tricky to discover.
Michael LugoMichael Lugo
Yet another approach :
Let us first analyze the sum till infinity. Let $$ S= \frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}+ \cdots \infty$$ $$\Rightarrow S=(\frac{1}{2^2}+\frac{1}{4^2}+ \cdots\infty) +(\frac{1}{3^2}+\frac{1}{5^2}+ \cdots\infty ) $$$$\Rightarrow S= \frac{1}{4}(1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots\infty)+ S' $$ Where $$S'=\frac{1}{3^2}+\frac{1}{5^2}+ \cdots\infty $$ $$\Rightarrow S=\frac{1}{4}(1+S)+S'$$ $$\Rightarrow 3S=4S'+1........ Eqn(1)$$ Now examine the following inequality $$ (\frac{1}{2^2}-\frac{1}{3^2})+(\frac{1}{4^2}-\frac{1}{5^2})+ \cdots \infty > 0$$ $$\Rightarrow \frac{1}{2^2}+\frac{1}{4^2}+\cdots > \frac{1}{3^2}+\frac{1}{5^2}+ \cdots$$ $$\Rightarrow \frac{1}{4}(1+\frac{1}{2^2}+\cdots) >\frac{1}{3^2}+\frac{1}{5^2}+ \cdots $$ $$\Rightarrow \frac{1}{4}(1+S)> S'$$ $$\Rightarrow (1+S)> 4S'......Eqn(2)$$ From Equation 1 and 2 we get $$ 1+S> 3S-1$$ $$\Rightarrow 1> S$$ Which shows $$ 1> \frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}+ \cdots \infty$$
Barun DasguptaBarun Dasgupta
Not the answer you're looking for? Browse other questions tagged discrete-mathematics inequality summation induction or ask your own question.
Summation inductional proof: $\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2}<2$
Induction on inequalities: $\frac1{1^2}+\frac1{2^2}+\frac1{3^2}+\ldots+\frac1{n^2}<2$
Illustrative examples of a phenomenon in the logic of mathematical induction
Sum of series question: $S_n = 1 + 1/4 + 1/9 + 1/16 + 1/25 + … + 1/n^2 < 2$
Proof verification for proving $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ by induction
Integers and Induction Question (formula for Fibonacci numbers)
Proof by Math Induction
Mathematical Induction Proof Question dealing with integers
Proof by induction involving Harmonic Numbers
Proof by induction of $\sum_{n=1}^{\infty }\left ( x+1 \right )^{-n}=\frac{1}{x}$
How do I use rule induction to prove this relation?
Prove using induction that the $(2^{i})^{th}$ partial sum is less than $i + 1$ for $i \ge 1$
Proof by Induction process for Inequalities