1
$\begingroup$

How can I prove $$\sum_{i=2}^{n} \frac{1}{i^2-i}\lt1$$ by induction on $n$?

So far:

If $m$ is a natural number such that $m\ge2$, let $P(m)$ be the statement: $$\sum_{i=2}^{m} \frac{1}{i^2-i}\lt1$$

We will prove $P(m)$ by induction on $m$.

Base Case: P(2) is the statement: $$\sum_{i=2}^{2} \frac{1}{2^2-2}=\frac{1}{2}\lt1$$

So $P(1)$ is true.

Inductive Step: Let $k$ be a natural number such that $k\ge2$. Assume $P(k)$ for some arbitrary $k\ge2$.

$\sum_{i=2}^{n+1} \frac{1}{i^2-i}=\sum_{i=2}^{n} \frac{1}{i^2-i}+\frac{1}{(n+1)^2-(n+1)}\lt 1+\frac{1}{(n+1)^2-(n+1)}$ (by Ind. Hyp.).

I do not know where to go from here.

$\endgroup$
1
$\begingroup$

Well, since $\frac 1{(n+1)^2 -n} > 0$ and knowing $\sum\limits_{k=2}^n \frac 1{k^2 - k} = M < 1$, that isn't enough to prove $M + \frac 1{(n+1)^2 -n}< 1$.

We have to prove something a little stronger that $\sum\limits_{k=2}^n \frac 1{k^2 - k} $ is not just $< 1$ but less then $1-v_n$ for some $v_n > \frac 1{(n+1)^2 - n}$.

Let's figure what some of the differences are.

$\frac 1{2^2-2} = \frac 12 = 1-\frac 12$ so $v_1 = \frac 12$.

$\frac 1{2^2- 2} + \frac 1{3^2-3}=\frac 12 + \frac 16 = \frac 23$ and so $v_1 = \frac 13$.

$\sum\limits_{k=2}^4\frac 1{k^2-k}=\frac 23+\frac 1{12}=\frac 9{12}=\frac 34$ and $v_n = \frac 14$.

Can that possible be it?

Can it be true that $\sum\limits_{k=2}^n\frac 1{k^2-k}= 1-\frac 1n < 1$?

Well...... let's see:

We've done three base cases..

Induction step: $\sum\limits_{k=2}^n\frac 1{k^2-k}= 1-\frac 1n$ then

$\sum\limits_{k=2}^{n+1}\frac 1{k^2-k}=(\sum\limits_{k=2}^n\frac 1{k^2-k}) + \frac 1{(n+1)^2 - n}=$

$ 1-\frac 1n + \frac 1{(n+1)^2 - (n+1)} =$

$\frac {n-1}n + \frac 1{(n+1)((n+1)-1)} = \frac {n-1}n + \frac 1{n(n+1)}=$

$\frac {(n-1)(n+1)}{n(n+1)} + \frac 1{n(n+1)}=\frac {n^2-1}{n(n+1)} + \frac 1{n(n+1)}$

$\frac {n^2 -1+1}{n(n+1)} = \frac {n^2}{n(n+1)}=$

$\frac n{n+1} = 1 - \frac 1{n+1}$.

Excellent! It works.

......

I should note; A La Jose Carlos Santos excellent answer, that $\frac 1{n^2 - n} = \frac 1{n-1} - \frac 1n$. That makes

$\sum_{k=2}^n \frac 1{n^2 - n} = \sum_{k=2}^n(\frac 1{n-1} - \frac 1n)=(1 - \frac 12) + (\frac 12 -\frac 13) + (\frac 13 - \frac 14) + ......(\frac 1{n-1} - \frac 1n) = 1 - \frac 1n$.

Hence JC Santos's excellent answer.

It's a clever manipulation the first time you see $\frac 1{n^2 - n} = \frac {n- (n-1)}{n(n-1)} = \frac 1{n-1} - \frac 1n$ but one should get used to it. It's more common than one would think.

It's essential in proving that $\lim_{n\to \infty}(1 + \frac 1n)^n:= e$ actually converges and exists.

$\endgroup$
1
  • $\begingroup$ Thank you. Just one thing. Shouldn't the beginning and end of first sentence have fractions with denominator $(n+1)^2-n$ instead of $(n+1)^2-1$? $\endgroup$ – thegoodhunter-9115 Nov 10 '19 at 17:47
3
$\begingroup$

You can prove by induction that$$(\forall n\in\mathbb N\setminus\{1\}):\sum_{i=2}^n\frac1{i^2-i}=1-\frac1n.$$Actually, you do not need induction; just use the fact that $\frac1{i^2-i}=\frac1{i-1}-\frac1i$ and that therefore your sum is a telescoping sum.

$\endgroup$
5
  • $\begingroup$ Shouldn't the fact be multiplicative? $\endgroup$ – thegoodhunter-9115 Nov 10 '19 at 16:38
  • 1
    $\begingroup$ "Shouldn't the fact be multiplicative?" Not sure what you mean but $\frac 1{i^2-i} = \frac 1{i(i-1)} = \frac {i-(i-1)}{i(i-1)} = \frac i{i(i-1)}- \frac {i-1}{i(i-1)} = \frac 1{i-1} - \frac 1i$. $\endgroup$ – fleablood Nov 10 '19 at 17:01
  • $\begingroup$ "you do not need induction; just use ... and that therefore your sum is a telescoping sum" well, techically a collapsing sequence $(a_1-a_2) + (a_2 - a_3) + ........ (a_{n-1} - a_n) = a_1 - a_n$ is using induction...... but point taken. $\endgroup$ – fleablood Nov 10 '19 at 17:03
  • $\begingroup$ And you are right, of course. $\endgroup$ – José Carlos Santos Nov 10 '19 at 17:07
  • $\begingroup$ @fleablood Sorry, my mistake. $\endgroup$ – thegoodhunter-9115 Nov 10 '19 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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