# Proving a summation by induction

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.

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

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.

• 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$? – thegoodhunter-9115 Nov 10 '19 at 17:47

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.

• Shouldn't the fact be multiplicative? – thegoodhunter-9115 Nov 10 '19 at 16:38
• "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$. – fleablood Nov 10 '19 at 17:01
• "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. – fleablood Nov 10 '19 at 17:03
• And you are right, of course. – José Carlos Santos Nov 10 '19 at 17:07
• @fleablood Sorry, my mistake. – thegoodhunter-9115 Nov 10 '19 at 17:20