In the book "An Introduction to the Analysis of Algorithms" there is a recurrence relation for the number of compares used in Quicksort algorithm: $$ C_N=N+1+\sum_{0≤k≤N-1}\frac{1}{N}(C_k+C_{N−k−1}) $$ (See http://aofa.cs.princeton.edu/10analysis/ for details)

This recurrence relation is already solved in the book: $$ C_N = 2(N+1)H_N - 2N$$ , where $ H_N $ are harmonic numbers.

Now I'm trying to solve it using Mathematica:

RSolve[{c[n] == n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}], 
        c[0] == 0}, c[n], n]

Unfortunately, I can't get a result: RSolve just pretty prints input and doesn't solve anything.

Is there any way to solve such recurrences using Mathematica? Are there any other CASes which able to solve it?

In the book An Introduction to the Analysis of Algorithms there is a recurrence relation for the number of compares used in Quicksort algorithm: $$ C_N=N+1+\sum_{0≤k≤N-1}\frac{1}{N}(C_k+C_{N−k−1}) $$ (See http://aofa.cs.princeton.edu/10analysis/ for details)

This recurrence relation is already solved in the book: $$ C_N = 2(N+1)H_N - 2N,$$ where $ H_N $ are harmonic numbers.

Now I'm trying to solve it using Mathematica:

RSolve[{c[n] == n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}], 
        c[0] == 0}, c[n], n]

Unfortunately, I can't get a result: RSolve just pretty prints input and doesn't solve anything.

Is there any way to solve such recurrences using Mathematica? Are there any other CASes which able to solve it?