Proving a summation by induction

Question

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.

Answer 1

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.

Answer 2

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.