solve recurrence relation: comparisons to construct binary search tree with maple

Question

I would like to solve the recurrence relation for the average number of comparisons necessary to the construction of a binary search tree.

the recurrence is $$ i(n) = n - 1 + \frac{2}{n} \sum_{k=0}^{n-1}i(k), \quad i(0) = 0 $$

and the result of rsolve is:

rsolve({i(0) = 0, i(n) = n-1+2*(sum(i(k), k = 0 .. n-1))/n}, i(n))

(It does nothing)

What am I doing wrong?

Answer 1

It seems the solver is not able to handle the summation statement. Trying now to avoid the summation: \begin{align} i(n) &= n - 1 + \frac{2}{n} \sum_{k=0}^{n-1}i(k) \\ i(n+1) &= n + \frac{2}{n+1} \sum_{k=0}^ni(k) \\ &= \frac{2}{n+1}i(n) + n + \frac{2}{n+1} \sum_{k=0}^{n-1} i(k) \\ &= \frac{2}{n+1}i(n) + n + \frac{n}{n+1} \left( i(n) - n + 1 \right) \\ &= \frac{n+2}{n+1} i(n)-\frac{n^2}{n+1}+\frac{n}{n+1} + n \\ &= \frac{n+2}{n+1} i(n) + \frac{2n}{n+1} \\ \end{align} This gives: $$ i(n) = \frac{n+1}{n} i(n-1) - \frac{2}{n} + 2 \quad (n > 0) $$ which you should be able to feed to Maple.

Test: The first sequence elements are \begin{align} i(0) &= 0 \\ i(1) &= 0 \\ i(2) &= 1 \\ i(3) &= 2 + 2/3 = 8/3 \\ i(4) &= 3 + 11/6 = 29 / 6 =^! 5/4 \, 8/3 - 1/2 + 2 = 10/3 + 3/2 = 29/6 \end{align}

Answer 2

Would you be ok with an answer like,

i(n) = (2*n+2)*Psi(n+1)+(2*gamma-4)*n+2*gamma;

where Psi is the digamma function as defined here?

I got that by issuing following in Maple 2015,

rsolve( {(it(n+1) - n/(n+1)*it(n) - n + n^2/(n+1)
          - n/(n+1))*(n+1)/2 = it(n), it(0)=0}, it(n) );