“Unrolling” a recurrence relation

Question

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

Answer 1

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