Solving a recurrence relation for the average-case running time A[n] for QuickSort:

A[n_]:=n-1+(1/n)(∑_(i=0)^(n-1))(A[i]+A[n-1-i]);

A[0]:=0;

A[1]:=0;

Mathematica cannot directly solve it  but it can graph it. 
(* The graphing is very slow because Mathematica computes values A[n] much more wastefully then Fibonacci numbers from the recurrence relation 
F[n]=F[n-1]+F[n-2]. *)

DiscretePlot[A[n],{n,0,15},PlotTheme->"Classic"]

It may be verified by direct calculation that the function

A[n] = 2(n+1)((∑_(i=1)^n)(1/i))-4n

satisfies the above recurrence relation for every n ≥ 1.

The graphs of both solutions coincide (the second was plotted with extra 
+.5 added to it so that one can see two graphs):

DiscretePlot[{A[n],2(n+1)((∑_(i=1)^n)(1/i))-4n+.5},{n,0,15},PlotTheme->"Classic"]

In order to prove that 
A[n] = 2(n+1)((∑_(j=1)^n)(1/j))-4n 
is a solution of the above recurrence relation, it suffices to show that for every n ≥ 1:

2(n+1)((∑_(j=1)^n)(1/j))-4n==n-1+(1/n)(∑_(i=0)^(n-1))(2(i+1)((∑_(j=1)^i)(1/j))-4i+2(n-i)((∑_(j=1)^(n-1-i))(1/j))-4(n-1-i))

Here is an experimental verification by graphing

DiscretePlot[{ 2(n+1)((∑_(j=1)^n)(1/j))-4n,n-1+(1/n)(∑_(i=0)^(n-1))(2(i+1)((∑_(j=1)^i)(1/j))-4i+2(n-i)((∑_(j=1)^(n-1-i))(1/j))-4(n-1-i))},{n,1,100}]

The difference between the sides of the equation is 0

DiscretePlot[{ 2(n+1)((∑_(j=1)^n)(1/j))-4n-(n-1+(1/n)(∑_(i=0)^(n-1))(2(i+1)((∑_(j=1)^i)(1/j))-4i+2(n-i)((∑_(j=1)^(n-1-i))(1/j))-4(n-1-i)))},{n,1,100}]

Here is an algebraic proof

In order to simplify calculations, we will eliminalte long summation (∑_(i=0)^(n-1)) from the recurrence relation. This can be obtained by calculating 
n A[n] - (n-1) A[n-1].
This way the following equality may be obtained from the recurrence ralation for A[n] - see textbook for a straightforward derivation.

For every n ≥ 1,
A[n]=(n+1) ((A[n-1])/n)+((2(n-1))/n)
It suffices to show that our solution given by
A[n]= 2(n+1)((∑_(i=1)^n)(1/i))-4n
and, therefore,
A[n-1]= 2n((∑_(i=1)^(n-1))(1/i))-4(n-1)
satisfies the equation.

Simplification of the right-hand side of the equation yields:

Expand[(n+1) (1/n)(2n((∑_(i=1)^(n-1))(1/i))-4(n-1))+((2(n-1))/n)]

(* Note. HarmonicNumber[k]=(∑_(i=1)^k)(1/i) *)

((2n)/n)+(2/n)-4 n+2 ((∑_(i=1)^(n-1))(1/i))+2 n ((∑_(i=1)^(n-1))(1/i))

-4 n+2 ((∑_(i=1)^n)(1/i))+2 n ((∑_(i=1)^n)(1/i))

The left-hand side of the equation is

Expand[2(n+1)((∑_(i=1)^n)(1/i))-4n]

-4 n+2 ((∑_(i=1)^n)(1/i))+2 n ((∑_(i=1)^n)(1/i))

So, lhs = rhs.

Bingo!

End of algebraic solution

Substituting the Euler's approximation of (∑_(i=1)^n)(1/i) in the above formula (see file Summationa.nb) we obtain:

A[n] ≈2(n+1)(Log[n]+.577+(1/(2n)))-4n

or

Simplify[2(n+1)(Log[n]+.577+(1/(2n)))-4n]

Since Log[n] = Log[2]×Log2[n], we conclude:

A[n] ≈2.154` +(1/n)-2.846` n+2Log[2] (1+n) Log2[n]

and by

N[2Log[2]]

1.3862943611198906`

A[n] ≈2.154 +(1/n)-2.846 n+1.386 (1+n) Log2[n]

or

A[n] ≈1.386 (1+n) Log2[n]-2.846 n+2.154 +(1/n)

The difference between the left-hand side and the right-hand side of the above approximation converges to 0 faster than (1/n).

Using closer approximation Log[n]+.577+(1/(2n))-(1/(12(n^2))) of Euler's formula one can get 

A[n] ≈ 

1.3862943611198906`(n+1)Log2[n]-2.8455686701969345` n+2.1544313298030655`+ (1/n)0.8333333333333334`-(0.16666666666666666`/(n^2))

the difference between which and the exact A[n] converges to 0 faster than (1/(n^2)).
The part highlighted yellow and its derivation is mandatory for all students; the rest of the aproximation and its derivation is optional - they are shown here for illustration purposes only.

( The textbook approximation was 

A[n] ≈ 1.386n Log2[n]-2.846 n  

- good enough if you don't want to be too accurate, although

A[n] ≈ 1.386(n+1) Log2[n]-2.846 n  

is somewhat better - see the 2 plots below.)

Textbook approximation vs the exact value:

DiscretePlot[{ 2(n+1)((∑_(j=1)^n)(1/j))-4n,1.386n Log2[n]-2.846 n },{n,1,100}]

The difference between the exact value and textbook approximation diverges to ∞ with n.

Improved approximation vs the exact value:

DiscretePlot[{ 2(n+1)((∑_(j=1)^n)(1/j))-4n,1.386(n+1) Log2[n]-2.846 n },{n,1,100}]

2(n+1)((∑_(j=1)^n)(1/j))-4n < n lg n for n ≤ 141 and

2(n+1)((∑_(j=1)^n)(1/j))-4n > n lg n for n ≥ 142

Plot[{ 2(n+1)((∑_(j=1)^n)(1/j))-4n,n Log2[n] },{n,1,200}]

Table[{ N[2(n+1)((∑_(j=1)^n)(1/j))-4n],N[n Log2[n]] },{n,141,142}]

The difference between the exact value and improved approximation converges to about 2.154 as n-> ∞.

Check of the more precise approximation:

Simplify[2(n+1)(Log[n]+.577+(1/(2n))-(1/(12(n^2))))-4n]

DiscretePlot[{ 2(n+1)((∑_(j=1)^n)(1/j))-4n,2.154` -0.16666666666666666`/(n^2)+0.8333333333333334`/n-2.846` n+2 (1+n) Log[n]},{n,1,100}]