“Unrolling” a recurrence relation

int function(int n)
{
int i;

if (n <= 0) {
return 0;
} else {
i = random(n - 1);
return function(i) + function(n - 1 - i);
}
}


Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a random integer which is evenly distributed within the range [0,n]. If the average processing time is T(n), what is the value of T(6)T(6)?

(Assume that all instructions other than the random cost a negligible amount of time.)

This question was on Brilliant and I was following along their solution

              T(n)=T(i)+T(n−1−i)+1
T(n)=T(0)+T(n−1)+1
T(n)=T(1)+T(n−2)+1
....
T(n)=T(n−2)+T(1)+1
T(n)=T(n−1)+T(0)+1

nT(n)=2(T(0)+T(1)+....+T(n−2)+T(n−1))+n..........(1)
(n−1)T(n−1)=2(T(0)+T(1)+...+T(n−2))+n−1).........(2)


Subtract 1 from 2

            nT(n)−(n−1)T(n−1)=2T(n−1)+1


$$\frac{T(n)}{n+1}$$ = $$\frac{T(n-1)}{n}$$ + $$\frac{1}{n(n+1)}$$. They mention this is a telescoping sequence.

They say T(0) = 0 and then get

$$\frac{T(n)}{n+1}$$ = $$\frac{1}{(1)(2)}$$ + $$\frac{1}{(2)(3)}$$ + ... + $$\frac{1}{n(n+1)}$$ = $$\frac{n}{n+1}$$. I do not understand how they got to this equation from the previous. ​

Let $$S(n) = T(n)/(n+1)$$. Notice that $$S(0) = 0$$ and $$S(n) = S(n-1) + 1/n(n-1)$$. Thus $$S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + S(n-2) = \cdots$$ Continuing in this way, for any $$i \geq 0$$ we get $$S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(i+1)(i+2)} + S(i).$$ In particular, for $$i = 0$$ we get $$S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(1)(2)}.$$
Alternatively, you can prove by induction that $$S(n) = n/(n+1)$$. This clearly holds for $$n = 0$$. Assuming it holds for $$n-1$$, we prove it for $$n$$: $$S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{n-1}{n} = \frac{1+(n-1)(n+1)}{n(n+1)} = \frac{n^2}{n(n+1)} = \frac{n}{n+1}.$$
Alternatively, we can prove directly that $$T(n) = n$$ by induction. This clearly holds for $$n = 0$$. Assuming it holds for $$n-1$$, we prove it for $$n$$: $$T(n) = \frac{n+1}{n} T(n-1) + \frac{n+1}{n(n+1)} = \frac{n+1}{n} \cdot (n-1) + \frac{1}{n} = \frac{(n+1)(n-1)+1}{n} = \frac{n^2}{n} = n.$$