# RSolve and a recurrence relation

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?

You can define c[n] with

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


and then use FindSequenceFunction to find the desired solution:

FindSequenceFunction[Table[c[n], {n, 1, 10}], n]

2 (1 + n) (-1 + EulerGamma + PolyGamma[0, 2 + n])

FullSimplify@%

2 (1 + n) (-1 + HarmonicNumber[1 + n])

%% == 2 (n + 1) HarmonicNumber[n] - 2 n // FullSimplify

True

• Dear Karsten, small question: what if instead of the condition c[0]=0 we had one of the kind c[n<2]=0, how do we express this in mathematica when defining and solving recurrence relations as you have exactly done in the above. Thanks in advance for any hints.
– user21766
Jul 14, 2017 at 13:33
• @user929304 You can use a PatternTest, a Condition, or Piecewise. Jul 14, 2017 at 20:10
• In my answer I could have used, e. g., c[n_?(# <= 0 &)] = 0;, c[n_ /; n <= 0] = 0;, or c[n_] /; n <= 0 := c[n] = 0; instead of c[0] = 0; or just c[n_] := c[n] = \[Piecewise] { {0, n <= 0}, {n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}], n > 0} } for both cases. Jul 14, 2017 at 20:13